Inilalarawan ng artikulo kung paano ipatupad WMS-system, nahaharap kami sa pangangailangang lutasin ang isang hindi karaniwang problema sa clustering at kung anong mga algorithm ang ginamit namin upang malutas ito. Sasabihin namin sa iyo kung paano namin inilapat ang isang sistematiko, siyentipikong diskarte sa paglutas ng problema, kung anong mga paghihirap ang aming naranasan at kung anong mga aral ang aming natutunan.
Nagsisimula ang publikasyong ito ng isang serye ng mga artikulo kung saan ibinabahagi namin ang aming matagumpay na karanasan sa pagpapatupad ng mga algorithm ng pag-optimize sa mga proseso ng bodega. Ang layunin ng serye ng mga artikulo ay upang ipaalam sa madla ang mga uri ng mga problema sa pag-optimize ng mga operasyon ng warehouse na lumitaw sa halos anumang daluyan at malaking bodega, pati na rin upang sabihin ang tungkol sa aming karanasan sa paglutas ng mga naturang problema at ang mga pitfalls na nakatagpo sa daan. . Ang mga artikulo ay magiging kapaki-pakinabang sa mga nagtatrabaho sa industriya ng logistik ng bodega, ipatupad WMS-mga sistema, pati na rin ang mga programmer na interesado sa mga aplikasyon ng matematika sa negosyo at pag-optimize ng mga proseso sa isang negosyo.
Bottleneck sa mga proseso
Noong 2018, natapos namin ang isang proyektong ipapatupad WMS-mga sistema sa bodega ng kumpanya na "Trading House "LD" sa Chelyabinsk. Ipinatupad namin ang produktong "1C-Logistics: Warehouse Management 3" para sa 20 lugar ng trabaho: mga operator WMS, mga tindera, mga driver ng forklift. Ang average na bodega ay humigit-kumulang 4 na libong m2, ang bilang ng mga cell ay 5000 at ang bilang ng mga SKU ay 4500. Ang bodega ay nag-iimbak ng mga ball valve ng aming sariling produksyon ng iba't ibang laki mula 1 kg hanggang 400 kg. Ang imbentaryo sa bodega ay naka-imbak sa mga batch, dahil may pangangailangan na pumili ng mga kalakal ayon sa FIFO.
Kapag nagdidisenyo ng mga scheme ng automation ng proseso ng warehouse, nahaharap kami sa kasalukuyang problema ng hindi pinakamainam na imbakan ng imbentaryo. Ang mga detalye ng pag-iimbak at pag-iimbak ng mga crane ay tulad na ang isang unit storage cell ay maaari lamang maglaman ng mga item mula sa isang batch. Dumarating ang mga produkto sa bodega araw-araw at bawat pagdating ay isang hiwalay na batch. Sa kabuuan, bilang isang resulta ng 1 buwan na operasyon ng bodega, 30 hiwalay na mga batch ang nilikha, sa kabila ng katotohanan na ang bawat isa ay dapat na naka-imbak sa isang hiwalay na cell. Ang mga produkto ay madalas na pinipili hindi sa buong mga pallet, ngunit sa mga piraso, at bilang isang resulta, sa zone ng pagpili ng piraso sa maraming mga cell ang sumusunod na larawan ay sinusunod: sa isang cell na may dami na higit sa 1 m3 mayroong ilang mga piraso ng crane na sumasakop ng mas mababa sa 5-10% ng dami ng cell.
Fig 1. Larawan ng ilang piraso ng kalakal sa isang cell
Malinaw na ang kapasidad ng imbakan ay hindi ginagamit nang husto. Upang isipin ang laki ng sakuna, maaari akong magbigay ng mga numero: sa karaniwan, mayroong mula 1 hanggang 3 na mga cell ng naturang mga cell na may dami na higit sa 100 m300 na may "minuscule" na balanse sa iba't ibang panahon ng operasyon ng bodega. Dahil medyo maliit ang bodega, sa panahon ng abalang panahon ng bodega ang salik na ito ay nagiging "bottleneck" at lubos na nagpapabagal sa mga proseso ng bodega.
Ideya ng solusyon sa problema
Lumitaw ang isang ideya: ang mga batch ng mga natira na may pinakamalapit na petsa ay dapat na bawasan sa isang solong batch, at ang mga natira na may pinag-isang batch ay dapat na ilagay nang magkakasama sa isang cell, o sa ilang, kung walang sapat na espasyo sa isa upang mapaunlakan ang buong dami ng natira.
Fig.2. Scheme para sa pag-compress ng mga nalalabi sa mga cell
Ito ay nagpapahintulot sa iyo na makabuluhang bawasan ang inookupahang espasyo ng bodega na gagamitin para sa mga bagong kalakal na inilalagay. Sa isang sitwasyon kung saan na-overload ang kapasidad ng warehouse, ang naturang panukala ay lubhang kailangan, kung hindi, maaaring walang sapat na libreng espasyo upang mapaunlakan ang mga bagong kalakal, na hahantong sa paghinto sa paglalagay ng bodega at mga proseso ng muling pagdadagdag. Dati bago ang pagpapatupad WMS-ginawa ng mga system ang operasyong ito nang manu-mano, na hindi epektibo, dahil medyo mahaba ang proseso ng paghahanap ng mga nalalabi sa mga cell. Ngayon, sa pagpapakilala ng isang WMS system, nagpasya kaming i-automate ang proseso, pabilisin ito at gawin itong matalino.
Ang proseso ng paglutas ng naturang problema ay nahahati sa 2 yugto:
- sa unang yugto nakita namin ang mga grupo ng mga batch na malapit sa petsa para sa compression;
- sa ikalawang yugto, para sa bawat pangkat ng mga batch ay kinakalkula namin ang pinaka-compact na paglalagay ng natitirang mga kalakal sa mga cell.
Sa kasalukuyang artikulo ay tututuon natin ang unang yugto ng algorithm, at iiwan ang saklaw ng ikalawang yugto para sa susunod na artikulo.
Maghanap ng isang mathematical model ng problema
Bago kami umupo upang magsulat ng code at muling likhain ang aming gulong, nagpasya kaming lapitan ang problemang ito sa siyentipikong paraan, ibig sabihin: bumalangkas ito sa matematika, bawasan ito sa isang kilalang problema sa discrete optimization at gumamit ng mga epektibong umiiral na algorithm upang malutas ito, o kunin ang mga umiiral na algorithm na ito bilang batayan at baguhin ang mga ito sa mga detalye ng praktikal na problemang nilulutas.
Dahil ito ay malinaw na sumusunod mula sa pormulasyon ng negosyo ng problema na kinakaharap natin sa mga set, bubuo tayo ng ganoong problema sa mga tuntunin ng set theory.
Hayaan β ang set ng lahat ng batch ng natitira sa isang partikular na produkto sa isang bodega. Hayaan β binibigyan ng pare-pareho ng mga araw. Hayaan β isang subset ng mga batch, kung saan ang pagkakaiba sa mga petsa para sa lahat ng mga pares ng mga batch sa subset ay hindi lalampas sa isang pare-pareho . Kailangan nating hanapin ang pinakamababang bilang ng mga magkahiwalay na subset , na ang lahat ng mga subset kapag pinagsama-sama ay magbibigay ng marami .
Sa madaling salita, kailangan nating maghanap ng mga grupo o kumpol ng magkatulad na partido, kung saan ang pamantayan ng pagkakapareho ay tinutukoy ng pare-pareho. . Ang gawaing ito ay nagpapaalala sa amin ng kilalang problema sa clustering. Mahalagang sabihin na ang problemang isinasaalang-alang ay naiiba sa clustering na problema dahil ang aming problema ay may mahigpit na tinukoy na kondisyon para sa kriterya ng pagkakatulad ng mga elemento ng kumpol, na tinutukoy ng pare-pareho. , ngunit sa problema sa clustering walang ganoong kondisyon. Ang pahayag ng problema sa clustering at impormasyon sa problemang ito ay matatagpuan
Kaya, nagawa naming bumalangkas ng problema at makahanap ng klasikal na problema na may katulad na pagbabalangkas. Ngayon ay kinakailangan na isaalang-alang ang mga kilalang algorithm para sa paglutas nito, upang hindi muling likhain ang gulong, ngunit upang gawin ang mga pinakamahusay na kasanayan at ilapat ang mga ito. Upang malutas ang problema sa clustering, isinasaalang-alang namin ang pinakasikat na mga algorithm, katulad: -ibig sabihin -ibig sabihin, algorithm para sa pagtukoy ng mga konektadong bahagi, minimum spanning tree algorithm. Ang isang paglalarawan at pagsusuri ng naturang mga algorithm ay matatagpuan
Upang malutas ang aming problema, clustering algorithm -ibig sabihin at -Ang ibig sabihin ay hindi naaangkop sa lahat, dahil ang bilang ng mga kumpol ay hindi alam nang maaga at ang mga naturang algorithm ay hindi isinasaalang-alang ang palagiang hadlang sa araw. Ang mga naturang algorithm ay una nang itinapon mula sa pagsasaalang-alang.
Upang malutas ang aming problema, ang algorithm para sa pagtukoy ng mga konektadong bahagi at ang minimum na spanning tree algorithm ay mas angkop, ngunit, tulad ng nangyari, hindi sila maaaring ilapat nang "head-on" sa problemang nilulutas at makakuha ng isang mahusay na solusyon. Upang ipaliwanag ito, isaalang-alang natin ang lohika ng pagpapatakbo ng naturang mga algorithm na may kaugnayan sa ating problema.
Isaalang-alang ang graph , kung saan ang mga vertex ay ang hanay ng mga partido , at ang gilid sa pagitan ng mga vertex ΠΈ ay may timbang na katumbas ng pagkakaiba ng mga araw sa pagitan ng mga batch ΠΈ . Sa algorithm para sa pagtukoy ng mga konektadong bahagi, tinukoy ang parameter ng input Saan , at sa graph lahat ng mga gilid kung saan mas malaki ang timbang ay tinanggal . Tanging ang pinakamalapit na pares ng mga bagay ay nananatiling konektado. Ang punto ng algorithm ay ang pumili ng ganoong halaga , kung saan ang graph ay "nahuhulog" sa ilang magkakaugnay na bahagi, kung saan ang mga partidong kabilang sa mga bahaging ito ay matutugunan ang aming pagkakatulad na pamantayan, na tinutukoy ng pare-pareho . Ang mga resultang bahagi ay mga kumpol.
Ang pinakamababang spanning tree algorithm ay unang nabuo sa isang graph pinakamababang spanning tree, at pagkatapos ay sunud-sunod na inaalis ang mga gilid na may pinakamataas na timbang hanggang sa ang graph ay "maghiwa-hiwalay" sa ilang konektadong mga bahagi, kung saan ang mga partidong kabilang sa mga bahaging ito ay matutugunan din ang aming pamantayan ng pagkakapareho. Ang mga resultang bahagi ay magiging mga kumpol.
Kapag gumagamit ng gayong mga algorithm upang malutas ang problemang isinasaalang-alang, maaaring lumitaw ang isang sitwasyon tulad ng sa Figure 3.
Fig 3. Application ng clustering algorithms sa problemang nireresolba
Sabihin nating ang ating pare-pareho para sa pagkakaiba sa pagitan ng mga araw ng batch ay 20 araw. Graph ay inilarawan sa spatial na anyo para sa kadalian ng visual na pang-unawa. Ang parehong mga algorithm ay gumawa ng isang 3-cluster na solusyon, na maaaring madaling mapabuti sa pamamagitan ng pagsasama-sama ng mga batch na inilagay sa magkahiwalay na mga cluster sa bawat isa! Malinaw na ang mga naturang algorithm ay kailangang baguhin upang umangkop sa mga detalye ng problemang nilulutas, at ang kanilang aplikasyon sa dalisay nitong anyo sa solusyon ng ating problema ay magbibigay ng hindi magandang resulta.
Kaya, bago kami nagsimulang magsulat ng code para sa mga algorithm ng graph na binago para sa aming gawain at muling likhain ang aming sariling bisikleta (sa mga silhouette kung saan maaari na naming makilala ang mga balangkas ng mga parisukat na gulong), muli, nagpasya kaming lapitan ang gayong problema sa siyentipikong paraan, lalo na: subukang bawasan ito sa isa pang discrete na pag-optimize ng problema, sa pag-asa na ang mga umiiral na algorithm para sa paglutas nito ay mailalapat nang walang pagbabago.
Ang isa pang paghahanap para sa isang katulad na klasikal na problema ay naging matagumpay! Nakahanap kami ng isang discrete na problema sa pag-optimize, ang pormulasyon nito ay tumutugma 1 sa 1 sa pagbabalangkas ng aming problema. Ang gawaing ito ay naging set covering problema. Ilahad natin ang pagbabalangkas ng problema kaugnay ng ating mga detalye.
Mayroong isang may hangganang hanay at pamilya ng lahat ng magkahiwalay na subset nito ng mga partido, na ang pagkakaiba sa mga petsa para sa lahat ng pares ng mga partido ng bawat subset mula sa pamilya ay hindi lalampas sa mga pare-pareho . Ang takip ay tinatawag na pamilya ng pinakamaliit na kapangyarihan, na kinabibilangan ng mga elemento , tulad na ang unyon ng mga set mula sa pamilya dapat ibigay ang hanay ng lahat ng partido .
Ang isang detalyadong pagsusuri sa problemang ito ay matatagpuan ΠΈ Ang iba pang mga opsyon para sa praktikal na aplikasyon ng problema sa takip at mga pagbabago nito ay matatagpuan
Algorithm para sa paglutas ng problema
Napagpasyahan namin ang modelo ng matematika ng problema na lutasin. Ngayon tingnan natin ang algorithm para sa paglutas nito. Mga subset mula sa pamilya ay madaling mahanap sa pamamagitan ng sumusunod na pamamaraan.
- Ayusin ang mga batch mula sa isang set sa pababang pagkakasunud-sunod ng kanilang mga petsa.
- Hanapin ang minimum at maximum na mga petsa ng batch.
- Para sa bawat araw mula sa minimum na petsa hanggang sa maximum, hanapin ang lahat ng mga batch na ang mga petsa ay naiiba hindi hihigit sa (kaya ang halaga Mas mainam na kunin ang even number).
Lohika ng pamamaraan para sa pagbuo ng isang pamilya ng mga hanay sa ang mga araw ay ipinakita sa Figure 4.
Fig.4. Pagbuo ng mga subset ng mga partido
Ang pamamaraang ito ay hindi kinakailangan para sa lahat dumaan sa lahat ng iba pang mga batch at suriin ang pagkakaiba sa kanilang mga petsa, o mula sa kasalukuyang halaga lumipat pakaliwa o pakanan hanggang sa makakita ka ng batch na iba ang petsa sa pamamagitan ng higit sa kalahati ng halaga ng pare-pareho. Ang lahat ng mga kasunod na elemento, kapag gumagalaw pareho sa kanan at kaliwa, ay hindi magiging kawili-wili sa amin, dahil para sa kanila ang pagkakaiba sa mga araw ay tataas lamang, dahil ang mga elemento sa array ay una nang iniutos. Ang diskarte na ito ay makabuluhang makakatipid ng oras kapag ang bilang ng mga partido at ang pagkalat ng kanilang mga petsa ay malaki.
Ang set covering problem ay -mahirap, na nangangahulugang walang mabilis (na may oras ng pagpapatakbo na katumbas ng isang polynomial ng data ng pag-input) at tumpak na algorithm para sa paglutas nito. Samakatuwid, upang malutas ang hanay na sumasaklaw sa problema, napili ang isang mabilis na sakim na algorithm, na, siyempre, ay hindi tumpak, ngunit may mga sumusunod na pakinabang:
- Para sa maliit na laki ng mga problema (at ito mismo ang aming kaso), kinakalkula nito ang mga solusyon na medyo malapit sa pinakamabuting kalagayan. Habang lumalaki ang laki ng problema, lumalala ang kalidad ng solusyon, ngunit medyo mabagal pa rin;
- Napakadaling ipatupad;
- Mabilis, dahil ang pagtatantya ng oras ng pagpapatakbo nito ay .
Ang greedy algorithm ay pumipili ng mga set batay sa sumusunod na panuntunan: sa bawat yugto, isang set ang pipiliin na sumasaklaw sa maximum na bilang ng mga elementong hindi pa sakop. Ang isang detalyadong paglalarawan ng algorithm at ang pseudocode nito ay matatagpuan
Ang paghahambing ng katumpakan ng gayong matakaw na algorithm sa data ng pagsubok ng problemang nilulutas sa iba pang kilalang algorithm, tulad ng probabilistic greedy algorithm, ant colony algorithm, atbp., ay hindi pa nagagawa. Ang mga resulta ng paghahambing ng mga naturang algorithm sa nabuong random na data ay matatagpuan
Pagpapatupad at pagpapatupad ng algorithm
Ang algorithm na ito ay ipinatupad sa wika 1S at isinama sa isang panlabas na pagproseso na tinatawag na "Residue Compression" na konektado sa WMS-sistema. Hindi namin ipinatupad ang algorithm sa wika C ++ at gamitin ito mula sa isang panlabas na Native component, na magiging mas tama, dahil mas mababa ang bilis ng code C + + beses at sa ilang mga halimbawa kahit na sampu-sampung beses na mas mabilis kaysa sa bilis ng katulad na code sa 1S. Sa dila 1S Ang algorithm ay ipinatupad upang makatipid ng oras ng pag-develop at kadalian ng pag-debug sa base ng produksyon ng customer. Ang resulta ng algorithm ay ipinakita sa Figure 5.
Fig.5. Pinoproseso upang "i-compress" ang mga nalalabi
Ipinapakita ng Figure 5 na sa tinukoy na bodega, ang kasalukuyang mga balanse ng mga kalakal sa mga cell ng imbakan ay nahahati sa mga kumpol, kung saan ang mga petsa ng mga batch ng mga kalakal ay naiiba sa bawat isa nang hindi hihigit sa 30 araw. Dahil ang customer ay gumagawa at nag-iimbak ng mga metal ball valve sa bodega, na ang buhay ng istante ay kinakalkula sa mga taon, ang gayong pagkakaiba ng petsa ay maaaring mapabayaan. Tandaan na ang naturang pagproseso ay kasalukuyang sistematikong ginagamit sa produksyon, at mga operator WMS kumpirmahin ang magandang kalidad ng party clustering.
Konklusyon at pagpapatuloy
Ang pangunahing karanasan na natamo namin sa paglutas ng gayong praktikal na problema ay ang pagkumpirma ng pagiging epektibo ng paggamit ng paradigm: matematika. pahayag ng problema sikat na banig. modelo sikat na algorithm algorithm na isinasaalang-alang ang mga detalye ng problema. Mahigit 300 taon nang umiral ang discrete optimization, at sa panahong ito nagawa ng mga tao na isaalang-alang ang maraming problema at nakaipon ng maraming karanasan sa paglutas ng mga ito. Una sa lahat, mas maipapayo na bumaling sa karanasang ito, at pagkatapos ay simulan ang muling pag-imbento ng iyong gulong.
Sa susunod na artikulo ipagpapatuloy namin ang kuwento tungkol sa mga algorithm sa pag-optimize at titingnan ang pinakakawili-wili at mas kumplikado: isang algorithm para sa pinakamainam na "compression" ng mga residu ng cell, na gumagamit ng data na natanggap mula sa batch clustering algorithm bilang input.
Inihanda ang artikulo
Roman Shangin, programmer ng departamento ng mga proyekto,
Unang kumpanya ng BIT, Chelyabinsk
Pinagmulan: www.habr.com