Matematika diskrit untuk WMS: algoritma untuk mengompresi barang dalam sel (bagian 1)

Dalam artikel ini, kami akan memberi tahu Anda cara mengatasi masalah kurangnya sel bebas di gudang dan pengembangan algoritme optimasi diskrit untuk menyelesaikan masalah ini. Kita akan berbicara tentang bagaimana kita "membangun" model matematika dari masalah optimisasi, dan tentang kesulitan apa yang tiba-tiba kita temui ketika memproses data input untuk algoritma.

Jika Anda tertarik pada aplikasi matematika dalam bisnis dan Anda tidak takut akan transformasi formula identik yang sulit di tingkat kelas 5, maka selamat datang di kucing!

Artikel ini akan berguna bagi mereka yang menerapkan sistem WMS , bekerja di gudang atau industri logistik produksi, serta programmer yang tertarik pada aplikasi matematika dalam bisnis dan optimalisasi proses di perusahaan.

Bagian pengantar

Publikasi ini melanjutkan serangkaian artikel yang kami bagikan pengalaman sukses kami dalam menerapkan algoritma pengoptimalan dalam proses gudang.

Artikel sebelumnya menjelaskan secara spesifik gudang tempat kami memperkenalkan sistem WMS , dan juga menjelaskan mengapa kami perlu menyelesaikan masalah pengelompokan tumpukan barang yang tersisa selama implementasi sistem WMS , dan bagaimana kami melakukannya.

Ketika kami selesai menulis artikel tentang algoritma optimasi, ternyata menjadi sangat besar, jadi kami memutuskan untuk membagi materi yang terakumulasi menjadi 2 bagian:

• Pada bagian pertama (artikel ini) kita akan berbicara tentang bagaimana kita "membangun" model matematika dari masalah, dan tentang kesulitan besar apa yang tiba-tiba kita temui ketika memproses dan mengonversi data input untuk algoritma.
• Pada bagian kedua, kami akan memeriksa secara rinci implementasi algoritma dalam C ++ , melakukan eksperimen komputasi, dan merangkum pengalaman yang kami peroleh selama implementasi "teknologi cerdas" dalam proses bisnis pelanggan.

Cara membaca artikel. Jika Anda membaca artikel sebelumnya, Anda dapat langsung pergi ke bab "Ikhtisar solusi yang ada", jika tidak, maka uraian masalah yang harus dipecahkan dalam spoiler di bawah ini.

Ikhtisar solusi yang ada

Sebelum melanjutkan ke deskripsi algoritma yang dikembangkan oleh kami, ada baiknya untuk melakukan tinjauan singkat dari sistem WMS yang ada di pasar yang menerapkan fungsi kompresi optimal yang serupa.

Pertama-tama, perlu diperhatikan produk “1C: Enterprise 8. WMS Logistics. Warehouse Management 4 ”, yang dimiliki dan direplikasi oleh 1C dan termasuk dalam sistem WMS generasi keempat yang dikembangkan oleh AXELOT. Dalam sistem ini, fungsi kompresi dideklarasikan, yang dirancang untuk menggabungkan residu produk yang berbeda dalam satu sel yang sama. Perlu disebutkan bahwa fungsi kompresi dalam sistem seperti itu juga mencakup fitur-fitur lain, misalnya, memperbaiki penempatan barang dalam sel sesuai dengan kelas ABC mereka, tetapi kami tidak akan memikirkannya.

Jika Anda menganalisis kode sistem "1C: Perusahaan 8. WMS Logistics. Warehouse Management 4 ”(yang terbuka di bagian fungsional ini), maka kita dapat menyimpulkan yang berikut ini. Algoritma kompresi residu mengimplementasikan logika linear yang agak primitif dan tidak ada pembicaraan tentang kompresi "optimal". Secara alami, ia tidak mengatur pengelompokan partai. Beberapa klien dengan sistem seperti itu diimplementasikan mengeluh tentang hasil perencanaan kompresi. Misalnya, sering dalam praktek selama kompresi situasi berikut terjadi: 100 pcs. direncanakan untuk memindahkan barang yang tersisa dari satu sel ke sel lain, di mana 1 pc terbaring. barang, meskipun optimal dalam hal waktu untuk melakukan yang sebaliknya.

