Routebepaling
Van theorie naar praktijk
De snelheid en efficiëntie waarmee je producten naar klanten vervoert, kan een groot competitief voordeel zijn. Om die snelheid en efficiëntie te bekomen, is het bepalen van de beste vervoersroute essentieel. AI kan je daarbij helpen, rekening houdende met de specifieke doelen en beperkingen van jouw bedrijf. Zo creëer je makkelijker meer efficiënte door o.a. de transporttijd en –afstand te verkorten, vrachten optimaal toe te wijzen aan voertuigen, betere levertijden voor je klanten te bekomen, en meer kosteffectieve routes te bepalen.
Toepassingen
Met behulp van een goede routebepaling, kun je snel en efficiënt producten naar je klanten vervoeren. Traditioneel betekent "snel en efficiënt” de kortste afstand of snelste levertijd. Doordat AI echter een hele reeks verschillende factoren in rekening kan nemen, hoeft het niet bij die definitie te blijven.
Neem het vervoeren van voeding. Verschillende types voeding hebben al snel verschillende vervoersvereisten. Zo vervoer je diepvriesproducten bij een andere temperatuur dan een pakje koekjes. Wanneer je in dit voorbeeld een traditionele routebepaling gaat doen met één vaste omgevingstemperatuur, verlies je heel wat efficiëntie. Met AI kun je makkelijker dergelijke afwijkende factoren in je routeberekeningen toevoegen. Overigens hoeft die berekening niet altijd terug te komen op snelheid of efficiëntie, maar kun je ook kijken welke ecologische voetafdruk je levering met zich meebrengt of hoe brandstofzuinig je levering is.
Als je over historische data omtrent je productieproces beschikt, kun je die data ook terugkoppelen naar je routebepaling. Verwerkingstijden, installatietijden, storingen, etc. zijn uiteindelijk allemaal belangrijke factoren om routes te bepalen. Wanneer je dergelijke factoren in rekening brengt met behulp van AI, kun je een enorm voordeel in snelheid en kwaliteit bekomen ten opzichte van manuele routebepaling. Zo gebeurt het bijvoorbeeld wel eens dat vrachtwagens moeten stilstaan voor onderhoud. Door middel van routebepaling te combineren met predictief onderhoud, loop je veel minder risico om een tekort aan vrachtwagens voor leveringen te hebben.
Wat ook vaak gebeurt, is dat je een route uitgestippeld hebt, maar deze dan niet kun volgen door onvoorziene omstandigheden. Denk bijvoorbeeld aan wijzigingen in klanten hun tijdsvenster. Zo kun je op basis van historische data van leveringen aan klanten dergelijke beperkingen of wijzigingen op voorhand anticiperen. Is een bepaalde klant vaak onvoorzien afwezig tijdens leveringen rond de lunchtijd? Met AI kun je dit anticiperen en je routebepaling daarop afstellen. Ook kan je met AI inspelen op een heel reeks andere onvoorziene omstandigheden zoals verkeersongevallen en een laag brandstofgehalte, vaak in real-time.
Nog een moeilijkheid om de optimale route te bepalen is wanneer je een hele reeks vrachtwagens in dienst hebt, meerdere opslaglocaties benut, of complexere logistieke methoden zoals cross docking gebruikt. In deze complexere gevallen wordt routebepaling al snel onoverzichtelijk. Binnen het domein van AI, bestaan er echter algoritmen die specifiek gemaakt zijn voor deze probleemstellingen. Swarm Intelligence, Artificial Bee Colony and Cuckoo Search algoritmen zijn bijvoorbeeld reeds gebruikt voor het optimaliseren van verse voeding levering rekeninghoudende met een vloot vrachtwagens. Dat zijn natuurlijk allemaal verwarrende benamingen, maar belangrijk om te onthouden is dat in de wereld van AI reeds verschillende algoritmen bestaan om bestaande, complexe problemen rond routebepaling aan te pakken. In het geval van meerdere opslaglocaties, past swarm intelligence algoritme in combinatie met een genetisch algoritme goed. Voor cross docking past een genetisch algoritme op zich goed.
Tot slot is de zogenaamde “last mile” een belangrijk concept geworden voor het leveren van producten. De producten tot de deur van klanten te brengen, is vaak kostenintensief. Tegelijkertijd verwachten klanten dit vaak wel, en als het kan de dag na hun bestelling. Alle hulp om dit proces te optimaliseren is dus welkom, en ook hier kan AI een rol spelen. Cainiao, een dochteronderneming van de Chinese e-commerce reus Alibaba, voert proefprojecten uit om met een kleine robot die zelf routebepaling doet producten te leveren aan klanten. Jingdong, een ander Chinees e-commerce bedrijf, alsook Mercedes-Benz doen gelijkaardige proefprojecten, maar dan met onbemande drones. De grote levervoertuigen rijden dan tot een bepaald punt, waarna de drones de “last mile” overnemen. Voor meer informatie over drones, zie de toepassing Robotica.
Vereisten
Data
- Gedigitaliseerd netwerk met plaatsen en connecties tussen plaatsen
- ~Inclusief tijd/kost voor een verplaatsing tussen A en B
- Historische dataset met verplaatsingen
- ~Timestamp, benodigde tijd, kost etc.
- Data betreffende capaciteit en vraag
- ~Capaciteit en andere eigenschappen van voertuigen (features, snelheid...)
- ~Historische vraag incL. eventuele vereisten (uiteindelijk te mappen op features van voertuigen)
- ~Eventueel eigenschappen over rijgedrag van de bestuurder
- Optioneel: context-specifieke informatie, weersinformatie, relevante gebeurtenissen etc.
Hardware
- Standaard capaciteit voor dataopslag en data verwerking
- ~Noot: je hebt uiteraard ook voertuigen nodig, maar deze spelen enkel een rol tijdens de uitvoering, niet tijdens de planning
Algoritme
- Optimalisatie-algoritmes voor shortest path finding
- ~Deterministic: Constraint programming
- ~Meta-heuristic: Genetic algorithm, Particla Swarm Optimization, Ant Colony Optimization, Artificial Bee Colony...
- ~Auctioneering-based assignment
Aandachtspunten
- Kies de juiste doelstelling voor je optimalisatie. Het is belangrijk om je case duidelijk te definiëren zodat je kan vastleggen wat je exact wenst te optimaliseren. Het optimaliseren van de route van 1 voertuig met een vastgelegd aantal stops (maar een onduidelijke volgorde), is een ander probleem dan het optimaliseren van de verdeling van N stops over M voertuigen die dan elk een optimale route moeten krijgen – en dat dan bijvoorbeeld zonder elkaar in de weg te rijden.
- Extra dynamiek zorgt voor extra complexiteit. Een extra complexiteit stelt zich wanneer routes nog tijdens de uitvoering kunnen veranderen omdat er orders toegevoegd worden. Dit moet opgelost worden door ofwel (1) een herberekening van de routes gegeven de huidige posities van de voertuigen en de stops die reeds afgelegd zijn ofwel (2) door op voorhand in enige mate rekening te houden met potentiële vraag van verschillende locaties.
- Simpele oplossingen zijn soms de beste oplossingen voor complexe problemen. In bepaalde gevallen kan je zelfs overschakelen naar een rittenschema dat gelijkaardig is aan hetgeen gebeurt bij openbaar vervoer of De Post, waarbij vaste ritten gereden worden die dagelijks een variërend volume moeten verwerken. In dit geval maak je geen dagelijkse optimalisatie op basis van gekende orders, maar ga je een schema optimaliseren op basis van de historische of voorspelde vraag per area/locatie.
- Shortest path finding is een erg complex probleem. Het bepalen van de optimale route is een probleem dat we “NP hard” noemen. Dit wil zeggen dat we tot op heden geen techniek kennen waarmee we op een efficiënte manier1 tot een gegarandeerd optimale oplossing komen. Momenteel bekende technieken produceren enkel een “best effort” waarbij de aangeboden oplossing beter is dan de verkende alternatieven. Deze best effort is vaak beter dan hetgeen je manueel zou kunnen bepalen en wordt dus over het algemeen beschouwd als een toegevoegde waarde.
- Externe beperkingen maken de oplossing nog complexer. In sommige gevallen moet er rekening gehouden worden met maximaal af te leggen afstand en eventuele rusttijden met al dan niet refueling of recharging points voor de voertuigen
- Routebepaling is niet hetzelfde als een zelfrijdend systeem. Zelfsturend rijgedrag waarbij het voertuig correcties uitvoert op de route om schade of vertraging te vermijden valt buiten de scope van deze toepassing.
- Gebruik bestaande oplossingen en/of ervaren vendors. Het bouwen van een eigen optimalisatie-oplossing is niet-triviaal in vergelijking met bijvoorbeeld het bouwen van een eigen model voor salesvoorspelling. Samenwerking met vendors is ten zeerste aangeraden om tot een operationele oplossing te komen.
Stappenplan
- Definiëren van use case en doelstellingen (m.a.w. optimaliseer je tijd, kost, energieverbruik, idle time, gelijke verdeling van werklast....)
- Definiëren van beperkingen waaraan oplossingen dienen te voldoen (beperkingen in capaciteit, voertuig-features, time windows...)
- Verkennen van providers van routing algoritmes
Interessante links
- Route Optimization is Being Revolutionized Thanks to AI
- A comprehensive survey on the Multiple Traveling Salesman Problem: Applications, approaches and taxonomy.
- The vehicle routing problem: State of the art classification and review.
- A survey of the generalized assignment problem and its applications.
Partners
Hulp nodig bij de implementatie van deze AI-toepassingen?
Ontdek hier enkele technologiepartners.