Toimingute parandamine marsruudi optimeerimise abil

Kaasautorid: Feiko Lai, Michal Szczecinski, Karupoeg, Miguel Fernandez

Iga päev saabuvad GOGOVANi autojuhid Aasia ladudesse, et korjata tuhandeid tellimusi, mida meie äripartnerid on palunud meil oma klientidele edastada.

Need tellimused võivad olla mitmesugused asjad - alates kauaoodatud uuest telefonist kuni viimasel minutil tellitud juubelikinkini. Kõik need on erineva suuruse, kuju ja raskusega. Kõigi nende jaoks on üks inimene, kes ootab ja loodab, et seekord jõuab kullerfirma õigeks ajaks kohale…

Seetõttu teeme GOGOVANis kõik endast oleneva, et tagada sujuvad ja õigeaegsed tarned kvaliteetse teenusega, mis hämmastab meie kliente. Iga tarnetee on hoolikalt käsitsi kavandatud ja meie operatsioonide meeskond kontrollib seda üle, et olla kindel, et me kunagi ei vea.

KÄSITSI ?!

Kas sa ei peaks lihtsalt ütlema, et teil on iga päev tuhandeid korraldusi?!

Jah, see on õige.

Varem pidi operatsioonide meeskond käsitsi sorteerima kättetoimetamise marsruudid, tavaliselt kauba vastuvõtmise hommikul, ja tagama, et vastaksime kõigile selle päeva tarneaja nõuetele. Nagu võite arvata, pole see eriti põnev ega kerge ülesanne :)

100-teekonnapunkti jaoks mitteoptimaalse marsruudi koostamiseks kulus ühel inimesel umbes üks tund. Sellest suuremate taotluste korral kasvas see aeg hüppeliselt.

Mõistsime koheselt, et see protsess kergitas lihtsalt mingit automatiseerimist.

Me mitte ainult ei tundnud kahetsust operatsioonide meeskonna üle, kes pidi igal varahommikul sellist igapäevast tööd tegema, vaid teadsime ka, et meie tellimuste mahu kasvades muutub see ülesanne aeglaselt missiooniks võimatuks. Nägime seda kui võimalust arendada tipptasemel tehnoloogiat, millest saab GOGOVANi andmeteaduste kogumi põhikomponent.

Kuidas me alustasime?

Oleme väga kliendi- ja juhikeskne. Sellest tulenevalt proovime alati kõigepealt analüüsida probleemi nende vaatenurgast, et mõista, kuidas meie lahendus võiks neile mõju avaldada. Pärast palju ajurünnakuid jõudsime järgmiste eesmärkideni:

  • Kõik tellimused tuleb kohale toimetada õigeaegselt.
  • Veenduge, et autojuhid ei kiirustaks seda õigel ajal tegema, kasutades puhveraegu ja reaalajas läbitud vahemaad.
  • Säästke kütust, vähendades läbitud vahemaad.
  • Minimeerige autojuhtide jõudeoleku aeg - mitte kellelegi ei meeldi oodata pakke täis pagasiruumiga.
  • Parandada sõiduki kasutamist.
  • Automatiseerige protsess täielikult.
  • Algoritm peab olema võimeline kasvama koos meiega - toetades eri tüüpi tarneid, sõidukeid ja riike.

Olles kindlaks määranud oma peamised eesmärgid, otsustasime uurida akadeemiliste ringkondade ja avatud lähtekoodiga maailma - pole mõtet ratast uuesti avastada. Mõistsime, et meie ees seisnud probleem oli laialt tuntud kui sõidukite marsruutimisprobleem.

Mis on sõidukite marsruutimisprobleem?

Sõidukite marsruutimisprobleeme (VRP) võib kirjeldada kui probleemi, mis on seotud optimaalsete marsruutide komplekti loomisega ühest või mitmest depoost mitmele kliendile, arvestades teatud piiranguid. Eesmärk on pakkuda kaupa kõigile klientidele, vähendades samal ajal marsruutide maksumust ja sõidukite arvu.

See probleem on NP-raske, nagu on tõestanud Lenstra ja Rinnooy Kan¹. Siiski on endiselt olemas mõned täpsed lahendusmeetodid, kasutades hargnenud ja seotud² või dünaamilist programmeerimist3, kuid nagu ülalpool kirjeldatud, näivad need töötavat ainult kuni 150 teekonnapunkti jaoks.