Selain itu, fungsi kompresi barang residual dalam sel dideklarasikan dalam banyak sistem WMS asing, tetapi, sayangnya, kami tidak memiliki umpan balik nyata mengenai efisiensi algoritma (ini adalah rahasia dagang), atau bahkan lebih banyak tentang kedalaman logikanya (perangkat lunak berpemilik dengan kode tertutup) kami tidak punya, oleh karena itu kami tidak bisa menilai.

Cari model matematika dari suatu masalah

Untuk merancang algoritma berkualitas tinggi untuk menyelesaikan masalah, pertama-tama perlu dirumuskan dengan jelas masalah ini secara matematis, yang akan kita lakukan.

Ada banyak sel $$$J$ di mana sisa-sisa beberapa barang. Selanjutnya, sel-sel tersebut akan disebut sel donor. Kami menunjukkan $$$w_j$ volume barang di dalam sel $$$$ j$ $.

Penting untuk mengatakan bahwa hanya satu produk dari satu pengiriman, atau beberapa pengiriman, yang sebelumnya dikelompokkan bersama dalam sebuah kluster (baca artikel sebelumnya ) dapat berpartisipasi dalam prosedur kompresi, yang disebabkan oleh penyimpanan dan penyimpanan barang yang spesifik. Untuk produk yang berbeda atau kelompok batch yang berbeda, prosedur kompresi yang terpisah harus diluncurkan.

Ada banyak sel $$$I$ di mana residu dari sel donor berpotensi ditempatkan. Sel-sel seperti itu akan disebut sel wadah. Ini bisa berupa sel bebas di gudang atau sel donor dari berbagai $$$J$ . Selalu banyak $$$J$ adalah bagian dari $$$I$ .

Untuk setiap sel $$$i$ dari banyak $$$I$ batas kapasitas yang ditetapkan $$$d_i$ diukur dalam dm3. Satu dm3 adalah kubus dengan sisi 10 cm. Produk yang disimpan di gudang cukup besar, jadi dalam hal ini, diskritisasi seperti itu sudah cukup.

Matriks jarak terpendek $$$s_ {ij}$ dalam meter di antara setiap pasangan sel $$$(i, j)$ dimana $$$i$ dan $$$j$ milik set $$$I$ dan $$$J$ sesuai.

Kami menunjukkan $$$S_ {ij}$ "Biaya" untuk memindahkan barang dari sel $$$i$ ke sel $$$j$ . Kami menunjukkan $$$D_i$ "Biaya" untuk memilih wadah $$$i$ untuk memindahkan residu dari sel lain ke dalamnya. Bagaimana tepatnya dan dalam satuan pengukuran apa nilai akan dihitung $$$S_ {ij}$ dan $$$D_i$ kami akan mempertimbangkan lebih lanjut (lihat bagian persiapan data masukan), sekarang cukup untuk mengatakan bahwa jumlah tersebut akan berbanding lurus dengan jumlah $$$s_ {ij}$ dan $$$d_i$ sesuai.

Ditunjukkan oleh $$$x_ {ij}$ nilai pengambilan variabel 1 jika sisa sel $$$j$ pindah ke wadah $$$i$ , dan 0 sebaliknya. Ditunjukkan oleh $$$y_i$ nilai pengambilan variabel 1 jika wadah $$$i$ berisi sisa-sisa produk, dan 0 sebaliknya.

Tugasnya adalah sebagai berikut : perlu menemukan begitu banyak wadah $$$I ^ *$ dan dengan demikian "menempelkan" sel donor ke wadah sel untuk meminimalkan fungsi

$$

$$\ min {F} = \ jumlah _ {i \ di I, ~ j \ in J} ^ {} S_ {ij} \ cdot x_ {ij} + \ sum _ {i \ in I} ^ {} D_ { i} \ cdot y_ {i}$$

di bawah batasan

$$

$$\ jumlah _ {j \ dalam J} ^ {} w_ {j} \ cdot x_ {ij} \ leq d_ {i} \ cdot y_ {i}, ~ untuk ~ semua orang ~ i \ dalam I$$

