Dynamic Vehicle Routing Problem with Prompt Confirmation of Advance Requests

Each language version is independently generated for its own context, not a direct translation.

Stel je voor dat je een super-dynamische taxi-dienst runt. Mensen bellen of appen en zeggen: "Ik wil om 14:00 uur hier weg en om 15:00 uur daar zijn." Jij hebt een vloot van busjes met een beperkt aantal zitplaatsen.

Deze paper beschrijft een slimme manier om dit te regelen, zodat je niet alleen snel antwoord geeft, maar ook zo min mogelijk mensen afwijst.

Hier is de uitleg, vertaald naar alledaagse taal met een paar leuke vergelijkingen:

1. Het Grote Probleem: De "Te Snelle" vs. De "Te Slimme"

Tot nu toe hadden planners twee opties, maar beide hadden een nadeel:

Optie A (De Haastige): Je zegt direct "Ja" of "Nee" zodra een verzoek binnenkomt.
- Voordeel: De klant krijgt direct geruststelling.
- Nadeel: Je bent te snel. Je zegt "Ja" tegen iemand, maar later blijkt dat je eigenlijk een ander verzoek had moeten accepteren dat veel beter paste. Je mist kansen omdat je niet verder kijkt dan je neus lang is.
Optie B (De Perfectie-zoeker): Je wacht even, kijkt naar alle verzoeken, en probeert de perfecte route te vinden voordat je iets zegt.
- Voordeel: Je vindt de allerbeste routes.
- Nadeel: De klant moet te lang wachten. "Wacht even, ik check het nog even..." is frustrerend.

De oplossing in deze paper: Een hybride aanpak. Je geeft direct antwoord (binnen een fractie van een seconde), maar je blijft in de achtergrond doorgaan met het verbeteren van de routes zolang er geen nieuw verzoek binnenkomt.

2. Hoe werkt het? De "Snelle Schatting" en de "Sluwe Chef"

Stel je dit proces voor als een restaurant:

Stap 1: De Snelle Schatting (Prompt Confirmation)

Wanneer een klant belt, moet de ober (ons algoritme) binnen een seconde zeggen: "Ja, we kunnen u meenemen" of "Nee, het is vol."

Hoe doen ze dit? Ze gebruiken een snelle "invoeg"-methode. Ze kijken naar de huidige route van de busjes en vragen zich af: "Kan ik deze nieuwe klant netjes tussen de bestaande stops inplakken zonder dat het chaotisch wordt?"
Ze doen dit razendsnel. Als het kan, zeggen ze "Ja". Zo krijgt de klant direct zekerheid.

Stap 2: De Sluwe Chef (Continual Optimization)

Zodra de ober het "Ja" heeft gezegd, is het werk niet klaar. De "Sluwe Chef" (een ander algoritme) gaat aan het werk in de keuken, terwijl de ober nieuwe gasten bedient.

Wat doet de Chef? Hij kijkt naar de routes die net zijn gemaakt en zegt: "Wacht even, als we deze stop hier en die stop daar verplaatsen, kunnen we straks misschien nog wel twee extra mensen meenemen."
Hij blijft de routes continu optimaliseren zolang er geen nieuw verzoek binnenkomt. Zodra de volgende klant belt, stopt de Chef met zijn hersenspinsels en gebruikt hij de beste versie van de route die hij tot nu toe heeft gevonden.
Dit is als een Anytime-algoritme: het kan op elk moment worden gestopt en geeft dan het beste antwoord dat tot dat moment beschikbaar was.

3. De "Kristallen Bol" (Reinforcement Learning)

Het moeilijkste deel is: Wanneer moet je "Ja" zeggen en wanneer "Nee"?
Als je nu "Ja" zegt tegen een klant die ver weg woont, heb je misschien geen plek meer voor een klant die straks belt en die veel dichterbij woont.

Om dit slim te doen, hebben de auteurs een AI-trainer gebruikt (Reinforcement Learning).

De Vergelijking: Stel je voor dat je een jonge kok traint. Je laat hem duizenden keren koken in een virtuele keuken. Soms zegt hij "Ja" en hij mist later een grote groep gasten. Soms zegt hij "Nee" en hij had die gasten wel kunnen meenemen.
De AI leert van deze fouten. Ze ontwikkelt een intuïtie (een "niet-korte-ziende" doelstelling). Ze leert niet alleen om nu een klant te bedienen, maar om te kijken naar de lange termijn: "Als ik deze klant nu accepteert, heb ik straks genoeg ruimte voor de drukte vanavond?"
Door deze AI te trainen, weet het systeem precies welke routes de meeste kans hebben om in de toekomst succesvol te zijn.