Praegu saadakse tipptasemel lahendusi metaheuristika abil: geneetilised algoritmid⁴, Tabu otsing⁵ ja antikoloonia optimeerimine⁶. Need on meetodid, mida tänapäeval kasutatakse peamiselt valdkonnas.

Valdkonna põhjalikuks ülevaateks soovitame seda hiilgavat lõputööd⁷, mille autor on Xiaoyan Li.

Meie lahendus

Kuna VRP on laialt tunnustatud probleem, on seal tõesti palju ettevõtteid, kes näivad selle probleemiga tegelevat.

Kuid me ei tundnud end nende lahendustega kuidagi rahul olevat ...

Me lihtsalt teadsime, et kui ühendada oma operatsiooniline oskusteave, andmeteadus ja teadusuuringute ekspertteadmised, suured andmemahud ja avatud lähtekoodiga moodsaim panus, võime jõuda tugeva sisemiseni lahenduseni, mis:

  • On ajakohasem, teostavam ning tal on kohandatavad algoritmid ja iteratsiooniloogika.
  • On odavam, tõhusam ja mastaapsem.
  • Võimaldab arendada materiaalset intellektuaalomandi vara ja ehitada selle ümber konkurentsieelised.
  • Võimaldab meil tagada oma klientidele, et nende tarneandmed ei lähe kaugemale kui GOGOVAN.

Mõeldes sellele üsna pikka aega, otsustasime, et kui tahame olla valdkonna juhid, peame seda tegema oma viisil, mitte kasutama mõnda blackboxi lahendust.

Nii et me läksime ...

Esimene algoritm

Kuid me ei sukeldunud kohe akadeemilistesse paberitesse!

Esiteks keskendusime oma lähenemisviiside väljatöötamisele ja nende hindamisele. See protsess võimaldas meil valdkonnast algusest peale paremini aru saada ja kogeda enda jaoks mõnda tavalist probleemi (me ei võtnud midagi enesestmõistetavaks!). Veelgi enam, see aitas meid hiljem, kuna saime hõlpsasti näha akadeemilistes töödes esitatud erinevate meetodite plusse ja miinuseid ning pakkuda välja strateegiaid nende ühendamiseks.

Selline protsess oli võti mõistmaks seda geniaalset paketti - Google'i optimeerimise tööriistu - kohe. Mõistsime, et Google'i inimesed päästsid meid kuude kaupa, et kulutaksime kõigi erinevate algoritmide kodeerimisele, mida tahtsime testida. Need võimaldasid meil kohe alla minna huvitavaimasse ossa!

Veetsime palju aega selle raamatukoguga mängides, erinevaid stsenaariume testides ja ise nähes, millised strateegiad millal toimisid.

Meile see nii meeldis, et otsustasime oma tööriista selle ümber ehitada!

Sellel oli kõik, mida vaja - läbipaistvus, katsetamisvõime, paindlikkus ja tugi.

Esimene algoritm oli valmis. Me juurutasime selle.

Joonis 1: Meie ühe esimese marsruudi optimeerimise ülesande visualiseerimine

Kiire kasv - kuidas käsitleda rohkem tellimusi?

Marsruudi optimeerimise esimene versioon osutus suureks õnnestumiseks.

Route Optimizerile esitatud tellimuste maht kasvas kiiresti 500-lt kaubalt lattu kuni 1000-ni. Teoreetiliselt peaks meil kõik korras olema.

Kuid me ei olnud.

Meie algoritmi käitusajad ja mälukasutus hüppasid uskumatult kiiresti - 1 minutist ja 500 MB-st 10 minutini ja 5 GB-ni. Proovides seda suuremate ja suuremate mahtude jaoks, jõudsime lõpuks maksimumini - 2000 teekonnapunkti jaoks kasutas moodul 25 GB RAM-mälu.

See oli vastuvõetamatu.

Põhimõtteliselt oli meil kaks võimalust:

  • Ehitage täiesti uus marsruudi optimeerija, mis vaikimisi suudaks toetada nii suuri mahtusid
  • Looge uus algoritm, mis töötab lisaks praegusele rakendusele - tõenäoliselt meetod, mis ühendab tellimusi väiksemates partiides, mis seejärel edastatakse peamisele optimeerimisalgoritmile

Kuna oleme praktilised (ja armastame ka juba tehtud suure töö peale ehitada), otsustasime jätkata teise variandiga.

