Artikel ini menjelaskan cara menerapkannya WMS-sistem, kami dihadapkan pada kebutuhan untuk memecahkan masalah pengelompokan non-standar dan algoritma apa yang kami gunakan untuk menyelesaikannya. Kami akan memberi tahu Anda bagaimana kami menerapkan pendekatan ilmiah dan sistematis dalam memecahkan masalah, kesulitan apa yang kami temui, dan pelajaran apa yang kami peroleh.
Publikasi ini memulai serangkaian artikel di mana kami berbagi pengalaman sukses kami dalam menerapkan algoritma optimasi dalam proses gudang. Tujuan dari rangkaian artikel ini adalah untuk memperkenalkan kepada audiens jenis-jenis masalah optimasi operasi gudang yang muncul di hampir semua gudang menengah dan besar, serta untuk menceritakan pengalaman kami dalam memecahkan masalah tersebut dan kendala yang dihadapi selama proses tersebut. . Artikel-artikel ini akan bermanfaat bagi mereka yang bekerja di industri logistik gudang, terapkan WMS-sistem, serta pemrogram yang tertarik pada penerapan matematika dalam bisnis dan optimalisasi proses dalam suatu perusahaan.
Kemacetan dalam proses
Pada tahun 2018, kami menyelesaikan proyek untuk dilaksanakan WMS-sistem di gudang perusahaan βTrading House βLDβ di Chelyabinsk. Kami menerapkan produk β1C-Logistics: Warehouse Management 3β untuk 20 tempat kerja: operator WMS, pemilik toko, pengemudi forklift. Luas gudang rata-rata sekitar 4 ribu m2, jumlah sel 5000 dan jumlah SKU 4500. Gudang tersebut menyimpan ball valve produksi kami sendiri dengan berbagai ukuran mulai dari 1 kg hingga 400 kg. Persediaan di gudang disimpan secara batch, karena perlu dilakukan pemilihan barang sesuai FIFO.
Saat merancang skema otomatisasi proses gudang, kami dihadapkan pada masalah penyimpanan inventaris yang tidak optimal. Kekhususan penyimpanan dan penyimpanan crane sedemikian rupa sehingga satu unit sel penyimpanan hanya dapat menampung barang-barang dari satu batch. Produk tiba di gudang setiap hari dan setiap kedatangan merupakan batch terpisah. Secara total, sebagai hasil dari 1 bulan pengoperasian gudang, 30 batch terpisah dibuat, meskipun masing-masing batch harus disimpan dalam sel terpisah. Produk seringkali dipilih tidak dalam palet utuh, tetapi dalam potongan, dan sebagai hasilnya, di zona pemilihan potongan di banyak sel, gambar berikut diamati: dalam sel dengan volume lebih dari 1 m3 ada beberapa potongan crane yang menempati kurang dari 5-10% volume sel.
Gambar 1. Foto beberapa barang dalam satu sel
Jelas kapasitas penyimpanan tidak digunakan secara maksimal. Untuk membayangkan skala bencana, saya dapat memberikan angka: rata-rata, terdapat 1 hingga 3 sel dengan volume lebih dari 100 m300 dengan saldo βsangat kecilβ selama berbagai periode pengoperasian gudang. Karena ukuran gudang relatif kecil, selama musim sibuk gudang, faktor ini menjadi βhambatanβ dan sangat memperlambat proses gudang.
Ide solusi masalah
Timbul gagasan: kumpulan sisa makanan dengan tanggal terdekat harus dikurangi menjadi satu kumpulan tunggal, dan sisa makanan tersebut dengan kumpulan terpadu harus ditempatkan secara kompak dalam satu sel, atau dalam beberapa sel, jika tidak ada cukup ruang dalam satu sel untuk menampungnya. seluruh jumlah sisa.
Gambar.2. Skema untuk mengompresi residu dalam sel
Hal ini memungkinkan Anda mengurangi secara signifikan ruang gudang yang ditempati yang akan digunakan untuk penempatan barang baru. Dalam situasi di mana kapasitas gudang kelebihan beban, tindakan seperti itu sangat diperlukan, jika tidak, mungkin tidak ada cukup ruang kosong untuk menampung barang baru, yang akan menyebabkan terhentinya proses penempatan dan pengisian gudang. Sebelumnya sebelum implementasi WMS-sistem melakukan operasi ini secara manual, yang tidak efektif, karena proses pencarian residu yang sesuai di dalam sel cukup lama. Kini, dengan diperkenalkannya sistem WMS, kami memutuskan untuk mengotomatiskan proses, mempercepatnya, dan menjadikannya cerdas.
Proses penyelesaian masalah tersebut dibagi menjadi 2 tahap:
- pada tahap pertama kami menemukan kelompok batch yang tanggal kompresinya hampir sama;
- pada tahap kedua, untuk setiap kelompok batch kami menghitung penempatan sisa barang yang paling kompak di dalam sel.
Pada artikel kali ini kami akan fokus pada algoritma tahap pertama, dan meninggalkan liputan tahap kedua untuk artikel berikutnya.
Cari model matematika dari masalahnya
Sebelum kami duduk untuk menulis kode dan menemukan kembali roda kami, kami memutuskan untuk mendekati masalah ini secara ilmiah, yaitu: merumuskannya secara matematis, mereduksinya menjadi masalah optimasi diskrit yang terkenal dan menggunakan algoritma efektif yang ada untuk menyelesaikannya, atau mengambil algoritma yang ada ini. sebagai dasar dan memodifikasinya sesuai dengan masalah praktis yang sedang dipecahkan.
Karena rumusan masalah yang kita hadapi dengan himpunan jelas mengikuti rumusan bisnis, maka kita akan merumuskan masalah tersebut dalam istilah teori himpunan.
Biarkan β himpunan semua batch sisa produk tertentu di gudang. Membiarkan β diberikan jumlah hari yang konstan. Membiarkan β subset dari batch, dimana perbedaan tanggal untuk semua pasangan batch dalam subset tersebut tidak melebihi suatu konstanta . Kita perlu mencari jumlah minimum himpunan bagian yang saling lepas , sehingga semua himpunan bagian jika digabungkan akan memberi banyak .
Dengan kata lain, kita perlu mencari kelompok atau cluster dari pihak-pihak yang sejenis, dimana kriteria kemiripannya ditentukan oleh konstanta . Tugas ini mengingatkan kita pada masalah pengelompokan yang terkenal. Penting untuk mengatakan bahwa masalah yang sedang dipertimbangkan berbeda dari masalah pengelompokan karena masalah kita memiliki kondisi yang ditentukan secara ketat untuk kriteria kesamaan elemen cluster, yang ditentukan oleh konstanta , namun pada masalah clustering tidak ada kondisi seperti itu. Pernyataan masalah clustering dan informasi mengenai masalah ini dapat ditemukan
Jadi, kami berhasil merumuskan masalah dan menemukan masalah klasik dengan rumusan serupa. Sekarang kita perlu mempertimbangkan algoritme terkenal untuk menyelesaikannya, agar tidak menemukan kembali roda, tetapi mengambil praktik terbaik dan menerapkannya. Untuk mengatasi masalah clustering, kami mempertimbangkan algoritma yang paling populer, yaitu: -cara -berarti, algoritma untuk mengidentifikasi komponen yang terhubung, algoritma pohon rentang minimum. Deskripsi dan analisis algoritma tersebut dapat ditemukan
Untuk mengatasi masalah kita, algoritma pengelompokan -berarti dan -Means tidak berlaku sama sekali, karena jumlah cluster tidak pernah diketahui sebelumnya dan algoritme semacam itu tidak memperhitungkan batasan hari yang konstan. Algoritme seperti itu pada awalnya dibuang dari pertimbangan.
Untuk mengatasi masalah kita, algoritma untuk mengidentifikasi komponen yang terhubung dan algoritma pohon merentang minimum lebih cocok, tetapi ternyata, keduanya tidak dapat diterapkan secara βlangsungβ pada masalah yang sedang dipecahkan dan memperoleh solusi yang baik. Untuk menjelaskan hal ini, mari kita pertimbangkan logika pengoperasian algoritma tersebut dalam kaitannya dengan masalah kita.
Perhatikan grafiknya , yang simpulnya adalah himpunan para pihak , dan tepi di antara simpul ΠΈ mempunyai bobot yang sama dengan selisih hari antar batch ΠΈ . Dalam algoritma untuk mengidentifikasi komponen yang terhubung, parameter input ditentukan Dimana , dan dalam grafik semua tepi yang bobotnya lebih besar dihilangkan . Hanya pasangan benda terdekat yang tetap terhubung. Inti dari algoritma ini adalah untuk memilih nilai tersebut , di mana grafik βterpecahβ menjadi beberapa komponen yang terhubung, di mana pihak-pihak yang termasuk dalam komponen ini akan memenuhi kriteria kesamaan kita, yang ditentukan oleh konstanta . Komponen yang dihasilkan adalah cluster.
Algoritme pohon rentang minimum pertama-tama dibuat berdasarkan grafik pohon rentang minimum, dan kemudian secara berurutan menghilangkan sisi-sisi dengan bobot tertinggi hingga grafik βterpecahβ menjadi beberapa komponen yang terhubung, di mana pihak-pihak yang termasuk dalam komponen tersebut juga akan memenuhi kriteria kesamaan kita. Komponen yang dihasilkan akan menjadi cluster.
Saat menggunakan algoritma tersebut untuk memecahkan masalah yang sedang dipertimbangkan, situasi seperti pada Gambar 3 mungkin muncul.
Gambar 3. Penerapan algoritma clustering pada permasalahan yang sedang dipecahkan
Katakanlah konstanta kita untuk perbedaan antara hari batch adalah 20 hari. Grafik digambarkan dalam bentuk spasial untuk memudahkan persepsi visual. Kedua algoritma menghasilkan solusi 3-cluster, yang dapat dengan mudah ditingkatkan dengan menggabungkan batch yang ditempatkan di cluster terpisah satu sama lain! Jelas bahwa algoritma seperti itu perlu dimodifikasi agar sesuai dengan spesifikasi masalah yang sedang dipecahkan, dan penerapannya dalam bentuk murni untuk memecahkan masalah kita akan memberikan hasil yang buruk.
Jadi, sebelum kami mulai menulis kode untuk algoritme grafik yang dimodifikasi untuk tugas kami dan menciptakan kembali sepeda kami sendiri (yang siluetnya sudah dapat kami lihat garis besar roda persegi), kami sekali lagi memutuskan untuk mendekati masalah tersebut secara ilmiah, yaitu: cobalah untuk mereduksinya ke optimasi masalah diskrit lainnya, dengan harapan algoritma penyelesaiannya yang ada dapat diterapkan tanpa modifikasi.
Pencarian lain untuk masalah klasik serupa telah berhasil! Kami berhasil menemukan masalah optimasi diskrit, yang rumusannya bertepatan 1 in 1 dengan rumusan masalah kami. Tugas ini ternyata berhasil mengatur masalah penutup. Mari kita sajikan rumusan masalah dalam kaitannya dengan kekhususan kita.
Ada himpunan yang terbatas dan keluarga dari semua himpunan bagian yang terpisah, sehingga perbedaan tanggal untuk semua pasangan pihak dari setiap himpunan bagian dari keluarga tidak melebihi konstanta . Penutup disebut keluarga dengan kekuatan yang paling kecil, yang unsur-unsurnya termasuk , sedemikian rupa sehingga gabungan himpunan dari keluarga harus memberikan himpunan semua pihak .
Analisis rinci tentang masalah ini dapat ditemukan ΠΈ Pilihan lain untuk penerapan praktis dari masalah penutup dan modifikasinya dapat ditemukan
Algoritma untuk memecahkan masalah
Kami telah memutuskan model matematika dari masalah yang akan diselesaikan. Sekarang mari kita lihat algoritma untuk menyelesaikannya. Subset dari keluarga dapat dengan mudah ditemukan dengan prosedur berikut.
- Susun batch dari satu set dalam urutan tanggalnya.
- Temukan tanggal batch minimum dan maksimum.
- Untuk setiap hari dari tanggal minimum hingga maksimum, temukan semua batch yang tanggalnya berbeda tidak lebih dari (jadi nilainya Lebih baik mengambil bilangan genap).
Logika tata cara pembentukan suatu keluarga himpunan di hari disajikan pada Gambar 4.
Gambar.4. Pembentukan subkelompok partai
Prosedur ini tidak diperlukan untuk semua orang periksa semua batch lainnya dan periksa perbedaan tanggalnya, atau dari nilai saat ini gerakkan ke kiri atau ke kanan hingga Anda menemukan kumpulan yang tanggalnya berbeda lebih dari setengah nilai konstanta. Semua elemen berikutnya, ketika dipindahkan ke kanan dan ke kiri, tidak akan menarik bagi kami, karena bagi mereka perbedaan hari hanya akan bertambah, karena elemen-elemen dalam array pada awalnya diurutkan. Pendekatan ini akan menghemat waktu secara signifikan ketika jumlah pesta dan penyebaran tanggalnya sangat banyak.
Masalah penutup himpunan adalah -sulit, artinya tidak ada algoritma yang cepat (dengan waktu operasi sama dengan polinomial data masukan) dan akurat untuk menyelesaikannya. Oleh karena itu, untuk menyelesaikan masalah himpunan cakupan, dipilih algoritma fast serakah, yang tentu saja tidak akurat, tetapi memiliki keuntungan sebagai berikut:
- Untuk masalah berukuran kecil (dan inilah kasus kami), ini menghitung solusi yang mendekati optimal. Ketika ukuran masalah bertambah, kualitas solusi pun menurun, namun masih cukup lambat;
- Sangat mudah diterapkan;
- Cepat, karena perkiraan waktu berjalannya .
Algoritme serakah memilih himpunan berdasarkan aturan berikut: pada setiap tahap, himpunan dipilih yang mencakup jumlah maksimum elemen yang belum tercakup. Penjelasan rinci tentang algoritma dan pseudocode-nya dapat ditemukan
Perbandingan keakuratan algoritma serakah tersebut pada data uji masalah yang sedang diselesaikan dengan algoritma lain yang diketahui, seperti algoritma serakah probabilistik, algoritma koloni semut, dll., belum dilakukan. Hasil perbandingan algoritma tersebut pada data acak yang dihasilkan dapat ditemukan
Implementasi dan implementasi algoritma
Algoritma ini diimplementasikan dalam bahasa tersebut 1S dan dimasukkan dalam pemrosesan eksternal yang disebut "Kompresi Residu" yang terhubung dengannya WMS-sistem. Kami tidak mengimplementasikan algoritme dalam bahasa tersebut C ++ dan menggunakannya dari komponen Asli eksternal, yang akan lebih tepat, karena kecepatan kodenya lebih rendah C + + kali dan dalam beberapa contoh bahkan puluhan kali lebih cepat daripada kecepatan kode serupa 1S. Di lidah 1S Algoritma ini diterapkan untuk menghemat waktu pengembangan dan kemudahan debugging di basis produksi pelanggan. Hasil algoritma disajikan pada Gambar 5.
Gambar.5. Pemrosesan untuk βmengompresiβ residu
Gambar 5 menunjukkan bahwa di gudang tertentu, saldo barang saat ini di sel penyimpanan dibagi menjadi beberapa kelompok, di mana tanggal batch barang berbeda satu sama lain tidak lebih dari 30 hari. Karena pelanggan memproduksi dan menyimpan katup bola logam di gudang, yang umur simpannya dihitung dalam beberapa tahun, perbedaan tanggal tersebut dapat diabaikan. Perhatikan bahwa pemrosesan tersebut saat ini digunakan secara sistematis dalam produksi, dan operator WMS mengkonfirmasi kualitas pengelompokan partai yang baik.
Kesimpulan dan kelanjutan
Pengalaman utama yang kami peroleh dari penyelesaian masalah praktis tersebut adalah penegasan efektivitas penggunaan paradigma: matematika. pernyataan masalah tikar terkenal. model algoritma terkenal algoritma dengan mempertimbangkan spesifik masalah. Optimalisasi diskrit telah ada selama lebih dari 300 tahun, dan selama ini orang telah berhasil mempertimbangkan banyak masalah dan mengumpulkan banyak pengalaman dalam menyelesaikannya. Pertama-tama, lebih disarankan untuk beralih ke pengalaman ini, dan baru kemudian mulai menemukan kembali roda Anda.
Pada artikel berikutnya kita akan melanjutkan cerita tentang algoritma optimasi dan melihat yang paling menarik dan jauh lebih kompleks: sebuah algoritma untuk βkompresiβ residu sel yang optimal, yang menggunakan data yang diterima dari algoritma pengelompokan batch sebagai masukan.
Mempersiapkan artikelnya
Roman Shangin, programmer departemen proyek,
Perusahaan BIT pertama, Chelyabinsk
Sumber: www.habr.com