Toimintojen parantaminen reitin optimoinnilla

Avustajat: Feiko Lai, Michal Szczecinski, Winnie So, Miguel Fernandez

GOGOVAN-kuljettajat saapuvat joka päivä Aasiaan varastoihin hakemaan tuhansia tilauksia, jotka liikekumppanimme ovat pyytäneet meitä toimittamaan asiakkailleen.

Nämä tilaukset voivat olla erilaisia ​​asioita - siitä kauan odotetusta uudesta puhelimesta viime hetken tilaaman vuosipäivän lahjaksi. Kaikki ne ovat erikokoisia, -muotoisia ja -painoisia. Jokaisessa heistä on henkilö, joka odottaa ja toivoo, että tällä kertaa kuriiriyhtiö saapuu sinne oikeaan aikaan ...

Siksi GOGOVANissa teemme kaikkemme varmistaaksemme sujuvat ja oikea-aikaiset toimitukset palvelun laadulla, joka hämmästyttää asiakkaitamme. Jokainen toimitusreitti suunnitellaan huolellisesti manuaalisesti ja operatiivisen tiimimme tarkistaa se kaksinkertaisesti varmistaaksemme, että emme koskaan epäonnistu.

KÄSIN?!

Etkö sinä vain sanoisi, että sinulla on tuhansia tilauksia päivittäin ?!

Kyllä se on oikein.

Aikaisemmin Operations-tiimin piti lajitella toimitusreitit manuaalisesti, yleensä noutoaamuna, ja varmistaa, että noudatamme kaikkia kyseisen päivän toimitusaikavaatimuksia. Kuten voitte kuvitella, se ei ole erityisen jännittävä tai helppo tehtävä :)

Yhden henkilön kesti noin yksi tunti optimaalisen reitin luomiseen 100 reittipisteelle. Suurempia pyyntöjä varten tämä aika kasvoi eksponentiaalisesti.

Ymmärsimme heti, että tämä prosessi vain kerättiin jonkin verran automaatiota.

Pahoittelemme paitsi operaatioryhmää, joka joutui tekemään sellaista arkipäivää joka aamu aamulla, mutta tiesimme myös, että tilausmäärämme kasvaessa siitä tehtävästä tulee hitaasti tehtävä mahdotonta. Näimme sen tilaisuutena kehittää huipputeknologiaa, josta tulee keskeinen osa GOGOVANin Data Science -pinoa.

Kuinka aloitimme?

Olemme erittäin asiakas- ja kuljettajakeskeisiä. Siksi yritämme aina ensin analysoida ongelmaa niiden näkökulmasta ymmärtääksemme, kuinka ratkaisumme voi vaikuttaa niihin ja hyödyttää niitä. Paljon aivoriihiä jälkeen nämä tavoitteet saavutimme:

  • Kaikki tilaukset on toimitettava ajoissa.
  • Varmista, että kuljettajia ei kiirehdi tekemään sitä ajoissa käyttämällä puskuriaikoja ja reaaliaikaista etäisyyttä.
  • Säästä polttoainetta vähentämällä ajomatkaa.
  • Minimoi kuljettajien joutokäynti - kukaan ei tykkää odottaa odottamalla täydellä tavaratilalla.
  • Paranna ajoneuvojen käyttöä.
  • Automatisoi prosessi täysin.
  • Algoritmin on kyettävä kasvamaan kanssamme - tukemalla erityyppisiä toimituksia, ajoneuvoja ja maita.

Päätettyään päätavoitteemme päätimme tutkia akateemisen maailman ja avoimen lähdekoodin maailmaa - ei ole mitään syytä löytää pyörä uudelleen. Ymmärsimme, että kohtaamiemme ongelma tunnetaan laajalti nimellä ajoneuvojen reititysongelma.

Mikä on ajoneuvojen reititysongelma?

Ajoneuvojen reititysongelmaa (VRP) voidaan kuvata ongelmana luoda joukko optimaalisia reittejä yhdestä tai useammasta varastosta useille asiakkaille, jollei rajoituksista muuta johdu. Tavoitteena on toimittaa tavaroita kaikille asiakkaille, minimoimalla samalla reittien kustannukset ja ajoneuvojen lukumäärä.

Tämä ongelma on NP-kova, kuten Lenstra ja Rinnooy Kan¹ ovat todistaneet. On kuitenkin edelleen joitain tarkkoja ratkaisumenetelmiä, joissa käytetään haara-ja-sidottua2 tai dynaamista ohjelmointia3, mutta kuten edellä olevissa julkaisuissa kuvataan, ne näyttävät toimivan vain 150 reittipisteessä.