4. Wat is het resultaat?

De auteurs hebben dit getest met echte data van een openbaar vervoersbedrijf in de VS en met taxi-data uit New York.

Snelheid: Ze geven antwoord in 0,2 seconden. Dat is sneller dan je kunt knipperen.
Efficiëntie: Ze weigeren veel minder mensen dan de oude methoden.
- Vergelijking: Stel dat de oude methoden 10 mensen afwezen, dan weigert deze nieuwe methode er maar 1. Dat is een enorm verschil voor de klanttevredenheid.

Samenvatting in één zin

Deze paper introduceert een slim systeem dat direct antwoord geeft aan klanten (zoals een snelle ober), maar in de tussentijd slim blijft nadenken over hoe de routes het beste kunnen worden ingedeeld (zoals een strategische chef-kok), zodat er in de toekomst zoveel mogelijk mensen kunnen worden vervoerd.

Het is de perfecte balans tussen gemak voor de klant (direct antwoord) en efficiëntie voor de vervoerder (minder afwijzingen).

Each language version is independently generated for its own context, not a direct translation.

1. Probleemstelling

Het paper adresseert een specifiek gat in de bestaande literatuur over het Dynamisch Voertuig Routing Probleem (DVRP) voor op aanvraag gebaseerde vervoersdiensten (zoals microtransit en paratransit).

De Uitdaging: Vervoersinstanties moeten reisinformaties in real-time verwerken. Bestaande methoden vallen uiteen in twee categorieën die beide tekortschieten:
1. Methodes die snelle bevestiging geven (accepteren/afwijzen direct bij aankomst van een verzoek) maar geen mogelijkheid bieden om routes later te optimaliseren, wat leidt tot suboptimale dienstverlening.
2. Methodes die continue optimalisatie toepassen om routes te verbeteren, maar geen garantie geven voor snelle bevestiging of het garanderen dat alle geaccepteerde verzoeken ook daadwerkelijk worden bediend.
De Realiteit: In de praktijk willen passagiers onmiddellijk weten of hun vooraf geboekte reis (advance requests) geaccepteerd is, terwijl de dienstverlener de flexibiliteit nodig heeft om routes continu te verbeteren om het aantal geslaagde reizen te maximaliseren.
Het Doel: Een oplossing ontwikkelen die prompte bevestiging (binnen een fractie van een seconde) biedt voor elke aanvraag, terwijl tegelijkertijd continue optimalisatie van de routes plaatsvindt tussen de aankomst van nieuwe verzoeken, om zo de dienstverleningsgraad (service rate) te maximaliseren.

2. Methodologie

De auteurs stellen een nieuwe computationele aanpak voor die drie kerncomponenten integreert: een snelle zoekalgoritme, een "anytime"-algoritme en versterkende leer (Reinforcement Learning - RL).

A. Probleemformulering als Markov Beslissingsproces (MDP)

Het probleem wordt gemodelleerd als een MDP onder onzekerheid:

Toestand ( $s_t$ ): Omvat de locaties van voertuigen, de set van geaccepteerde verzoeken, de huidige routes (manifests) en het nieuw binnenkomende verzoek.
Actie ( $a_t$ ): Bestaat uit twee delen:
1. Beslissen of het nieuwe verzoek wordt geaccepteerd of afgewezen.
2. Het bijwerken van de routes voor alle voertuigen.
Beloning (Reward): 1 als een verzoek wordt geaccepteerd, 0 anders. Het doel is het maximaliseren van de cumulatieve beloning op lange termijn (dus de totale dienstverleningsgraad).

B. Twee-staps Computationele Aanpak

Prompte Bevestiging (Quick Insertion Search):
- Wanneer een verzoek arriveert, moet binnen seconden een beslissing worden genomen.
- Het algoritme zoekt naar een simpele invoeging van het nieuwe verzoek in de bestaande routes zonder de volgorde van eerdere verzoeken te veranderen of voertuigtoewijzingen te wijzigen.
- Dit beperkt de zoekruimte aanzienlijk, waardoor een oplossing in <1 seconde mogelijk is.
- De beslissing wordt niet gebaseerd op een myopische heuristiek, maar op een niet-myopische objectieve functie (zie hieronder).
Continue Optimalisatie (Anytime Algorithm):
- Tussen de aankomst van twee opeenvolgende verzoeken heeft het systeem tijd om de routes te verbeteren.
- Er wordt een Simulated Annealing-algoritme gebruikt als "anytime"-metaheuristiek. Dit betekent dat het algoritme op elk moment kan worden gestopt (bij de aankomst van het volgende verzoek) en de beste tot nu toe gevonden oplossing kan teruggeven.
- Operaties omvatten: Swap (verzoeken wisselen tussen voertuigen), Move (verplaatsen van een verzoek), Shift (volgorde aanpassen) en Reverse.

