Kab lus piav qhia yuav ua li cas siv WMS-system, peb tau ntsib nrog qhov xav tau los daws qhov teeb meem tsis yog txheej txheem pawg thiab dab tsi algorithms peb siv los daws nws. Peb yuav qhia rau koj paub tias peb siv txoj hauv kev zoo, kev tshawb fawb txog kev daws teeb meem, peb tau ntsib dab tsi thiab cov lus qhia uas peb tau kawm.
Cov ntawv tshaj tawm no pib ntau cov kab lus uas peb qhia peb cov kev paub dhau los hauv kev ua kom zoo tshaj plaws algorithms hauv cov txheej txheem warehouse. Lub hom phiaj ntawm cov kab lus yog kom paub cov neeg tuaj saib nrog cov hom kev txhim kho cov teeb meem ntawm kev ua haujlwm hauv tsev rau khoom uas tshwm sim hauv yuav luag txhua qhov chaw nruab nrab thiab loj warehouse, nrog rau kev qhia txog peb cov kev paub txog kev daws teeb meem zoo li no thiab cov pitfalls ntsib txoj kev. . Cov ntawv yuav muaj txiaj ntsig zoo rau cov neeg ua haujlwm hauv kev lag luam warehouse logistics, siv WMS-systems, nrog rau cov programmers uas txaus siab rau kev siv lej hauv kev lag luam thiab kev ua kom zoo ntawm cov txheej txheem hauv kev lag luam.
Bottleneck hauv cov txheej txheem
Hauv 2018, peb tau ua tiav ib qhov project los siv WMS-systems ntawm lub warehouse ntawm lub tuam txhab "Trading House "LD" nyob rau hauv Chelyabinsk. Peb tau siv cov khoom "1C-Logistics: Warehouse Management 3" rau 20 qhov chaw ua haujlwm: cov neeg ua haujlwm WMS, storekeepers, forklift drivers. Qhov nruab nrab warehouse yog hais txog 4 txhiab m2, cov xov tooj ntawm tes yog 5000 thiab tus naj npawb ntawm SKUs yog 4500. Lub warehouse khaws cov pob li qub ntawm peb tus kheej ntau thiab tsawg los ntawm 1 kg mus rau 400 kg. Cov khoom muag hauv lub tsev khaws khoom yog khaws cia hauv cov khoom siv, vim tias yuav tsum xaiv cov khoom raws li FIFO.
Thaum tsim cov txheej txheem warehouse automation schemes, peb tau ntsib nrog cov teeb meem uas twb muaj lawm ntawm cov khoom muag tsis zoo. Qhov tshwj xeeb ntawm kev khaws cia thiab stowing cranes yog xws li tias ib chav tsev cia khoom tsuas muaj cov khoom ntawm ib pawg. Cov khoom tuaj txog ntawm lub tsev khaws khoom txhua hnub thiab txhua qhov tuaj txog yog ib pawg cais. Nyob rau hauv tag nrho, raws li ib tug tshwm sim ntawm 1 lub hlis ntawm warehouse lag luam, 30 cais batch yog tsim, txawm lub fact tias txhua txhua yuav tsum tau muab cia rau hauv ib tug nyias muaj nyias ib lub cell. Cov khoom feem ntau raug xaiv tsis nyob hauv tag nrho cov pallets, tab sis nyob rau hauv daim, thiab yog li ntawd, nyob rau hauv lub piece xaiv cheeb tsam nyob rau hauv ntau lub hlwb daim duab hauv qab no yog pom: nyob rau hauv ib lub cell nrog ib tug ntim ntawm ntau tshaj 1 m3 muaj ob peb daim ntawm cranes. nyob tsawg dua 5-10% ntawm lub cell ntim.
Daim duab 1. Daim duab ntawm ob peb daim ntawm cov khoom hauv ib lub xov tooj ntawm tes
Nws yog qhov tseeb tias lub peev xwm khaws cia tsis raug siv kom zoo. Txhawm rau xav txog qhov ntsuas ntawm qhov kev puas tsuaj, kuv tuaj yeem muab cov duab: qhov nruab nrab, muaj los ntawm 1 mus rau 3 lub hlwb ntawm cov hlwb uas muaj ntau dua 100 m300 nrog "minuscule" sib npaug thaum lub sijhawm sib txawv ntawm lub tsev khaws khoom ua haujlwm. Txij li thaum lub tsev khaws khoom me me, thaum lub sij hawm warehouse tibneeg hu tauj coob lub caij, qhov no yuav ua tau ib tug "bottleneck" thiab heev slows down warehouse txheej txheem.
Teeb meem daws tswv yim
Ib lub tswv yim tau tshwm sim: cov khoom seem ntawm cov khoom seem nrog cov hnub ze tshaj plaws yuav tsum raug txo kom tsawg rau ib pawg, thiab cov khoom seem uas muaj kev sib koom ua ke yuav tsum tau muab tso rau hauv ib lub xov tooj ntawm tes, lossis hauv ob peb, yog tias tsis muaj qhov chaw txaus hauv ib qho los ua kom haum. tag nrho cov nyiaj tshuav.
Fig.2. Tswv yim rau compressing residues nyob rau hauv cell
Qhov no tso cai rau koj kom txo tau qhov chaw nyob hauv warehouses uas yuav siv rau cov khoom tshiab raug muab tso. Nyob rau hauv qhov xwm txheej uas muaj peev xwm warehouse overloaded, xws li ib qho kev ntsuas yog qhov tsim nyog heev, txwv tsis pub nws yuav tsis muaj qhov chaw dawb txaus kom haum rau cov khoom tshiab, uas yuav ua rau kom nres ntawm qhov chaw tso khoom thiab cov txheej txheem ntxiv. Yav dhau los ua ntej kev siv WMS-systems tau ua qhov haujlwm no manually, uas tsis muaj txiaj ntsig, txij li cov txheej txheem ntawm kev tshawb nrhiav cov khoom seem hauv lub hlwb tau ntev heev. Tam sim no, nrog kev qhia txog WMS qhov system, peb txiav txim siab los ua kom cov txheej txheem, ua kom nws ceev thiab ua kom ntse.
Cov txheej txheem ntawm kev daws qhov teeb meem no tau muab faib ua 2 theem:
- nyob rau hauv thawj theem peb pom cov pab pawg ntawm batch kaw nyob rau hauv hnub rau compression;
- nyob rau theem ob, rau txhua pab pawg ntawm batch peb xam qhov kev cog lus tshaj plaws ntawm cov khoom seem hauv lub hlwb.
Nyob rau hauv tsab xov xwm tam sim no peb yuav tsom mus rau thawj theem ntawm algorithm, thiab tawm kev pab them nqi ntawm theem thib ob rau tsab xov xwm tom ntej.
Tshawb nrhiav tus qauv lej ntawm qhov teeb meem
Ua ntej peb zaum los sau cov cai thiab rov tsim peb lub log, peb txiav txim siab los ua qhov teeb meem no scientifically, uas yog: tsim nws txoj kev ua lej, txo nws mus rau qhov kev paub zoo txog qhov teeb meem zoo tshaj plaws thiab siv cov algorithms uas twb muaj lawm los daws nws, lossis coj cov algorithms uas twb muaj lawm. raws li lub hauv paus thiab hloov lawv mus rau qhov tshwj xeeb ntawm cov teeb meem tswv yim raug daws.
Txij li nws kom meej meej ua raws li los ntawm kev lag luam formulation ntawm cov teeb meem uas peb tab tom soj ntsuam nrog poob lawm, peb yuav tsim ib qho teeb meem no nyob rau hauv cov nqe lus ntawm teeb txoj kev xav.
Cia - cov txheej txheem ntawm tag nrho cov khoom seem ntawm ib qho khoom hauv ib lub tsev rau khoom. Cia - muab tas li ntawm hnub. Cia - subset ntawm batch, qhov twg qhov sib txawv ntawm hnub rau tag nrho cov khub ntawm batches nyob rau hauv lub subset tsis tshaj ib tug tas li . Peb yuav tsum nrhiav qhov tsawg kawg nkaus ntawm disjoint subsets , zoo li tag nrho cov subsets coj ua ke yuav muab ntau .
Hauv lwm lo lus, peb yuav tsum nrhiav cov pab pawg lossis pawg ntawm cov tog neeg zoo sib xws, qhov twg cov txheej txheem zoo sib xws yog txiav txim los ntawm qhov tsis tu ncua . Txoj hauj lwm no ua rau peb nco txog qhov teeb meem kev sib koom ua ke. Nws yog ib qho tseem ceeb uas yuav tsum tau hais tias qhov teeb meem nyob rau hauv kev txiav txim siab txawv ntawm qhov teeb meem ntawm pawg hauv qhov uas peb qhov teeb meem muaj cov txheej txheem nruj me ntsis rau cov txheej txheem ntawm qhov sib xws ntawm pawg pawg, txiav txim siab los ntawm qhov tas li. , tab sis nyob rau hauv lub clustering teeb meem tsis muaj xws li mob. Cov lus hais txog qhov teeb meem ntawm pawg thiab cov ntaub ntawv ntawm qhov teeb meem no tuaj yeem pom
Yog li, peb tau tswj hwm los tsim qhov teeb meem thiab nrhiav tau ib qho teeb meem classical nrog cov qauv zoo sib xws. Tam sim no nws yog ib qho tsim nyog los xav txog cov txheej txheem paub zoo rau kev daws nws, yog li tsis yog rov tsim lub log, tab sis coj cov kev coj ua zoo tshaj plaws thiab siv lawv. Txhawm rau daws qhov teeb meem ntawm pawg, peb suav tias yog cov algorithms nrov tshaj plaws, uas yog: - txhais tau tias -txhais tau hais tias, algorithm rau kev txheeb xyuas cov khoom sib txuas, qhov tsawg kawg nkaus spanning ntoo algorithm. Kev piav qhia thiab kev txheeb xyuas ntawm cov algorithms tuaj yeem pom
Yuav kom daws tau peb cov teeb meem, pawg algorithms - txhais tau tias thiab - txhais tau tias tsis muaj feem xyuam rau tag nrho, txij li tus naj npawb ntawm pawg tsis tau paub ua ntej thiab xws li algorithms tsis coj mus rau hauv tus account lub hnub tsis tu ncua. Xws li algorithms tau pib muab pov tseg los ntawm kev xav.
Txhawm rau daws peb cov teeb meem, lub algorithm rau kev txheeb xyuas cov khoom sib txuas thiab qhov tsawg kawg nkaus spanning ntoo algorithm yog qhov tsim nyog dua, tab sis, raws li nws tau muab tawm, lawv tsis tuaj yeem siv "head-on" rau qhov teeb meem tau daws thiab tau txais kev daws teeb meem zoo. Txhawm rau piav qhia qhov no, cia peb xav txog cov laj thawj ntawm kev ua haujlwm ntawm cov algorithms uas cuam tshuam nrog peb qhov teeb meem.
Xav txog daim duab , nyob rau hauv uas lub vertices yog cov txheej ntawm ob tog , thiab ntug nruab nrab ntawm cov vertices ΠΈ muaj qhov hnyav sib npaug rau qhov sib txawv ntawm hnub ntawm cov khoom siv ΠΈ . Nyob rau hauv lub algorithm rau kev txheeb xyuas cov khoom sib txuas, cov khoom siv nkag tau teev tseg qhov twg , thiab hauv daim duab tag nrho cov npoo uas qhov hnyav ntau dua raug tshem tawm . Tsuas yog qhov ze tshaj plaws ntawm cov khoom tseem txuas nrog. Lub ntsiab lus ntawm algorithm yog xaiv tus nqi zoo li no , nyob rau hauv uas cov duab "poob sib nrug" mus rau ntau yam kev sib txuas, qhov twg ob tog koom nrog cov khoom no yuav ua tau raws li peb cov kev cai zoo sib xws, txiav txim siab los ntawm qhov tas li. . Qhov tshwm sim cov khoom yog pawg.
Qhov tsawg kawg nkaus spanning ntoo algorithm ua ntej tsim ntawm ib daim duab yam tsawg kawg nkaus spanning ntoo, thiab tom qab ntawd tshem tawm cov npoo nrog qhov hnyav tshaj plaws kom txog rau thaum daim duab "tso tawm" mus rau ntau qhov sib txuas, qhov twg cov tog neeg koom nrog cov khoom no kuj yuav ua rau peb zoo sib xws. Qhov tshwm sim ntawm cov khoom yuav yog pawg.
Thaum siv cov algorithms los daws qhov teeb meem hauv kev xav, qhov xwm txheej yuav tshwm sim raws li hauv daim duab 3.
Daim duab 3. Daim ntawv thov ntawm kev sib koom ua ke algorithms rau qhov teeb meem tau daws
Cia peb hais tias peb qhov tsis tu ncua rau qhov sib txawv ntawm batch hnub yog 20 hnub. Daim duab tau piav qhia nyob rau hauv daim ntawv spatial kom yooj yim ntawm kev pom kev pom. Ob qho tib si algorithms tsim ib qho kev daws teeb meem 3-cluster, uas tuaj yeem txhim kho tau yooj yim los ntawm kev sib txuas cov khoom tso rau hauv cov pawg sib cais! Nws yog qhov pom tseeb tias cov algorithms yuav tsum tau hloov kho kom haum rau qhov tshwj xeeb ntawm qhov teeb meem raug daws, thiab lawv daim ntawv thov hauv nws daim ntawv ntshiab rau kev daws peb qhov teeb meem yuav ua rau cov txiaj ntsig tsis zoo.
Yog li, ua ntej peb pib sau cov lej rau graph algorithms hloov kho rau peb txoj haujlwm thiab rov tsim kho peb tus kheej lub tsheb kauj vab (hauv silhouettes uas peb tuaj yeem pom cov qauv ntawm lub log square), peb, dua, txiav txim siab los ua qhov teeb meem xws li kev tshawb fawb, xws li: sim txo nws mus rau lwm qhov teeb meem kev ua kom zoo dua qub, hauv kev cia siab tias cov algorithms uas twb muaj lawm rau kev daws nws tuaj yeem siv yam tsis muaj kev hloov kho.
Lwm qhov kev tshawb nrhiav rau qhov teeb meem classical zoo sib xws tau ua tiav! Peb tau tswj xyuas kom pom qhov teeb meem kev ua kom zoo tsis sib haum, qhov kev tsim ntawm uas coincides 1 hauv 1 nrog cov qauv ntawm peb qhov teeb meem. Txoj hauj lwm no tau tshwm sim teeb npog teeb meem. Cia peb nthuav qhia cov qauv ntawm qhov teeb meem cuam tshuam nrog peb cov kev tshwj xeeb.
Muaj ib tug finite set thiab tsev neeg ntawm tag nrho nws cov disjoint subsets ntawm ob tog, xws li qhov sib txawv nyob rau hauv hnub rau tag nrho cov khub ntawm ob tog ntawm txhua subset los ntawm tsev neeg tsis tshaj qhov qub . Ib daim npog hu ua tsev neeg ntawm lub hwj chim tsawg tshaj plaws, cov ntsiab lus uas muaj nyob rau , xws li lub union ntawm poob lawm los ntawm tsev neeg yuav tsum muab cov txheej txheem ntawm txhua tog .
Kev soj ntsuam ntxaws txog qhov teeb meem no tuaj yeem pom ΠΈ Lwm cov kev xaiv rau kev siv tswv yim ntawm cov teeb meem npog thiab nws cov kev hloov kho tuaj yeem pom
Algorithm rau kev daws qhov teeb meem
Peb tau txiav txim siab ntawm tus qauv lej ntawm qhov teeb meem yuav daws tau. Tam sim no cia saib lub algorithm rau kev daws nws. Subsets los ntawm tsev neeg tuaj yeem pom tau yooj yim los ntawm cov txheej txheem hauv qab no.
- Npaj batch los ntawm ib txheej nyob rau hauv qis qis ntawm lawv cov hnub.
- Nrhiav qhov tsawg kawg nkaus thiab siab kawg batch hnub.
- Rau txhua hnub txij hnub yam tsawg kawg mus rau qhov siab tshaj plaws, nrhiav txhua pawg uas nws cov hnub sib txawv tsis muaj ntau tshaj li (yog li tus nqi Nws yog qhov zoo dua los coj tus lej sib npaug).
Logic ntawm cov txheej txheem rau kev tsim ib tsev neeg ntawm cov txheej txheem ntawm hnub tau nthuav tawm hauv daim duab 4.
Fig.4. Tsim cov subsets ntawm tog
Cov txheej txheem no tsis tsim nyog rau txhua tus mus dhau tag nrho lwm cov batch thiab xyuas qhov sib txawv ntawm lawv cov hnub, lossis los ntawm tus nqi tam sim no txav mus rau sab laug lossis sab xis kom txog thaum koj pom ib pawg uas nws hnub txawv ntawm los ntawm ntau tshaj ib nrab ntawm tus nqi ntawm qhov tsis tu ncua. Tag nrho cov ntsiab lus tom ntej, thaum tsiv mus rau sab xis thiab sab laug, yuav tsis nthuav rau peb, vim rau lawv qhov sib txawv ntawm cov hnub tsuas yog nce ntxiv, txij li cov ntsiab lus hauv array tau pib xaj. Txoj hauv kev no yuav txuag lub sijhawm thaum muaj pes tsawg tus tog neeg thiab kev sib kis ntawm lawv cov hnub tseem ceeb heev.
Lub teeb npog teeb meem yog - nyuaj, uas txhais tau hais tias tsis muaj qhov nrawm (nrog rau lub sijhawm ua haujlwm sib npaug ntawm cov ntaub ntawv sau npe) thiab qhov tseeb algorithm rau kev daws nws. Yog li ntawd, txhawm rau daws qhov teeb meem npog qhov teeb meem, xaiv qhov ceev greedy algorithm, uas, ntawm chav kawm, tsis yog, tab sis muaj qhov zoo hauv qab no:
- Rau cov teeb meem me me (thiab qhov no yog raws nraim peb cov ntaub ntawv), nws suav cov kev daws teeb meem uas ze rau qhov zoo tshaj plaws. Raws li qhov loj ntawm qhov teeb meem nce, qhov zoo ntawm cov tshuaj deteriorates, tab sis tseem qeeb heev;
- Yooj yim heev rau kev siv;
- Ceev ceev, txij li nws lub sijhawm kwv yees ua haujlwm yog .
Lub greedy algorithm xaiv cov txheej txheem raws li txoj cai hauv qab no: nyob rau txhua theem, ib pawg raug xaiv uas suav nrog ntau tshaj ntawm cov ntsiab lus tseem tsis tau them. Cov lus piav qhia ntxaws ntxaws ntawm algorithm thiab nws cov pseudocode tuaj yeem pom
Ib qho kev sib piv ntawm qhov tseeb ntawm qhov kev ntshaw algorithm ntawm kev sim cov ntaub ntawv ntawm qhov teeb meem raug daws nrog rau lwm cov algorithms paub, xws li qhov kev ntshaw ntshaw algorithm, tus ntsaum colony algorithm, thiab lwm yam, tsis tau ua. Cov txiaj ntsig ntawm kev sib piv xws li algorithms ntawm generated random cov ntaub ntawv tuaj yeem pom
Kev siv thiab kev siv cov algorithm
Qhov algorithm no tau muab coj los siv ua lus 1S thiab tau suav nrog kev ua haujlwm sab nraud hu ua "Residue Compression" uas tau txuas nrog WMS-system. Peb tsis tau siv cov algorithm hauv cov lus C++ thiab siv nws los ntawm ib qho kev tivthaiv Native sab nraud, uas yuav yog qhov tseeb dua, vim tias qhov ceev ntawm txoj cai qis dua C ++ lub sij hawm thiab nyob rau hauv ib co piv txwv txawm kaum ntawm lub sij hawm sai tshaj qhov ceev ntawm cov code zoo sib xws rau 1S. Ntawm tus nplaig 1S Lub algorithm tau siv los txuag lub sijhawm txhim kho thiab yooj yim ntawm kev debugging ntawm tus neeg siv khoom lub hauv paus. Cov txiaj ntsig ntawm algorithm yog nthuav tawm hauv daim duab 5.
Fig.5. Ua rau "compress" residues
Daim duab 5 qhia tau hais tias nyob rau hauv lub warehouses teev, tam sim no tshuav nyiaj li cas ntawm cov khoom nyob rau hauv cia cell muab faib ua pawg, nyob rau hauv uas cov hnub ntawm cov khoom batches txawv ntawm ib leeg tsis pub dhau 30 hnub. Txij li thaum tus neeg siv khoom tsim thiab khaws cov hlau pob li qub hauv lub tsev rau khoom, nws lub neej txee yog suav nrog xyoo, xws li hnub sib txawv tuaj yeem tsis quav ntsej. Nco ntsoov tias cov txheej txheem no yog tam sim no siv systematically hauv ntau lawm, thiab cov neeg ua haujlwm WMS paub meej tias qhov zoo ntawm tog pawg.
Cov lus xaus thiab txuas ntxiv
Qhov kev paub tseem ceeb uas peb tau txais los ntawm kev daws qhov teeb meem zoo li no yog kev lees paub ntawm kev siv lub tswv yim zoo: lej. teeb meem nqe lus nto moo mat. qauv nto moo algorithm algorithm coj mus rau hauv tus account qhov tshwj xeeb ntawm qhov teeb meem. Kev ua kom zoo tsis tu ncua tau nyob ib puag ncig ntau dua 300 xyoo, thiab lub sijhawm no tib neeg tau tswj hwm los txiav txim siab ntau yam teeb meem thiab suav nrog ntau yam kev paub daws teeb meem. Ua ntej tshaj plaws, nws yog qhov pom zoo kom tig mus rau qhov kev paub no, thiab tsuas yog tom qab ntawd pib rov tsim koj lub log.
Nyob rau hauv tsab xov xwm tom ntej no peb yuav txuas ntxiv zaj dab neeg txog kev ua kom zoo tshaj plaws algorithms thiab saib qhov nthuav dav tshaj plaws thiab ntau txoj hauv kev: ib qho algorithm rau "compression" ntawm cov cell residues, uas siv cov ntaub ntawv tau txais los ntawm batch clustering algorithm raws li cov tswv yim.
Npaj los ntawm
Roman Shangin, programmer ntawm cov haujlwm department,
Thawj BIT tuam txhab, Chelyabinsk
Tau qhov twg los: www.hab.com