Kuidas luua väiksemaid partiisid?

Alustame tuntud klasterdamisalgoritmiga - DBSCAN⁸.

Meil on nüüdisaegne meetod, mis koondab geograafilised punktid. Sellel on aga oma varjukülg: igal klastril peab olema sama raadius.

Seda ei soovi me ühel lihtsal põhjusel: üks Tsim Sha Tsui 1km raadiuses klaster võib sisaldada 1000 tellimust, teised Pok Fu Lam ja Waterfall Bay 1km klastrid võivad sisaldada ainult 3 tellimust.

Need klastrid oleksid tõesti ebaefektiivsed ja ebaühtlased ...

Tsim Sha Tsui puhul oleks klastri suurus liiga suur - meil oleks ühes klastris liiga palju tellimusi. Kuid samal ajal ei piisaks mõnes teises piirkonnas sellest raadiusest - klastrid oleksid liiga väikesed ja suhteliselt lähestikku asuvad korraldused paikneksid eraldi klastrites.

Seetõttu otsustasime kasutada muudetud lähenemisviisi - nn rekursiivne-DBSCAN.

Rekursiivne-DBSCAN

See tugineb DBSCANi hiilgusele, kuid samal ajal võimaldab meil kaevata sügavamale kõrge teekonnapunkti tihedusega piirkondadesse, grupeerides samal ajal kaugtellimusi.

Tellimuste loendi jaoks peame leidma raadiuse, mille jaoks keskmine teekonnapunktide arv on suurim (kuid klastrite arv on suurem kui min_no_clusters). Kasutame lihtsat binaarset otsingu algoritmi.

Kui oleme leidnud optimaalse lahenduse, sisestame liiga suured klastrid ja rakendame sama loogikat, kuni jõuame punktini, kus igas klastris on vähem kui max_len_cluster.

Seejärel käivitame iga klastri jaoks marsruudi optimeerimise algoritmi, mille oleme välja töötanud Google'i optimeerimise tööriistade abil. Loodetavasti annab see sarnase tulemuse kiiremini ja vähem RAM-i mälu kasutades.

Pseudokood on järgmine:

Võrdlusalused

Olime väga huvitatud sellest, kuidas meie meetod toimib, kuid samal ajal muretsesime, et rekursioon võib kesta väga kaua, muutes sellest tulenevalt meie algoritmi paremaks kui algtaseme meetod.

Sellepärast otsustasime kõigepealt uurida käitusaegu:

Selgus, et rekursiivne-dbscan-algoritm edestas suuresti Google'i optimeerimise tööriistade meetodit. Samal ajal ei erinenud see palju dbscan-meetodi käitamisaegadest.

Dbscan-i suutsime RAM-mälukasutuse tõttu käivitada maksimaalselt 2000 tellimust ja Google'i optimeerimise tööriistu 1500 tellimuse jaoks: mõlemad meetodid purunesid, kui mälu ületas 25 GB.

Kestusperioodid on olulised, kuid meid huvitas ka see, kuidas meie uus algoritm töötab võrreldes algmeetodiga kogupikkuse ja kasutatud sõidukite arvu osas. Need kaks graafikut näitavad järgmist:

Nagu näeme, järgib rekursiivne meetod nii kauguse kui ka sõidukite arvu osas täpselt Google'i optimeerimise tööriistade meetodit. Samal ajal edestab see dbscan-meetodit.

See tähendab, et meie uus algoritm on kiirem kui lähtejoon ja leitud lahenduste kvaliteet on sama hea. Samuti on maksimaalne kasutatav mälu “ainult” 1 GB!

Me saime selle!

DBSCAN vs rekursiivne-DBSCAN

Samuti tahtsime näidata teile, kuidas täpselt rekursiivne-dbscan töötab kaugemates teekonnapunktides paremini.

Joonis 5: DBSCAN ja rekursiivsete-DBSCAN marsruutide võrdlus. Me teame, et need pole endiselt täiuslikud!

Ülalpool vasakul on kaart, mis näitab tavalise DBSCAN algoritmi abil leitud ülesannet. Näeme, et paljud juhid toimetavad ainult ühe tellimuse - kuna need tellimused on nende partiides ainsad.

Parempoolsest küljest näeme, et rekursiivne meetod tegeleb selle küsimusega üsna hästi, kasutades eri piirkondade jaoks erinevaid raadiusi, ja õnnestub leida lahendus, mis annaks kõik tellimused ainult 3 sõidukiga!

