Artikel nerangake carane ngleksanakake WMS-sistem, kita padha ngadhepi karo perlu kanggo ngatasi masalah clustering non-standar lan apa algoritma kita digunakake kanggo ngatasi. Kita bakal ngandhani kepiye carane ngetrapake pendekatan ilmiah sing sistematis kanggo ngrampungake masalah kasebut, kesulitan apa sing kita temoni lan pelajaran apa sing kita sinau.
Publikasi iki miwiti seri artikel sing nuduhake pengalaman sukses ing implementasi algoritma optimasi ing proses gudang. Tujuan saka seri artikel kasebut yaiku kanggo ngerteni para pamirsa babagan jinis masalah optimasi operasi gudang sing muncul ing meh kabeh gudang medium lan gedhe, uga nyritakake pengalaman kita kanggo ngrampungake masalah kasebut lan pitfalls sing ditemoni ing dalan. . Artikel bakal migunani kanggo sing makarya ing industri logistik gudang, ngleksanakake WMS-sistem, uga programer sing kasengsem ing aplikasi matématika ing bisnis lan optimalisasi pangolahan ing perusahaan.
Bottleneck ing proses
Ing 2018, kita ngrampungake proyek sing bakal ditindakake WMS-sistem ing gudang perusahaan "Trading House "LD" ing Chelyabinsk. Kita ngetrapake produk "1C-Logistik: Manajemen Gudang 3" kanggo 20 papan kerja: operator WMS, storekeepers, driver forklift. Gudang rata-rata udakara 4 ewu m2, jumlah sel 5000 lan jumlah SKU 4500. Gudang nyimpen katup bal saka produksi kita dhewe kanthi ukuran sing beda-beda saka 1 kg nganti 400 kg. Persediaan ing gudang disimpen ing batch, amarga ana perlu kanggo milih barang miturut FIFO.
Nalika ngrancang skema otomatisasi proses gudang, kita ngadhepi masalah panyimpenan persediaan sing ora optimal. Spesifik kanggo nyimpen lan stowing crane kaya sing siji sel panyimpenan unit mung bisa ngemot item saka siji kumpulan. Produk teka ing gudang saben dina lan saben rawuh minangka kumpulan sing kapisah. Secara total, minangka asil saka operasi gudang 1 wulan, 30 batch kapisah digawe, sanajan saben kudu disimpen ing sel sing kapisah. Produk asring dipilih ora ing kabeh palet, nanging kanthi potongan, lan minangka asil, ing zona pilihan potongan ing pirang-pirang sel, gambar ing ngisor iki diamati: ing sel kanthi volume luwih saka 1 m3 ana sawetara potongan crane sing ngenggoni kurang saka 5-10% saka volume sel.
Gambar 1. Foto sawetara potongan barang ing sel
Cetha yen kapasitas panyimpenan ora digunakake kanthi optimal. Kanggo mbayangno skala bencana, aku bisa menehi angka: rata-rata, ana 1 nganti 3 sel sel kasebut kanthi volume luwih saka 100 m300 kanthi saldo "minuscule" sajrone periode operasi gudang sing beda-beda. Wiwit gudang relatif cilik, ing mangsa sibuk gudang faktor iki dadi "bottleneck" lan banget slows mudhun proses gudang.
Gagasan solusi masalah
Ide muncul: tumpukan sisa kanthi tanggal sing paling cedhak kudu dikurangi dadi siji batch, lan turahan kasebut kanthi kumpulan sing manunggal kudu dilebokake kanthi kompak ing siji sel, utawa ing sawetara, yen ora cukup ruang ing siji kanggo nampung kabeh jumlah sisa.
Gbr.2. Skema kanggo ngompres residu ing sel
Iki ngidini sampeyan nyuda ruang gudang sing dikuwasani sing bakal digunakake kanggo barang anyar sing diselehake. Ing kahanan ing ngendi kapasitas gudang kakehan, ukuran kasebut pancen perlu, yen ora ana cukup ruang kosong kanggo nampung barang anyar, sing bakal mandheg ing proses penempatan lan replenishment gudang. Sadurunge sadurunge implementasine WMS-sistem nindakake operasi iki kanthi manual, sing ora efektif, amarga proses nggoleki residu sing cocog ing sel kasebut cukup suwe. Saiki, kanthi introduksi sistem WMS, kita mutusake kanggo ngotomatisasi proses kasebut, nyepetake lan nggawe iku cerdas.
Proses ngrampungake masalah kasebut dipérang dadi 2 tahap:
- ing tataran kapisan kita nemokake klompok kumpulan cedhak tanggal kanggo komprèsi;
- ing tataran kapindho, kanggo saben klompok kumpulan kita ngetung panggonan paling kompak saka barang isih ing sel.
Ing artikel saiki, kita bakal fokus ing tahap pertama algoritma, lan ninggalake jangkoan tahap kapindho kanggo artikel sabanjure.
Telusuri model matematika saka masalah
Sadurunge kita lungguh kanggo nulis kode lan reinvent kita wheel , kita mutusaké kanggo nyedhaki masalah iki ilmiah, yaiku: ngramu matématika, nyuda dadi masalah optimasi diskrèt kondhang lan nggunakake kalkulus ana efektif kanggo ngatasi, utawa njupuk iki algoritma ana. minangka basis lan ngowahi menyang spesifik masalah praktis sing ditanggulangi.
Awit iku cetha nderek saka formulasi bisnis saka masalah sing kita dealing with set, kita bakal ngramu masalah kuwi ing syarat-syarat teori set.
Ayo - set kabeh kumpulan saka sisa produk tartamtu ing gudang. Ayo – diwenehi pancet dina. Ayo – subset saka kumpulan, ing ngendi prabédan tanggal kanggo kabeh pasangan kumpulan ing subset ora ngluwihi konstanta . Kita kudu nemokake jumlah minimal subset disjoint , supaya kabeh subset dijupuk bebarengan bakal menehi akeh .
Ing tembung liya, kita kudu nemokake klompok utawa klompok saka pihak sing padha, ing ngendi kriteria kamiripan ditemtokake dening konstanta. . Tugas iki ngelingake masalah clustering sing kondhang. Penting kanggo ngomong yen masalah sing dipikirake beda karo masalah clustering amarga masalah kita nduweni kondisi sing ditemtokake kanthi ketat kanggo kriteria persamaan unsur kluster, sing ditemtokake dening konstanta. , nanging ing masalah clustering ora ana kondisi kasebut. Pernyataan masalah clustering lan informasi babagan masalah iki bisa ditemokake
Dadi, kita bisa ngrumusake masalah kasebut lan nemokake masalah klasik kanthi formulasi sing padha. Saiki perlu kanggo nimbang algoritma kondhang kanggo ngatasi, supaya ora reinvent setir, nanging njupuk laku paling apik lan aplikasi. Kanggo ngatasi masalah clustering, kita nganggep algoritma sing paling populer, yaiku: - tegese -tegese, algoritma kanggo ngenali komponen disambungake, algoritma wit spanning minimal. Katrangan lan analisis algoritma kasebut bisa ditemokake
Kanggo ngatasi masalah kita, algoritma clustering - tegese lan -tegese ora ditrapake ing kabeh, wiwit nomer klompok ora tau dikenal ing advance lan algoritma kuwi ora njupuk menyang akun alangan dina pancet. Algoritma kasebut wiwitane dibuwang saka pertimbangan.
Kanggo ngatasi masalah kita, algoritma kanggo ngenali komponen sing disambungake lan algoritma wit spanning minimal luwih cocok, nanging, ternyata, ora bisa ditrapake "head-on" kanggo masalah sing ditanggulangi lan entuk solusi sing apik. Kanggo nerangake iki, ayo nimbang logika operasi algoritma kasebut ing hubungane karo masalah kita.
Coba grafik , ing ngendi vertex minangka set partai , lan pinggiran antarane vertex и nduweni bobot padha karo prabédan dina antarane kumpulan и . Ing algoritma kanggo ngenali komponen sing disambungake, parameter input ditemtokake ngendi , lan ing grafik kabeh pinggiran sing bobote luwih gedhe dibusak . Mung pasangan obyek sing paling cedhak tetep nyambung. Titik algoritma yaiku milih nilai kasebut , ing endi grafik "ambruk" dadi sawetara komponen sing disambungake, ing ngendi pihak sing duwe komponen kasebut bakal nyukupi kritéria kamiripan, sing ditemtokake dening konstanta. . Komponen sing diasilake yaiku kluster.
Algoritma wit spanning minimal pisanan dibangun ing grafik wit spanning minimal, lan banjur sequentially mbusak sudhut karo bobot paling dhuwur nganti graph "mudhun loro" menyang sawetara komponen disambungake, ngendi pihak gadhah komponen iki uga bakal gawe marem kritéria podho kita. Komponen sing diasilake bakal dadi klompok.
Nalika nggunakake algoritma kasebut kanggo ngatasi masalah sing dipikirake, bisa uga ana kahanan kaya ing Gambar 3.
Fig 3. Aplikasi algoritma clustering kanggo masalah sing ditanggulangi
Ayo dadi konstanta kita kanggo beda antarane dina kumpulan yaiku 20 dina. Grafik digambarake ing wangun spasial kanggo gampang persepsi visual. Kaloro algoritma kasebut ngasilake solusi 3-cluster, sing bisa gampang didandani kanthi nggabungake batch sing diselehake ing klompok sing kapisah! Cetha yen algoritma kasebut kudu diowahi supaya cocog karo spesifik masalah sing ditanggulangi, lan aplikasi ing wangun murni kanggo solusi masalah kita bakal menehi asil sing ora apik.
Dadi, sadurunge kita miwiti nulis kode kanggo algoritma grafik sing diowahi kanggo tugas kita lan reinventing mancal kita dhewe (ing siluet kang kita wis bisa mbedakake njelaske nganggo bentuk garis saka gembong kothak), kita mutusaké kanggo nyedhaki masalah iki ilmiah, yaiku: nyoba kanggo ngurangi menyang Optimization masalah diskrèt liyane, ing pangarep-arep sing kalkulus ana kanggo mecahaken iku bisa Applied tanpa modifikasi.
Panelusuran liyane kanggo masalah klasik sing padha wis sukses! Kita bisa nemokake masalah optimasi diskret, formulasi sing pas 1 ing 1 karo formulasi masalah kita. Tugas iki ternyata nyetel masalah panutup. Ayo kita nampilake rumusan masalah sing ana hubungane karo spesifik kita.
Ana set winates lan kulawarga saka kabeh subset partai, saengga beda tanggal kanggo kabeh pasangan partai saben subset saka kulawarga ora ngluwihi konstanta . Panutup diarani kulawarga daya paling cilik, unsur kang kagungane , kuwi sing Uni saka set saka kulawarga kudu menehi set kabeh pihak .
Analisis rinci babagan masalah iki bisa ditemokake и Pilihan liyane kanggo aplikasi praktis saka masalah panutup lan modifikasi bisa ditemokake
Algoritma kanggo ngrampungake masalah
Kita wis mutusake model matematika saka masalah sing bakal ditanggulangi. Saiki ayo goleki algoritma kanggo ngrampungake. Subset saka kulawarga bisa gampang ditemokake dening prosedur ing ngisor iki.
- Atur batch saka set ing urutan mudhun tanggal sing.
- Temokake tanggal batch minimal lan maksimal.
- Kanggo saben dina saka tanggal minimal kanggo maksimum, golek kabeh kumpulan kang tanggal beda-beda saka ora luwih saka (dadi nilai Iku luwih apik kanggo njupuk nomer malah).
Logika prosedur kanggo mbentuk kulawarga set ing dina ditampilake ing Gambar 4.
Gambar 4. Pembentukan subset partai
Prosedur iki ora perlu kanggo kabeh wong pindhah liwat kabeh kumpulan liyane lan mriksa prabédan ing tanggal, utawa saka Nilai saiki pindhah ngiwa utawa nengen nganti sampeyan nemokake kumpulan sing tanggal beda saka dening luwih saka setengah Nilai saka konstanta. Kabeh unsur sakteruse, nalika obah loro ing sisih tengen lan ngiwa, ora bakal menarik kanggo kita, amarga kanggo wong-wong mau prabédan ing dina mung bakal nambah, amarga unsur ing Uploaded pisanan dhawuh. Pendekatan iki bakal ngirit wektu nalika jumlah partai lan panyebaran tanggale akeh banget.
Masalah panutup set punika -angel, kang tegese ora ana cepet (karo wektu operasi witjaksono menyang polynomial saka data input) lan algoritma akurat kanggo mecahaken iku. Mulane, kanggo ngatasi masalah sing nutupi set, algoritma rakus cepet dipilih, sing, mesthi, ora akurat, nanging nduweni kaluwihan ing ngisor iki:
- Kanggo masalah ukuran cilik (lan iki persis kasus kita), ngetung solusi sing cukup cedhak karo paling optimal. Minangka ukuran masalah mundhak, kualitas solusi deteriorates, nanging isih cukup alon;
- Gampang banget kanggo ngleksanakake;
- Cepet, wiwit estimasi wektu mlaku .
Algoritma rakus milih set adhedhasar aturan ing ngisor iki: ing saben tahapan, set dipilih sing nyakup jumlah maksimum unsur sing durung dijamin. Katrangan rinci babagan algoritma lan pseudocode bisa ditemokake
Perbandingan akurasi algoritma rakus kasebut ing data tes masalah sing ditanggulangi karo algoritma liyane sing dikenal, kayata algoritma rakus probabilistik, algoritma koloni semut, lan liya-liyane, durung digawe. Asil mbandhingake algoritma kasebut ing data acak sing digawe bisa ditemokake
Implementasi lan implementasine saka algoritma
Algoritma iki dileksanakake ing basa 1є lan iki klebu ing Processing external disebut "Residu Compression" kang disambungake menyang WMS-sistem. Kita ora ngleksanakake algoritma ing basa kasebut C ++ lan nggunakake saka komponen Native external, kang bakal luwih bener, wiwit kacepetan kode luwih murah C ++ kaping lan ing sawetara conto malah puluhan kaping luwih cepet saka kacepetan kode padha ing 1є. Ing ilat 1є Algoritma kasebut ditindakake kanggo ngirit wektu pangembangan lan gampang debugging ing basis produksi pelanggan. Asil saka algoritma ditampilake ing Gambar 5.
Gbr.5. Ngolah kanggo "compress" ampas
Gambar 5 nuduhake yen ing gudang sing ditemtokake, imbangan saiki barang ing sel panyimpenan dipérang dadi klompok, ing ngendi tanggal batch barang beda-beda ora luwih saka 30 dina. Wiwit customer mrodhuksi lan nyimpen katup werni logam ing gudang, kang urip beting wis diwilang ing taun, prabédan tanggal kuwi bisa nguciwakake. Elinga yen pangolahan kasebut saiki digunakake kanthi sistematis ing produksi, lan operator WMS konfirmasi kualitas apik saka clustering partai.
Kesimpulan lan tutugan
Pengalaman utama sing kita entuk saka ngrampungake masalah praktis kasebut yaiku konfirmasi efektifitas nggunakake paradigma: matematika. statement masalah Mat misuwur. model algoritma misuwur algoritma njupuk menyang akun tartamtu saka masalah. Optimasi diskrèt wis ana luwih saka 300 taun, lan ing wektu iki wong wis bisa nimbang akeh masalah lan nglumpukake akeh pengalaman kanggo ngrampungake. Kaping kabeh, iku luwih apik kanggo nguripake kanggo pengalaman iki, lan mung banjur miwiti reinventing Panjenengan wheel .
Ing artikel sabanjure, kita bakal nerusake crita babagan algoritma optimasi lan ndeleng sing paling menarik lan luwih rumit: algoritma kanggo "kompresi" optimal saka residu sel, sing nggunakake data sing ditampa saka algoritma clustering batch minangka input.
Disiapake artikel
Roman Shangin, programmer departemen proyek,
Perusahaan BIT pisanan, Chelyabinsk
Source: www.habr.com