Nykyään huipputekniset ratkaisut saadaan käyttämällä metaheuristiikkaa: Geneettiset algoritmit⁴, Tabu Search⁵ ja Ant Colony Optimization⁶. Näitä menetelmiä käytetään pääasiassa kentällä nykyään.

Suosittelemme alan syvällistä katsausta Xiaoyan Li loistava opinnäytetyö⁷.

Ratkaisumme

Koska VRP on laajalti tunnustettu ongelma, siellä on todella paljon yrityksiä, jotka näyttävät ratkaisevan ongelman.

Emme jotenkin olleet tyytyväisiä ratkaisuihimme ...

Tiesimme vain, että jos yhdistämme toimintamme tietotaidon, tietotekniikan ja tutkimusosaamisen, suuret tietomäärät ja avoimen lähdekoodin huipputekniset tiedot, voimme saavuttaa vankan sisäisen ratkaisun, joka:

  • On nykyaikaisempi, suorittava ja siinä on muokattavissa olevat algoritmit ja iterointilogiikka.
  • On halvempi, tehokkaampi ja skaalautuvampi.
  • Mahdollistaa aineellisen omaisuuden kehittämisen ja kilpailuedun rakentamisen sen ympärille.
  • Voimme taata asiakkaillemme, että heidän toimitustiedot eivät mene pidemmälle kuin GOGOVAN.

Pohtinut sitä jo melko kauan, päätimme, että jos haluamme olla alan johtajia, meidän on tehtävä se omalla tavallamme, ettemme käytä jotakin blackbox-ratkaisua.

Joten menimme ...

Ensimmäinen algoritmi

Mutta emme suostuneet akateemisiin tutkimuksiin heti!

Ensinnäkin keskityimme keksimään omia lähestymistapojamme ja arvioimaan niitä. Tämän prosessin avulla saimme paremman käsityksen kentästä alusta alkaen ja koemme itsellemme joitain yleisiä ongelmia (emme ottaneet mitään itsestäänselvyytenä!). Lisäksi tämä auttoi meitä myöhemmin, koska pystyimme helposti näkemään akateemisessa työssä esitettyjen erilaisten menetelmien hyvät ja huonot puolet ja keksimään strategioita niiden yhdistämiseksi.

Tällainen prosessi oli avain ymmärtää heti, kuinka tämä loistava paketti - Google Optimization Tools - toimi. Ymmärsimme, että Googlen ihmiset säästivät meitä kuukausia, jolloin vietimme koodaamaan kaikki erilaiset algoritmit, jotka halusimme testata. He antoivat meille pääsyn mielenkiintoisimpaan osaan heti!

Vietimme paljon aikaa leikkimällä kyseisen kirjaston kanssa, testaamalla erilaisia ​​skenaarioita ja nähdäksemme itse, mitkä strategiat toimivat milloin.

Pidimme siitä niin paljon, päätimme rakentaa työkalumme sen ympärille!

Siinä oli kaikki mitä tarvitsimme - läpinäkyvyys, kyky kokeilla, joustavuus ja tuki.

Ensimmäinen algoritmi oli valmis. Olemme ottaneet sen käyttöön.

Kuva 1: Visualisointi yhdestä ensimmäisistä reittien optimointitehtävistämme

Nopea kasvu - kuinka käsitellä enemmän tilauksia?

Reittien optimoinnin ensimmäinen versio osoittautui menestykseksi.

Route Optimizerille toimitettujen tilausten määrä nousi nopeasti 500 tuotteesta varastossa yli 1000: een. Teoriassa meidän pitäisi olla kunnossa.

Mutta emme olleet.

Algoritmimme ajonajat ja muistin käyttö hyppäsivät uskomattoman nopeasti - 1 minuutista ja 500 Mt: sta 10 minuuttiin ja 5 Gt. Kun testaamme sitä suurempien määrien suhteen, saavutimme vihdoin maksimiarvon - 2000 reittipisteelle moduuli käytti 25 Gt RAM-muistia.

Sitä ei voitu hyväksyä.

Periaatteessa meillä oli kaksi vaihtoehtoa:

  • Luo täysin uusi reittien optimoija, joka kykenee oletuksena tukemaan niin suuria määriä
  • Luo uusi algoritmi, joka toimii nykyisen toteutuksen päällä - luultavasti menetelmä, joka yhdistää tilaukset pienemmissä erissä, jotka sitten toimitetaan pääoptimointialgoritmille

Koska olemme käytännöllisiä (ja rakastamme myös rakentamista jo tehdyn suuren työn päälle), päätimme jatkaa toista vaihtoehtoa.

Kuinka luomme pienemmät erät?

Aloitetaan tunnetulla klusterointialgoritmilla - DBSCAN⁸.