See on täiuslik ülevaade sellest, kuidas rekursiivne-dbscan-meetod on meie kasutusjuhu jaoks parem ja miks me valisime selle kasutamise.

Järeldus (teise nimega TL; DR)

Selles artiklis oleme esitanud oma lähenemisviisi Time Windowsi mahukate sõidukite marsruutimisprobleemidele suure hulga teekonnapunktide (kuni 5000) jaoks. Rekursiivse dbscan-meetodi abil suutsime käitusaegu ja mälukasutust märkimisväärselt vähendada, säilitades samas tulemuste kvaliteedi nagu Google'i optimeerimise tööriistade algmeetodi puhul.

See algoritm on meie operatsioonide meeskonnale suureks abiks, vähendades argise käsitsitöö tunde mõne minutini protsessori ajast (ja tulemuste kahekordne kontrollimine inimese poolt).

Tulevik

Oleme teadlikud, et meie tööriist pole täiuslik.

Üks peamisi probleeme on see, et tegemist on ikkagi staatilise meetodiga, mis ei ajakohastatud rada enam paremat marsruuti saades või teeolukorra muutumisel iseenesest. Meil on sel juhul vähe võimalusi, üks neist on geohaldusprogrammi rakendamine nagu Lyft või teine, mis pärineb meie partnerilt - PolyU Hongkongi Big Data Analyticsi uurimisüksus.

Meie eesmärk on parendada marsruudi optimeerimist nii, et see jälgib pidevalt autojuhte ja saadab hoiatusi, kui autojuhid on oht, et nad ei saa seda mõne pakiga õigel ajal teha - seda kõike selleks, et muuta meie kliendid meie teenusega õnnelikumaks.

Loodetavasti on see artikkel teile andnud hea ülevaate probleemidest, millega GOGOVANil tegeleme. Kui see tundub teile huvitav või soovite lihtsalt rohkem teada saada, võtke kindlasti ühendust ja võtke ühendust.

Edaspidiseks täiustamiseks on loomulikult palju alust, kuid loodame jagada oma lähenemisviise, et käivitada arutelusid ja edusamme põnevas nõudluse logistika optimeerimise valdkonnas.
Kui soovite meie andmetiimi kohta rohkem teada saada, lugege meie andmejuhi artiklit siin.
Otsime alati tipptasemel rakendustoiminguid ja ML Researchi talente. Kui olete huvitatud, võtke ühendust! (Kohapealne ja kauge)
Viited:
[1] Lenstra, J. K. ja Kan, A. H. (1981), Sõidukite marsruutimis- ja sõiduplaani koostamise probleemide keerukus. Networks, 11: 221–227. doi: 10.1002 / net.3230110211
[2] Fukasawa, R., Longo, H., Lysgaard, J. jt. Matemaatika. Programm. (2006) 106: 491.
[3] Baldacci, R. & Mingozzi, A. Math. Programm. (2009) 120: 347. https://doi.org/10.1007/s10107-008-0218-9
[4] Nagata Y. (2007) servasõlme ristmik mahukate sõidukite marsruutimisprobleemi jaoks. Osades: Cotta C., van Hemert J. (toim) Evolutionary Computation in Combinatorial Optimization. EvoCOP 2007. Loengumärkused arvutiteaduses, vol 4446. Springer, Berliin, Heidelberg
[5] Bräysy, O. ja Gendreau, M. Top (2002) 10: 211. https://doi.org/10.1007/BF02579017
[6] Tan X., Zhuo X., Zhang J. (2006) Antikoloonia süsteem sõidukite marsruutimisprobleemide optimeerimiseks ajaakendega (VRPTW). Osades: Huang DS., Li K., Irwin G.W. (toim) arvutuslik intelligentsus ja bioinformaatika. ICIC 2006. Loengumärkused arvutiteaduses, vol 4115. Springer, Berliin, Heidelberg
[7] Xiaoyan Li (2015) Probleemne sõidukite marsruutimisprobleem ajaliste akendega: juhtumianalüüs mittetulundusühingutes dieettoodete korjamise kohta
[8] M. Ester, H. Kriegel, J. Sander ja X. Xu, Proc. 2. rahvusvaheline Konf. Teadmiste avastamine ja andmete kaevandamine (KDD’96), 1996, lk 226–231.