Secara total, dalam proses menghitung solusi untuk masalah tersebut, kami berusaha untuk:

• pertama, menghemat kapasitas penyimpanan;
• kedua, menghemat waktu pemilik toko.

Pembatasan terakhir berarti bahwa kita tidak dapat memindahkan barang ke wadah yang belum kita pilih, dan karena itu, belum “mengeluarkan biaya” untuk pilihan mereka. Pembatasan ini juga berarti bahwa volume barang yang diangkut dari sel ke wadah tidak boleh melebihi kapasitas wadah. Solusi masalah yang kami maksud adalah banyak wadah $$$I ^ *$ dan metode untuk menempelkan sel donor ke wadah.

Perumusan masalah optimisasi ini bukanlah hal baru, dan telah dipelajari oleh banyak ahli matematika sejak awal tahun 80-an abad terakhir. Dalam literatur asing, ada 2 masalah optimasi dengan model matematika yang sesuai: Masalah Lokasi Fasilitas Berkapasitas Sumber Tunggal dan Masalah Lokasi Fasilitas Berkapasitas Sumber Banyak (kami akan membahas perbedaan antara tugas di bawah ini). Patut dikatakan bahwa dalam literatur matematika pernyataan dari dua masalah optimisasi ini dirumuskan dalam hal menempatkan perusahaan di lapangan, oleh karena itu dinamakan “Fasilitas Lokasi”. Sebagian besar, ini merupakan penghargaan terhadap tradisi, karena untuk pertama kalinya kebutuhan untuk memecahkan masalah kombinatorial seperti itu berasal dari bidang logistik, sebagian besar, pertumbuhan industri militer di tahun 50-an abad lalu. Dalam hal lokasi perusahaan, tugas-tugas tersebut dirumuskan sebagai berikut:

• Ada sejumlah kota terbatas di mana berpotensi untuk menemukan perusahaan manufaktur (selanjutnya disebut kota manufaktur). Untuk setiap kota manufaktur, biaya untuk membuka perusahaan di dalamnya, serta pembatasan kapasitas produksi dari perusahaan yang dibuka di dalamnya, ditetapkan.
• Ada sejumlah kota terbatas di mana pelanggan sebenarnya berada (selanjutnya disebut sebagai kota klien). Untuk setiap kota klien tersebut, volume permintaan untuk produk ditetapkan. Untuk mempermudah, kami berasumsi bahwa produk yang dihasilkan dan dikonsumsi oleh perusahaan adalah satu.
• Untuk setiap pasangan, kota produsen dan kota klien, nilai biaya transportasi untuk pengiriman volume produk yang diperlukan dari produsen ke klien ditetapkan.

Diperlukan untuk menemukan kota mana yang membuka perusahaan dan cara menghubungkan pelanggan ke perusahaan tersebut untuk:

• Total biaya pembukaan usaha dan biaya transportasi sangat minim;
• Volume permintaan pelanggan yang melekat pada perusahaan terbuka tidak melebihi kapasitas produksi perusahaan ini.

Sekarang perlu disebutkan satu-satunya perbedaan dalam dua masalah klasik ini:

• Masalah Lokasi Fasilitas Berkapasitas Sumber Tunggal - klien hanya dipasok dari satu perusahaan terbuka;
• Masalah Lokasi Fasilitas Berkapasitas Multi-Sumber - klien dapat dipasok dari beberapa perusahaan terbuka pada saat yang sama.

Perbedaan antara kedua masalah tersebut pada pandangan pertama tidak signifikan, tetapi, pada kenyataannya, mengarah pada struktur kombinatorial yang sama sekali berbeda dari masalah-masalah tersebut dan, sebagai hasilnya, menjadi algoritma yang sama sekali berbeda untuk menyelesaikannya. Perbedaan antara tugas ditunjukkan pada gambar di bawah ini.


Fig. 3. a) Masalah Lokasi Fasilitas Berkapasitas Banyak Sumber


Fig. 3. b) Masalah Lokasi Fasilitas Berkapasitas Sumber Tunggal