Meillä on huipputekninen menetelmä, joka ryhmittelee maantieteelliset kohdat. Sillä on kuitenkin haittapuoli: jokaisella klusterilla on oltava sama säde.

Tätä me emme halua yhdestä yksinkertaisesta syystä: yksi 1 km: n säteellä oleva klusteri Tsim Sha Tsuissa voi sisältää 1000 tilausta, kun taas muut 1 km: n klusterit Pok Fu Lamissa ja Waterfall Bayssä voivat sisältää vain 3 tilausta.

Nämä klusterit olisivat todella tehottomia ja epätasaisia ​​...

Tsim Sha Tsuissa klusterin koko olisi liian suuri - meillä olisi liian paljon tilauksia yhdessä klusterissa. Mutta samaan aikaan joillakin muilla alueilla tämä säde ei riitä - klusterit olisivat liian pienet ja suhteellisen lähellä toisiaan olevat tilaukset olisivat erillisissä klustereissa.

Siksi päätimme käyttää muokattua lähestymistapaa - nimeltään ”rekursiivinen-DBSCAN”.

Rekursiivinen-DBSCAN

Se perustuu DBSCANin loistavuuteen, mutta antaa samalla mahdollisuuden kaivaa syvemmälle korkean reittipistetiheyden alueille ryhmittämällä etätilaukset yhteen.

Tilausluettelolle pyrimme löytämään säteen, jolle keskimääräinen reittipisteiden lukumäärä on suurin (mutta klustereiden lukumäärä on suurempi kuin min_no_custers). Teemme niin käyttämällä yksinkertaista binaarista hakualgoritmia.

Kun olemme löytäneet optimaalisen ratkaisun, "kirjoitamme" klustereihin, jotka ovat liian suuria, ja käytämme samaa logiikkaa, kunnes saavutamme pisteen, jolloin jokainen klusteri sisältää vähemmän kuin max_len_cluster.

Sitten kullekin klusterille suoritamme Googlen optimointityökaluilla kehittämämme Reittien optimointi -algoritmin. Toivottavasti tämä antaa meille samanlaisen tuloksen nopeammin ja käyttämällä vähemmän RAM-muistia.

Pseudokoodi on seuraava:

vertailukohtia

Olimme hyvin kiinnostuneita siitä, kuinka menetelmämme toimisi, mutta samalla huolissamme, että rekursio voi kestää erittäin kauan, joten algoritmemme ei ollut parempi kuin perustaso.

Siksi päätimme ensin katsoa ajoaikoja:

Kävi ilmi, että rekursiivinen dbscan-algoritmi ylitti huomattavasti Google Optimization Tools -menetelmän. Samanaikaisesti se ei eroa paljolti dbscan-menetelmän ajoista.

Pystyimme ajamaan dbscania enintään 2000 tilausta ja Google Optimization -työkaluja vain 1500 tilaukselle RAM-muistin käyttöongelman vuoksi: molemmat menetelmät murskattiin, kun muistin tarve ylitti 25 Gt.

Ajoajat ovat tärkeitä, mutta kiinnostaimme myös sitä, kuinka uusi algoritmimme suorittaa kokonaismatkan ja käytettyjen ajoneuvojen lukumäärän suhteen perusmenetelmään. Nämä kaksi kuvaajaa osoittavat, että:

Kuten näemme, rekursiivinen menetelmä seuraa tarkasti Google Optimization Tools -menetelmää sekä etäisyyden että ajoneuvojen lukumäärän suhteen. Samalla se ylittää dbscan-menetelmän.

Se tarkoittaa, että uusi algoritmimme on nopeampi kuin lähtöviiva ja löydettyjen ratkaisujen laatu on yhtä hyvä. Lisäksi suurin sallittu RAM-muisti on “vain” 1 Gt!

Me saimme sen!

DBSCAN vs. rekursiivinen-DBSCAN

Halusimme myös näyttää sinulle kuinka rekursiivinen dbscan toimii paremmin etäreittipisteissä.

Kuva 5: DBSCAN- ja rekursiivisten-DBSCAN-reittien vertailu. Tiedämme, että ne eivät vieläkään ole täydellisiä!

Yllä, vasemmalla puolella on kartta, joka osoittaa normaalin DBSCAN-algoritmin avulla löydetyn tehtävän. Voimme nähdä, että monet kuljettajista toimittavat vain yhden tilauksen - koska nämä tilaukset ovat ainoat erissä.

Oikealla puolella näemme, että rekursiivinen menetelmä käsittelee tätä asiaa melko hyvin, käyttämällä erilaisia ​​sädeitä eri alueille, se onnistuu löytämään ratkaisun, joka toimittaa kaikki tilaukset vain kolmella ajoneuvolla!