C. Versterkende Leer (Reinforcement Learning) voor Objectieve Functie

Een cruciale innovatie is het leren van een niet-myopische objectieve functie $Q(s, a)$ die de lange-termijn kans op het accepteren van toekomstige verzoeken maximaliseert.

Q-Learning: De auteurs gebruiken Q-learning om de actie-waarde functie te benaderen.
Feature Vectors: Omdat de staat complex en variabel van lengte is, worden staten omgezet in vaste feature-vectors (bijv. totale inactiviteitstijd, temporele beschikbaarheid, ruimtelijk-temporele beschikbaarheid via een grid).
Neurale Netwerken: Verschillende architecturen (MLP, KAN, CNN) worden getraind om $Q(s, a)$ te voorspellen.
Supervised Pre-training: Om de trainingstijd te verkorten, wordt eerst een simpele policy ( $\pi_0$ ) gesimuleerd om data te genereren voor supervised learning, waarna het model wordt fijngeslepen met RL.

3. Belangrijkste Bijdragen

Nieuwe Probleemformulering: Het introduceren van het DVRP met zowel prompte bevestiging als continue optimalisatie, een combinatie die in eerdere werken ontbrak.
Hybride Computationele Architectuur: De integratie van een snelle invoegingszoektocht voor real-time beslissingen en een anytime-algoritme voor achtergrondoptimalisatie.
Leren van een Niet-Myopische Doelfunctie: Het gebruik van RL om een $Q$ -functie te leren die de lange-termijn prestaties maximaliseert, in plaats van alleen de directe haalbaarheid te kijken.
Open Source Implementatie: De auteurs hebben hun simulatieomgeving en code open-source gemaakt.

4. Resultaten

De methode is geëvalueerd op twee datasets: een real-world microtransit-dataset uit een Amerikaanse stad en het NYC-taxi-dataset.

Dienstverleningsgraad (Service Rate) / Afwijzingspercentage:
- De voorgestelde methode ( $\pi^*$ ) verlaagt het afwijzingspercentage aanzienlijk ten opzichte van bestaande methoden (Google OR-Tools, Rolling Horizon, Monte Carlo VRP).
- Op de microtransit-dataset wordt het afwijzingspercentage teruggebracht tot ongeveer 1%, terwijl andere methoden aanzienlijk hoger liggen.
Bevestigingstijd:
- De bevestigingstijd voor een verzoek is gemiddeld 0,2 seconden (microtransit) en 1 seconde (NYC data). Dit is snel genoeg voor real-time interactie met passagiers.
- Ter vergelijking: De Rolling Horizon methode kan tot 122 seconden duren voor een beslissing, wat onpraktisch is voor directe bevestiging.
Ablatie Studies:
- Het tonen van het belang van continue optimalisatie: hoe langer het anytime-algoritme mag draaien tussen verzoeken, hoe lager het afwijzingspercentage.
- Het tonen van het belang van de geleerde $Q$ -functie: het vervangen van de geleerde functie door een simpele heuristiek leidt tot slechtere prestaties, wat aantoont dat de niet-myopische visie cruciaal is.

5. Betekenis en Conclusie

Dit paper biedt een praktische oplossing voor de uitdagingen van opkomende on-demand microtransit-diensten. Het bewijst dat het mogelijk is om:

Passagiers onmiddellijk zekerheid te geven over hun vooraf geboekte reizen (prompte bevestiging).
Tegelijkertijd de operationele efficiëntie te maximaliseren door continu de routes te optimaliseren, wat leidt tot een veel hoger percentage geslaagde reizen dan bestaande systemen.

De aanpak maakt het mogelijk om schaalbare, betrouwbare en efficiënte publieke vervoersdiensten te bouwen die zowel gebruikersvriendelijk zijn (door snelle feedback) als operationeel optimaal (door continue aanpassing). De resultaten suggereren dat deze methode een grote stap voorwaarts is ten opzichte van traditionele VRP-oplossers die vaak te traag zijn voor real-time bevestiging of te star zijn om routes dynamisch te verbeteren.