Keduanya tugas $$$NP$ sulit, yaitu, tidak ada algoritma yang tepat yang akan memecahkan masalah seperti itu dalam waktu polinomial dari ukuran data input. Dengan kata-kata yang lebih sederhana, semua algoritma yang tepat untuk memecahkan masalah akan bekerja secara eksponensial, meskipun mungkin lebih cepat daripada pencarian lengkap opsi di dahi. Karena tugas $$$NP$ sulit, maka kita akan mempertimbangkan hanya perkiraan heuristik, yaitu algoritma yang akan secara stabil menghitung solusi yang sangat dekat dengan optimal dan akan bekerja cukup cepat. Jika ada minat pada tugas seperti itu, maka di sini Anda dapat menemukan ulasan yang bagus dalam bahasa Rusia.

Jika kita beralih ke terminologi masalah kompresi optimal barang dalam sel, maka:

• kota klien adalah sel donor $$$J$ dengan sisa-sisa barang,
• kota manufaktur - sel kontainer $$$I$ , di mana ia seharusnya menempatkan sisa-sisa dari sel lain,
• biaya transportasi - biaya waktu $$$S_ {ij}$ pemilik toko untuk memindahkan volume barang dari sel donor $$$j$ ke sel wadah $$$i$ ;
• biaya membuka perusahaan - biaya memilih wadah $$$D_i$ sama dengan volume sel wadah $$$i$ dikalikan dengan koefisien ekonomi tertentu volume bebas (nilai koefisien selalu> 1) (lihat bagian menyiapkan data input).

Setelah analogi dengan pengiriman klasik yang terkenal dari masalah telah ditarik, perlu untuk menjawab pertanyaan penting di mana pilihan arsitektur algoritma solusi tergantung: perpindahan residu dari sel donor hanya mungkin dalam satu dan hanya satu wadah (Sumber Tunggal), atau perpindahan residu dimungkinkan. ke dalam beberapa sel kontainer (Multi-Source)?

Perlu dicatat bahwa dalam praktiknya kedua rumusan masalah memiliki tempatnya. Kami memberikan semua pro dan kontra untuk setiap pernyataan di bawah ini:
Tabel 1. Pro dan kontra dari opsi Single-Source dan Multi-Source.

Karena jumlah plus untuk opsi Sumber-Tunggal lebih besar, dan juga memperhitungkan fakta bahwa semakin kecil jumlah residu dalam sel donor, semakin kecil perbedaan dalam tingkat kekompakan kompresi yang dihitung untuk kedua versi masalah, pilihannya jatuh pada Single- Sumber

Perlu dikatakan bahwa solusi dari opsi Multi-Source juga terjadi. Ada sejumlah besar algoritma yang efektif untuk menyelesaikannya, yang sebagian besar bermuara pada penyelesaian sejumlah masalah transportasi. Ada juga tidak hanya algoritma yang efisien, tetapi juga yang elegan, misalnya, di sini.

Persiapan input

Sebelum melanjutkan ke analisis dan pengembangan suatu algoritma untuk memecahkan masalah, perlu untuk menentukan data apa dan dalam bentuk apa kita akan mengirimkannya ke input. Tidak ada masalah dengan volume barang yang tersisa di sel donor dan kapasitas sel kontainer, karena ini sepele - nilai-nilai seperti itu akan diukur dalam m3, tetapi dengan biaya menggunakan wadah kontainer dan biaya memindahkan matriks, itu tidak begitu sederhana!

Pertama, kami mempertimbangkan perhitungan biaya memindahkan barang dari sel donor ke sel wadah. Pertama-tama, perlu untuk menentukan dalam unit pengukuran apa kita akan menghitung biaya pemindahan. Dua opsi yang paling jelas adalah meter dan detik. Dalam meter "bersih", biaya bergerak tidak ada gunanya. Kami menunjukkan ini dengan contoh. Biarkan sel $$$A$ terletak di tingkat pertama, sel $$$Ke$ dihapus 30 meter dan terletak di tingkat kedua:

• Pindah keluar $$$A$ masuk $$$B$ lebih mahal daripada pindah dari $$$B$ masuk $$$A$ , karena menurunkan turun dari tingkat kedua (1,5-2 meter dari lantai) lebih mudah daripada menaikkannya ke tingkat kedua, meskipun jaraknya akan sama;
• Pindahkan 1 pc. barang dari sel $$$A$ masuk $$$B$ Ini akan lebih mudah daripada memindahkan 10 pcs. dari produk yang sama, meskipun jaraknya akan sama.