Tämä on täydellinen kuvaus siitä, kuinka rekursiivinen-dbscan-menetelmä on parempi käyttötapaamme varten ja miksi valitsimme sen.

Johtopäätös (alias TL; DR)

Tässä artikkelissa olemme esittäneet lähestymistapani Time Windows -sovellusten kapasiteettiajoneuvojen reititysongelmiin useiden reittipisteiden (jopa 5000) kanssa. Käyttämällä rekursiivista dbscan-menetelmää pystyimme vähentämään ajoja ja muistin käyttöä merkittävästi, säilyttäen samalla tulosten laadun kuin perustiedot Google Optimization Tools -menetelmässä.

Tämä algoritmi on suureksi avuksi operaatiotiimillemme, sillä se vähentää arkipäivän käsityön tunteja muutamiin minuutteihin suorittimen ajasta (ja ihmisen tarkistaa tulokset kaksinkertaisesti).

Tulevaisuus

Tiedämme, että työkalumme ei ole täydellinen.

Yksi pääongelmista on, että se on edelleen staattinen menetelmä, joka kerran ajaa ei päivitä itsensä, jos parempaa reittiä on käytettävissä tai jos tien tilanne muuttuu. Meillä on tässä tapauksessa muutama vaihtoehto, joista toinen toteuttaa geohaun, kuten Lyft, tai toinen, joka tulee kumppaniltamme - tutkimusyksikkö Big Data Analyticsissa PolyU Hongkongissa.

Tavoitteenamme on parantaa reittien optimointia siten, että se seuraa jatkuvasti kuljettajia ja lähettää hälytyksiä, jos kuljettajat ovat vaarassa olla tekemättä sitä ajoissa joidenkin pakettien kanssa - kaikki tämä tehdäksemme asiakkaillemme onnellisempia palvelumme kanssa.

Toivottavasti tämä artikkeli on antanut sinulle hyvän käsityksen ongelmista, joita käsittelemme GOGOVANissa. Jos se kuulostaa mielenkiintoiselta tai haluat vain tietää lisätietoja, älä epäröi ottaa yhteyttä.

Tulevaisuuden parannuksille on luonnollisesti paljon perustaa, mutta toivomme jakavan joitain lähestymistapojamme keskustelujen ja edistyksen käynnistämiseksi kiehtovalla alueella, jolla optimoidaan kysyntälogistiikkatoimintoja.
Jos haluat lisätietoja tietoryhmästämme, tutustu tietopäällikön artikkeliin täällä.
Etsimme jatkuvasti huipputasoa soveltavia operaatioita ja ML Research -taitoja. Ota yhteyttä jos olet kiinnostunut! (Paikan päällä ja kauko)
Viitteet:
[1] Lenstra, J. K. ja Kan, A. H. (1981), Ajoneuvojen reititys- ja aikataulu-ongelmien monimutkaisuus. Networks, 11: 221–227. doi: 10.1002 / net.3230110211
[2] Fukasawa, R., Longo, H., Lysgaard, J. et ai. Matematiikka. Ohjelmoida. (2006) 106: 491.
[3] Baldacci, R. & Mingozzi, A. Math. Ohjelmoida. (2009) 120: 347. https://doi.org/10.1007/s10107-008-0218-9
[4] Nagata Y. (2007) reuna-asennuksen ristikkäin kapasiteettiajoneuvojen reititysongelmaan. Julkaisussa: Cotta C., van Hemert J. (toim.) Evolutionary Computation in Combinatorial Optimization. EvoCOP 2007. Tietojenkäsittelytieteen muistiinpanot, osa 4446. Springer, Berliini, Heidelberg
[5] Bräysy, O. & Gendreau, M. Top (2002) 10: 211. https://doi.org/10.1007/BF02579017
[6] Tan X., Zhuo X., Zhang J. (2006) muurahaiskolonijärjestelmä ajoneuvojen reititysongelman optimoimiseksi aika-ikkunoissa (VRPTW). Julkaisussa: Huang DS., Li K., Irwin G.W. (eds) Laskennallinen älykkyys ja bioinformatiikka. ICIC 2006. Tietotekniikan luentomerkinnät, vol. 4115. Springer, Berliini, Heidelberg
[7] Xiaoyan Li (2015) Ajoneuvojen kapasiteettinen ajoneuvojen reititysongelma: Tapaustutkimus ruokavaliovalmisteiden noutoista voittoa tavoittelemattomissa organisaatioissa
[8] M. Ester, H. Kriegel, J. Sander ja X. Xu, ”Tiheyspohjainen algoritmi klusterien löytämiseksi meluisissa paikkatietokannoissa”, Proc. 2. Int. Conf. Tietojen etsiminen ja tiedon louhinta (KDD'96), 1996, s. 226–231.