Atik la dekri kijan pou aplike WMS-system, nou te fè fas ak nesesite pou rezoud yon pwoblèm clustering ki pa estanda ak ki algoritm nou itilize pou rezoud li. N ap di w kouman nou te aplike yon apwòch sistematik, syantifik pou rezoud pwoblèm nan, ki difikilte nou te rankontre ak ki leson nou te aprann.
Piblikasyon sa a kòmanse yon seri atik kote nou pataje eksperyans siksè nou nan mete ann aplikasyon algoritm optimize nan pwosesis depo. Objektif la nan seri atik la se fè konesans odyans lan ak kalite pwoblèm optimize nan operasyon depo ki rive nan prèske nenpòt depo mwayen ak gwo, osi byen ke pale sou eksperyans nou nan rezoud pwoblèm sa yo ak enkonvenyans yo rankontre sou wout la. . Atik yo pral itil moun ki travay nan endistri a lojistik depo, aplike WMS-sistèm, osi byen ke pwogramasyon ki enterese nan aplikasyon pou matematik nan biznis ak optimize nan pwosesis nan yon antrepriz.
Boutik nan pwosesis yo
Nan 2018, nou te konplete yon pwojè pou aplike WMS-sistèm nan depo konpayi "Komèsyal House "LD" nan Chelyabinsk. Nou aplike pwodwi "1C-Logistics: Warehouse Management 3" pou 20 espas travay: operatè WMS, magazen, chofè chariot. Depo an mwayèn se sou 4 mil m2, kantite selil yo se 5000 ak kantite SKUs se 4500. Depo a magazen tiyo boul nan pwodiksyon pwòp nou yo nan diferan gwosè soti nan 1 kg a 400 kg. Envantè nan depo a estoke nan lo, paske gen yon bezwen chwazi machandiz dapre FIFO.
Lè w ap desine plan automatisation pwosesis depo, nou te fè fas ak pwoblèm ki egziste deja nan depo envantè ki pa optimal. Espesifik yo nan estoke ak stoke trepye yo se konsa ke yon sèl selil depo inite ka sèlman gen atik ki soti nan yon pakèt. Pwodwi yo rive nan depo a chak jou epi chak arive se yon pakèt separe. An total, kòm yon rezilta nan 1 mwa nan operasyon depo, 30 lo separe yo kreye, malgre lefèt ke chak ta dwe estoke nan yon selil separe. Pwodwi yo souvan chwazi pa nan palèt antye, men an moso, ak kòm yon rezilta, nan zòn nan seleksyon moso nan anpil selil yo obsève foto sa a: nan yon selil ki gen yon volim ki gen plis pase 1 m3 gen plizyè moso nan trepye ki okipe mwens pase 5-10% nan volim selil la.
Fig 1. Foto plizyè moso machandiz nan yon selil
Li klè ke kapasite depo pa ke yo te itilize optimal. Pou imajine echèl la nan dezas la, mwen ka bay figi: an mwayèn, gen soti nan 1 a 3 selil nan selil sa yo ak yon volim ki gen plis pase 100 m300 ak balans "miniskil" pandan diferan peryòd nan operasyon depo a. Depi depo a relativman ti, pandan sezon okipe depo a faktè sa a vin yon "boutèy" ak anpil ralanti pwosesis depo yo.
Lide solisyon pwoblèm
Yon lide te parèt: pakèt rès ki gen dat ki pi pre yo ta dwe redwi a yon sèl pakèt, epi rès sa yo ki gen yon pakèt inifye yo ta dwe mete konpak ansanm nan yon sèl selil, oswa nan plizyè, si pa gen ase espas nan yon sèl pou akomode a. tout kantite rès rès.
Fig.2. Scheme pou konpresyon résidus nan selil yo
Sa a pèmèt ou redwi siyifikativman espas depo okipe a ke yo pral itilize pou nouvo machandiz yo mete. Nan yon sitiyasyon kote kapasite depo twò chaje, mezi sa a trè nesesè, otreman ka tou senpleman pa gen ase espas gratis pou akomode nouvo machandiz, ki pral mennen nan yon kanpe nan plasman nan depo ak pwosesis renouvèlman. Anvan aplikasyon an WMS-systems fè operasyon sa a manyèlman, ki pa efikas, depi pwosesis pou chèche résidus apwopriye nan selil yo te byen long. Kounye a, ak entwodiksyon de yon sistèm WMS, nou deside otomatize pwosesis la, akselere li epi fè li entèlijan.
Pwosesis pou rezoud pwoblèm sa a divize an 2 etap:
- nan premye etap la nou jwenn gwoup pakèt fèmen nan dat pou konpresyon;
- nan dezyèm etap la, pou chak gwoup lo nou kalkile plasman ki pi kontra enfòmèl ant machandiz ki rete yo nan selil yo.
Nan atik aktyèl la nou pral konsantre sou premye etap algorithm la, epi kite kouvèti dezyèm etap la pou pwochen atik la.
Chèche yon modèl matematik pwoblèm nan
Anvan nou te chita pou ekri kòd epi re-envante wou nou an, nou te deside apwoche pwoblèm sa a syantifikman, sètadi: fòmile li matematik, redwi li nan yon pwoblèm byen koni optimize disrè epi itilize algoritm efikas ki egziste deja pou rezoud li, oswa pran algorithm sa yo ki egziste deja. kòm yon baz epi modifye yo nan spesifik yo nan pwoblèm nan pratik ke yo te rezoud.
Depi li klèman soti nan fòmilasyon biznis nan pwoblèm nan ke nou ap fè fas ak ansanm, nou pral fòmile tankou yon pwoblèm an tèm de teyori seri.
Se pou – seri tout pakèt rès yon sèten pwodwi nan yon depo. Kite – bay konstan jou. Kite – yon sou-ansanm nan pakèt, kote diferans lan nan dat pou tout pè pakèt nan sub-ansanm pa depase yon konstan . Nou bezwen jwenn kantite minimòm disjoint subsets , konsa tout sous-ensembles pran ansanm ta bay anpil .
Nan lòt mo, nou bezwen jwenn gwoup oswa grap nan pati ki sanble, kote kritè a resanblans detèmine pa konstan an. . Travay sa a fè nou sonje pwoblèm clustering byen li te ye. Li enpòtan pou nou di ke pwoblèm ki anba konsiderasyon an diferan de pwoblèm gwoupman an paske pwoblèm nou an gen yon kondisyon entèdi defini pou kritè resanblans eleman gwoup yo, ki detèmine pa konstan an. , men nan pwoblèm nan clustering pa gen okenn kondisyon sa yo. Ou ka jwenn deklarasyon pwoblèm gwoupman an ak enfòmasyon sou pwoblèm sa a
Se konsa, nou jere yo fòmile pwoblèm nan epi jwenn yon pwoblèm klasik ak yon fòmilasyon menm jan an. Koulye a, li nesesè yo konsidere algoritm byen li te ye pou rezoud li, se konsa yo pa reenvante volan an, men yo pran pi bon pratik yo epi aplike yo. Pou rezoud pwoblèm gwoupman an, nou konsidere algoritm ki pi popilè yo, sètadi: - vle di -means, algorithm pou idantifye konpozan konekte, minimòm spanning algorithm pyebwa. Ou ka jwenn yon deskripsyon ak analiz de algoritm sa yo
Pou rezoud pwoblèm nou an, clustering algorithms - vle di ak -Means yo pa aplikab ditou, depi kantite grap yo pa janm konnen davans ak algoritm sa yo pa pran an kont kontrent jou konstan. Algoritm sa yo te okòmansman jete nan konsiderasyon.
Pou rezoud pwoblèm nou an, algorithm pou idantifye eleman ki konekte ak algorithm pye bwa minimòm spanning la pi apwopriye, men, kòm li te tounen soti, yo pa ka aplike "tèt-sou" nan pwoblèm nan ke yo te rezoud epi jwenn yon solisyon bon. Pou eksplike sa, se pou nou konsidere lojik operasyon algorithm sa yo an relasyon ak pwoblèm nou an.
Konsidere graf la , kote somè yo se ansanm pati yo , ak kwen ki genyen ant somè yo и gen yon pwa ki egal a diferans ki genyen nan jou ant lo и . Nan algorithm pou idantifye eleman ki konekte yo, yo espesifye paramèt opinyon an kote , ak nan graf la tout kwen pou ki pwa a pi gwo yo retire . Se sèlman pè ki pi pre objè yo rete konekte. Pwen algorithm la se chwazi yon valè konsa , nan ki graf la "tonbe apa" nan plizyè eleman konekte, kote pati yo ki fè pati eleman sa yo pral satisfè kritè resanblans nou an, ki detèmine pa konstan an. . Konpozan ki kapab lakòz yo se grap.
Algorithm spanning tree minimòm lan premye bati sou yon graf minimòm spanning pye bwa, ak Lè sa a, sekans retire bor ak pwa ki pi wo a jiskaske graf la "tonbe apa" nan plizyè eleman konekte, kote pati yo ki fè pati eleman sa yo pral satisfè kritè resanblans nou an tou. Konpozan ki kapab lakòz yo pral grap.
Lè w ap itilize algorithm sa yo pou rezoud pwoblèm nan konsidere, yon sitiyasyon ka parèt tankou nan Figi 3.
Fig 3. Aplikasyon algorithm clustering nan pwoblèm nan rezoud
Ann di konstan nou an pou diferans ki genyen ant jou pakèt se 20 jou. Grafik te dekri nan fòm espasyal pou fasilite pèsepsyon vizyèl. Tou de algoritm yo te pwodwi yon solisyon 3-grap, ki ka fasil amelyore lè yo konbine pakèt yo mete nan grap separe youn ak lòt! Li evidan ke algoritm sa yo bezwen modifye pou adapte spesifik yo nan pwoblèm nan ke yo te rezoud, ak aplikasyon yo nan fòm pi li yo nan solisyon an nan pwoblèm nou an pral bay rezilta pòv yo.
Se konsa, anvan nou te kòmanse ekri kòd pou algorithm graf modifye pou travay nou an ak reenvante pwòp bisiklèt nou an (nan silwèt yo nan ki nou te kapab deja disène deskripsyon yo nan wou kare), nou, ankò, deside apwòch yon pwoblèm sa a syantifikman, sètadi: eseye diminye li nan yon lòt optimize pwoblèm disrè, nan espwa ke algoritm ki egziste deja pou rezoud li ka aplike san modifikasyon.
Yon lòt rechèch pou yon pwoblèm klasik menm jan an te reyisi! Nou te jere jwenn yon pwoblèm optimize disrè, fòmilasyon ki konyenside 1 nan 1 ak fòmilasyon pwoblèm nou an. Travay sa a te tounen vin jwenn li mete pwoblèm kouvri. Se pou nou prezante fòmilasyon pwoblèm nan an relasyon ak espesifik nou yo.
Gen yon seri fini ak fanmi nan tout pati disjoint li yo, konsa diferans ki genyen nan dat pou tout pè pati nan chak sous-ansanm soti nan fanmi an pa depase konstan . Yon kouvèti rele yon fanmi nan pi piti pouvwa a, eleman yo ki fè pati , tankou sendika a nan seri soti nan fanmi an ta dwe bay ansanm nan tout pati yo .
Ou ka jwenn yon analiz detaye sou pwoblèm sa a и Ou ka jwenn lòt opsyon pou aplikasyon an pratik nan pwoblèm nan kouvri ak modifikasyon li yo
Algorithm pou rezoud pwoblèm nan
Nou te deside sou modèl matematik pwoblèm nan dwe rezoud. Koulye a, ann gade nan algorithm pou rezoud li. Sou-ansanm soti nan fanmi an ka fasil jwenn pa pwosedi sa a.
- Fè aranjman pou lo nan yon seri nan lòd desandan dat yo.
- Jwenn dat pakèt minimòm ak maksimòm.
- Pou chak jou soti nan dat minimòm nan rive nan maksimòm, jwenn tout pakèt ki gen dat diferan de pa plis pase (konsa valè a Li pi bon pou w pran nimewo menm).
Lojik pwosedi pou fòme yon fanmi ansanm nan jou yo prezante nan Figi 4.
Fig.4. Fòmasyon sou-ansanm pati yo
Pwosedi sa a pa nesesè pou tout moun ale nan tout lòt lo epi tcheke diferans ki genyen nan dat yo, oswa nan valè aktyèl la deplase a goch oswa adwat jiskaske ou jwenn yon pakèt ki gen dat diferan de pa plis pase mwatye valè konstan an. Tout eleman ki vin apre yo, lè w ap deplase tou de sou bò dwat la ak sou bò gòch la, pa pral enteresan pou nou, paske pou yo diferans nan jou ap sèlman ogmante, depi eleman yo nan etalaj la te okòmansman bay lòd. Apwòch sa a pral siyifikativman ekonomize tan lè kantite pati yo ak pwopagasyon dat yo siyifikativman gwo.
Pwoblèm nan kouvri ansanm se -difisil, ki vle di pa gen okenn rapid (ak tan opere egal a yon polinòm nan done yo antre) ak algorithm egzat pou rezoud li. Se poutèt sa, pou rezoud pwoblèm nan kouvri seri, yo te chwazi yon algorithm visye rapid, ki, nan kou, se pa egzat, men li gen avantaj sa yo:
- Pou pwoblèm ti gwosè (e sa a se egzakteman ka nou an), li kalkile solisyon ki byen pre pi gwo a. Kòm gwosè a nan pwoblèm nan ogmante, bon jan kalite a nan solisyon an deteryore, men yo toujou byen dousman;
- Trè fasil pou aplike;
- Vit, depi estimasyon tan kouri li se .
Algorithm visye a chwazi seri ki baze sou règ sa a: nan chak etap, yo chwazi yon seri ki kouvri kantite maksimòm eleman ki poko kouvri. Ou ka jwenn yon deskripsyon detaye algorithm la ak pseudocode li yo
Yon konparezon de presizyon nan yon algorithm visye konsa sou done tès nan pwoblèm nan ke yo te rezoud ak lòt algorithm li te ye, tankou algorithm nan pwobabilite visye, algorithm nan koloni foumi, elatriye, pa te fèt. Ou ka jwenn rezilta konpare algorithm sa yo sou done o aza ki pwodui
Aplikasyon ak aplikasyon algorithm la
Algorithm sa a te aplike nan lang lan 1S epi li te enkli nan yon pwosesis ekstèn ki rele "Konpresyon rezidi" ki te konekte ak WMS-sistèm. Nou pa t aplike algorithm nan lang lan C ++ epi sèvi ak li soti nan yon eleman ekstèn natif natal, ki ta pi kòrèk, depi vitès la nan kòd la pi ba C ++ fwa ak nan kèk egzanp menm dè dizèn de fwa pi vit pase vitès la nan kòd ki sanble sou 1S. Sou lang 1S Algorithm la te aplike pou ekonomize tan devlopman ak fasilite debogaj nan baz pwodiksyon kliyan an. Rezilta algorithm la prezante nan Figi 5.
Fig.5. Pwosesis pou "konprese" résidus yo
Figi 5 montre ke nan depo espesifye, balans aktyèl machandiz yo nan selil depo yo divize an grap, nan ki dat pakèt machandiz yo diferan youn ak lòt pa plis pase 30 jou. Depi kliyan an pwodui ak estoke tiyo boul metal nan depo a, ki gen lavi etajè kalkile nan ane, tankou yon diferans dat ka neglije. Remake byen ke se pwosesis sa yo kounye a itilize sistematik nan pwodiksyon, ak operatè yo WMS konfime bon jan kalite a nan gwoupman pati.
Konklizyon ak kontinyasyon
Eksperyans prensipal ke nou te jwenn nan rezoud yon pwoblèm pratik konsa se konfimasyon efikasite nan sèvi ak paradigm nan: matematik. deklarasyon pwoblèm tapi popilè. modèl algorithm pi popilè algorithm pran an kont spesifik yo nan pwoblèm nan. Optimizasyon diskrè te alantou pou plis pase 300 ane, ak pandan tan sa a moun te jere yo konsidere yon anpil nan pwoblèm ak akimile anpil eksperyans nan rezoud yo. Premye a tout, li se pi plis konseye yo ale nan eksperyans sa a, epi sèlman Lè sa a, kòmanse reenvante wou ou.
Nan pwochen atik la nou pral kontinye istwa a sou algoritm optimize epi gade nan pi enteresan an ak pi konplèks: yon algorithm pou optimal "konpresyon" nan résidus selilè, ki sèvi ak done yo resevwa nan algorithm nan gwoup gwoup kòm opinyon.
Prepare pa
Roman Shangin, pwogramè depatman pwojè yo,
Premye konpayi BIT, Chelyabinsk
Sous: www.habr.com