Biaya pergerakan sebaiknya diperhitungkan dalam hitungan detik, karena ini memungkinkan Anda untuk memperhitungkan perbedaan tingkatan dan perbedaan jumlah barang yang diangkut. Untuk memperhitungkan biaya perpindahan dalam hitungan detik, kita harus menguraikan operasi pemindahan ke komponen dasar dan melakukan pengukuran waktu untuk setiap komponen dasar.

Biarkan dari sel $$$j$ bergerak $$$N_j$ pcs barang ke wadah $$$i$ . Biarkan $$$S_ {run}$ - kecepatan rata-rata karyawan di gudang, diukur dalam m / s. Biarkan $$$S_ {get}$ dan $$$S_ {put}$ - kecepatan rata-rata dari satu eksekusi operasi untuk mengambil dan menempatkan, masing-masing, untuk volume barang yang sama dengan 4 dm3 (volume rata-rata yang dibutuhkan seorang karyawan di gudang untuk 1 kali selama operasi). Biarkan $$$H_ {get}$ dan $$$H_ {put}$ ketinggian sel tempat operasi dilakukan mengambil dan menempatkan sesuai. Misalnya, ketinggian rata-rata tingkat pertama (lantai) adalah 1 m, tingkat kedua adalah 2 m, dll. Kemudian rumus untuk menghitung total waktu untuk menyelesaikan operasi pemindahan $$$T_ {ij}$ berikut ini:

$$

$$T_ {ij} = \ kiri (N_ {j} \ cdot \ frac {w_ {j}} {4} \ kanan) \ cdot S_ {get} \ cdot H_ {get} + s_ {ij} \ cdot S_ { jalankan} + \ kiri (N_ {j} \ cdot \ frac {w_ {j}} {4} \ kanan) \ cdot S_ {put} \ cdot H_ {put}.$$

Tabel 2 menunjukkan statistik waktu pelaksanaan setiap operasi dasar, dikumpulkan oleh staf gudang, dengan mempertimbangkan spesifik barang yang disimpan.
Tabel 2. Rata-rata waktu untuk melakukan operasi gudang

Dengan metode penghitungan biaya pemindahan diputuskan. Sekarang Anda perlu mencari cara menghitung biaya memilih sel kontainer . Di sini, semuanya jauh, jauh lebih rumit daripada dengan biaya bergerak, karena:

• pertama, biayanya harus secara langsung bergantung pada volume sel - lebih baik untuk menempatkan volume residu yang sama yang ditransfer dari sel donor ke dalam wadah dengan volume lebih kecil daripada ke dalam wadah besar, asalkan volume tersebut cocok sepenuhnya di kedua wadah . Dengan demikian, dengan meminimalkan biaya total memilih wadah, kami berupaya untuk menghemat kapasitas penyimpanan gratis “langka” di area zona pemilihan untuk melakukan operasi selanjutnya dengan menempatkan barang dalam sel. Gambar 4 menunjukkan opsi untuk memindahkan residu ke wadah besar dan kecil dan konsekuensi dari opsi tersebut untuk bergerak selama operasi gudang berikutnya.
• kedua, karena kita perlu meminimalkan total biaya dalam menyelesaikan masalah awal, dan ini adalah jumlah dari biaya bergerak dan biaya memilih kontainer, volume sel dalam meter kubik entah bagaimana harus dihubungkan dengan detik, yang jauh dari sepele.

Fig. 4. Opsi untuk memindahkan residu ke dalam wadah dengan kapasitas berbeda.

Gambar 4 menunjukkan warna merah volume residu yang tidak lagi sesuai dalam wadah pada tahap kedua penempatan barang berikutnya.

Persyaratan berikut untuk solusi terhitung untuk masalah ini akan membantu menghubungkan meter kubik biaya kontainer dengan detik-detik biaya transportasi:

• Adalah penting bahwa residu dari sel donor dipindahkan ke sel wadah dalam hal apa pun, jika hal ini mengurangi jumlah total sel wadah di mana barang berada.
• Penting untuk mencapai keseimbangan antara volume kontainer dan waktu yang dihabiskan untuk bergerak: misalnya, jika solusi baru untuk masalah tersebut dibandingkan dengan perolehan volume yang besar dan waktu yang hilang kecil, maka Anda harus memilih yang baru.

Mari kita mulai dengan persyaratan terakhir. Untuk menentukan kata ambigu "keseimbangan", kami melakukan survei terhadap karyawan gudang untuk mengetahui hal berikut. Biarkan ada volume wadah sel$$d 0 , di mana pergerakan sisa-sisa barang dari sel donor ditugaskan dan total waktu pergerakan tersebut$d_0$$$$T_0$ . Misalkan ada beberapa opsi alternatif untuk menempatkan jumlah barang yang sama dari sel donor yang sama di wadah lain, di mana setiap penempatan memiliki peringkat sendiri $$$d_1$ dimana $$d 1 <$d_1$$$$d_0$ dan $$$T_1$ dimana $$T 1 >$T_1$$$$T_0$ .

Pertanyaannya adalah: berapa gain minimum dalam volume $$d 0 - d 1 dapat diterima, untuk nilai kerugian waktu tertentu$d_0-d_1$$$$T_1-T_0$ ?Mari kita ilustrasikan dengan sebuah contoh. Awalnya, residu seharusnya ditempatkan dalam wadah volume 1000 dm3 (1 m3) dan waktu tempuh adalah 70 detik. Ada opsi untuk menempatkan residu dalam wadah lain 500 dm3 dan waktu 130 detik. Pertanyaan: apakah kita siap untuk menghabiskan 60 detik tambahan waktu dari pemilik toko untuk berpindah guna menghemat 500 dm3 volume gratis? Berdasarkan survei terhadap karyawan gudang, bagan berikut disusun.


Fig. 5. Diagram ketergantungan penghematan volume minimum yang diijinkan pada peningkatan perbedaan waktu operasi

, yaitu, jika biaya waktu tambahan adalah 40 detik, maka kami siap untuk menghabiskannya hanya ketika keuntungan dalam volume setidaknya 500 dm3. Terlepas dari kenyataan bahwa sedikit nonlinearitas diamati dalam ketergantungan, untuk kesederhanaan perhitungan lebih lanjut, kami mengasumsikan bahwa ketergantungan antara jumlah adalah linier dan dijelaskan oleh ketidaksetaraan

$$

$$\frac{d_{0}-d_{1}}{10} \geq T_{1}-T_{0}$$

Pada gambar di bawah ini, kami mempertimbangkan metode penempatan barang dalam wadah berikut.


Fig. 6. Opsi (a): 2 kontainer, volume total 400 dm3, total waktu 150 detik.

. 6. (b): 2 , 600 3, 190 .

Fig. 6. Opsi: 1 kontainer, volume total 400 dm3, total waktu 200 detik.

Opsi (a) dari pilihan wadah lebih disukai daripada opsi awal, karena ketidaksetaraan berlaku: (800-400) / 10> = 150-120, yang menyiratkan 40> = 30. Opsi (b) kurang disukai daripada opsi asli , karena ketidaksetaraan tidak berlaku: (800-600) / 10> = 190-150, yang menyiratkan 20> = 40. Tetapi opsi (c) tidak cocok dengan logika ini! Pertimbangkan opsi ini secara lebih rinci. Di satu sisi, ketimpangan (800-400) / 10> = 200-120, yang berarti bahwa ketimpangan 40> = 80 tidak terpenuhi, yang menunjukkan bahwa kenaikan volume tidak sebanding dengan kerugian besar dalam waktu.

Tetapi di sisi lain, dalam opsi ini (c), kami tidak hanya mengurangi total volume yang ditempati, tetapi juga mengurangi jumlah sel yang ditempati, yang merupakan yang pertama dari dua persyaratan penting untuk solusi terhitung untuk masalah yang tercantum di atas. Jelas, agar persyaratan ini mulai terpenuhi, perlu untuk menambahkan beberapa konstanta positif ke sisi kiri ketidaksetaraan $$$Const$ , dan konstanta seperti itu perlu ditambahkan hanya ketika jumlah kontainer berkurang. Ingat itu $$$y_i$ Apakah variabel sama dengan 1 saat wadah $$$i$ dipilih, dan 0 saat wadah $$$i$ tidak dipilih. Dilambangkan $$$I_0$ - banyak wadah dalam larutan asli dan $$$I_1$ - Banyak wadah dalam solusi baru. Secara umum, ketidaksetaraan baru akan terlihat seperti ini:

$$

$$\ jumlah _ {i \ dalam I_ {0}} ^ {} \ frac {d_ {i}} {10} + Const \ cdot \ jumlah _ {i \ di I_ {0}} ^ {} y_ {i} - \ kiri (\ jumlah _ {i \ di I_ {1}} ^ {} \ frac {d_ {i}} {10} + Const \ cdot \ sum _ {i \ di I_ {1}} ^ {} y_ {i} \ kanan) \ geq T_ {1} -T_ {0}$$

Mengubah ketidaksetaraan di atas, kita dapatkan

$$

$$\ jumlah _ {i \ dalam I_ {0}} ^ {} \ frac {d_ {i}} {10} + Const \ cdot \ jumlah _ {i \ di I_ {0}} ^ {} y_ {i} + T_ {0} \ geq \ jumlah _ {i \ di I_ {1}} ^ {} \ frac {d_ {i}} {10} + Const \ cdot \ sum _ {i \ di I_ {1}} ^ {} y_ {i} + T_ {1}$$

Berdasarkan ini, kami memiliki formula untuk menghitung total biaya $$$F_k$ beberapa solusi untuk masalah ini:

$$

$$F_ {k} = \ jumlah _ {i \ di I_ {k}} ^ {} \ frac {d_ {i}} {10} + Const \ cdot \ sum _ {i \ dalam I_ {k}} ^ { } y_ {i} + T_ {k}.$$

Tetapi sekarang muncul pertanyaan : nilai apa yang harus dimiliki oleh konstanta seperti itu? $$$Const$ ? Jelas, nilainya harus cukup besar sehingga persyaratan pertama untuk penyelesaian masalah selalu terpenuhi. Anda tentu saja dapat mengambil nilai konstan sama dengan 10 ³ atau 10 ⁶ , tetapi saya ingin menghindari "angka ajaib" tersebut. Jika kita mempertimbangkan secara spesifik melakukan operasi gudang, kita dapat menghitung beberapa perkiraan numerik yang kuat tentang besarnya konstanta tersebut.

Biarkan $$$S_ {maks}$ - jarak maksimum antara sel-sel gudang satu zona ABC, sama dalam kasus kami hingga 100 m $$$d_ {maks}$ - volume maksimum wadah sel di gudang, sama dalam kasus kami dengan 1000 dm3.

Cara pertama menghitung nilai $$$Const$ . Pertimbangkan situasi ketika ada 2 kontainer di tingkat pertama di mana barang sudah secara fisik terletak, yaitu, mereka sendiri adalah sel donor, dan biaya memindahkan barang ke sel yang sama secara alami adalah 0. Perlu untuk menemukan nilai konstan seperti itu $$$Const$ di mana akan menguntungkan untuk selalu memindahkan residu dari wadah 1 ke wadah 2. Mengganti nilai $$$S_ {maks}$ dan $$$d_ {maks}$ ke dalam ketidaksetaraan di atas, kita memperoleh:

$$

$$\ frac {d_ {max}} {10} + Const \ geq S_ {max} \ cdot s_ {run} + \ frac {d_ {max}} {4} \ kiri (s_ {get} + s_ {put} \ benar),$$

berikut apa

$$

$$Const \ geq S_ {max} \ cdot s_ {run} + d_ {max} \ kiri (\ frac {s_ {get} + s_ {put}} {4} - \ frac {1} {10} \ kanan) .$$

Mengganti nilai waktu eksekusi rata-rata operasi dasar dalam rumus di atas, kami dapatkan

$$

$$Const \ geq 100 \ cdot 1.5 + 1000 \ kiri (\ frac {9} {10} \ kanan) \ rightarrow Const \ geq 1050.$$

Cara kedua untuk menghitung nilai $$$Const$ . Pertimbangkan situasi di mana ada $$$N$ sel donor yang darinya direncanakan untuk memindahkan barang ke dalam wadah 1. Ditunjukkan $$$S_ {1j}$ - jarak dari sel donor $$$j$ ke wadah 1. Ada juga wadah 2, di mana sudah ada barang, dan volume yang memungkinkan Anda untuk menampung sisanya $$$N$ sel. Untuk kesederhanaan, kami akan menganggap bahwa volume barang yang diangkut dari sel donor ke wadah adalah sama dan sama $$$d_ {max} / N$ . Diperlukan untuk menemukan nilai yang konstan $$$Const$ di mana penempatan semua residu dari $$$N$ sel dalam wadah 2 akan selalu lebih menguntungkan daripada menempatkannya dalam wadah yang berbeda:

$$

$$2 \ cdot \ frac {d_ {max}} {10} +2 \ cdot Const + N \ kiri (S_ {1j} \ cdot s_ {run} + \ frac {d_ {max}} {4 \ cdot N} \ kiri (s_ {get} + s_ {put} \ kanan) \ kanan) \ geq \ qquad \ qquad \ qquad \ qquad \ qquad \ qquad \ qquad \ qquad \ qquad \ qquad \ qquad \ qquad \ qquad \ frac {d_ {max}} { 10} + Konst + N \ cdot \ kiri (S_ {max} \ cdot s_ {run} + \ frac {d_ {max}} {4 \ cdot N} \ kiri (s_ {get} + s_ {put} \ kanan ) \ benar).$$

Mengubah ketimpangan yang kita dapatkan

$$

$$\ frac {d_ {max}} {10} + Const + N \ cdot S_ {1j} \ cdot s_ {run} \ geq N \ cdot S_ {max} \ cdot s_ {run} \ rightarrow Const \ geq N \ cdot s_ {run} \ kiri (S_ {max} -S_ {1j} \ kanan) - \ frac {d_ {max}} {10}.$$

Untuk "memperkuat" nilai kuantitas $$$Const$ , kami menganggap itu $$$S_ {1j}$ = 0. Jumlah rata-rata sel yang biasanya terlibat dalam proses mengompresi saldo stok adalah 10. Mengganti nilai kuantitas yang diketahui, kita memiliki nilai konstan berikut

$$

$$Const \ geq 10 \ cdot 1.5 \ cdot 100- \ frac {1000} {10} \ rightarrow Const \ geq 1400.$$

Kami mengambil nilai terbesar yang dihitung untuk setiap opsi, ini akan menjadi nilai $$$Const$ untuk parameter gudang yang diberikan. Sekarang untuk kelengkapan, kami menulis rumus untuk menghitung biaya total $$$F_k$ untuk beberapa solusi yang layak $$$k$ :

$$

$$F_ {k} = \ jumlah _ {i \ di I_ {k}} ^ {} \ frac {d_ {i}} {10} +1400 \ cdot \ sum _ {i \ di I_ {k}} ^ { } y_ {i} + T_ {k}.$$

Sekarang, setelah semua upaya besar untuk mengkonversi data input, kita dapat mengatakan bahwa semua data input dikonversi ke bentuk yang diinginkan dan siap digunakan dalam algoritma optimasi.

Kesimpulan

Seperti yang diperlihatkan oleh praktik, kompleksitas dan pentingnya persiapan dan konversi data input untuk algoritma sering dianggap remeh. Dalam artikel ini, kami secara khusus menaruh banyak perhatian pada tahap ini untuk menunjukkan bahwa hanya data input yang disiapkan secara kualitatif dan bijak yang dapat membuat keputusan yang dihitung oleh algoritma benar-benar berharga bagi klien. Ya, ada banyak kesimpulan dari formula, tetapi kami memperingatkan Anda sebelum kat :)

Pada artikel berikutnya, kita akhirnya akan sampai pada apa yang dipikirkan oleh 2 publikasi sebelumnya - algoritma optimasi diskrit.

Mempersiapkan artikel
Roman Shangin, Programmer, Departemen Proyek,
Perusahaan Bit Pertama, Chelyabinsk