🤖 machine learning

Deep Reinforcement Learning solution for pickup and delivery routing problems with time window and capacity constraints

Dit artikel presenteert een nieuwe deep reinforcement learning-aanpak, gebaseerd op een aangepast JAMPR-model, die effectief middelgrote Pickup and Delivery-problemen met capaciteits- en tijdvensterbeperkingen (CPDPTW) in realtime oplost en snelle suboptimale oplossingen biedt voor grootschalige instanties van meer dan 200 knooppunten.

Oorspronkelijke auteurs: Andrew Soroka, Alex Meshcheryakov, Sergey Gerasimov

Gepubliceerd 2026-08-17

📖 4 min leestijd☕ Koffiepauze-leesvoer

CC BY 4.0

Oorspronkelijke auteurs: Andrew Soroka, Alex Meshcheryakov, Sergey Gerasimov

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Stel je voor dat je de kapitein bent van een vloot bestelwagens in een bruisende, steeds groeiende stad. Je taak is om pakketjes af te leveren en retourzendingen op te halen voor honderden klanten, maar je hebt een strikte set regels: je vrachtwagens kunnen maar een bepaalde hoeveelheid lading vervoeren, en elke klant heeft een specifieke tijdvenster wanneer hij thuis is om een pakketje te ontvangen. Als je te vroeg of te laat aankomt, of als je probeert te veel dozen in de achterkant van een busje te proppen, mislukt het plan. Dit is het "Pickup and Delivery Problem", een enorme puzzel die moeilijker wordt naarmate er meer mensen aan worden toegevoegd.

Decennialang hebben computers geprobeerd dit op te lossen door te fungeren als supersnelle rekenmachines, waarbij ze miljoenen mogelijke routes één voor één testen om het perfecte pad te vinden. Maar naarmate steden groeien en het aantal stops explodeert, raken deze rekenmachines vastgelopen. Ze doen er uren over om een route uit te rekenen die een mens in minuten kan schetsen, of erger nog, ze geven het volledig op en zeggen: "Ik kan dit niet oplossen." Hier komt een nieuw soort computerbrein in beeld: Deep Reinforcement Learning. Denk hierbij niet aan een rekenmachine, maar aan een videogame-personage dat leert door te spelen. In plaats van elke enkele mogelijkheid te berekenen, speelt het de bezorggame duizenden keren, waarbij het met elke ronde sneller en slimmer wordt en leert de beste zetten te herkelen zonder dat het elke optie hoeft te controleren.

In dit artikel besloten Andrew Soroka en zijn team van de Staatsuniversiteit van Moskou en het Instituut voor Ruimteonderzoek van de RAS dit "videogame-brein" te leren hoe het om moet gaan met de rommelige, echte regels van bezorging: beperkte vrachtwagenruimte en strikte tijdvensters. Ze namen een bestaand slim model genaamd JAMPR en gaven het een speciale upgrade om de "pickup and delivery"-regels te begrijpen, waarbij een vrachtwagen een pakketje moet ophalen bij één stop en het bij een andere stop moet afleveren, terwijl het tegelijkertijd de capaciteitslimieten beheert.

De onderzoekers ontdekten dat hun geüpgradede model een snelheidspiraat is voor kleine tot middelgrote steden (met 50 tot 20-0 stops). In deze scenario's kan de AI in de eerste paar seconden een bijna perfecte route uitspugen, waarmee het de traditionele "rekenmachine"-methoden verslaat die veel langer nodig hebben om zelfs maar te beginnen. Het is alsoals een bezorger die de stad zo goed kent dat hij onmiddellijk de beste route kan roepen, terwijl de ouderwetse computer nog steeds de kaart probeert te lezen.

Het verhaal wordt echter wat ingewikkelder wanneer de stad enorm groot wordt (400 tot 1.000 stops). Hier is de AI nog steeds de winnaar in de race qua snelheid en biedt het bijna onmiddellijk een "goed genoeg" oplossing, terwijl de traditionele methoden moeite hebben om in de eerste minuut überhaupt een geldige route te vinden. Maar de AI is nog niet perfect. Om de absoluut beste route voor deze gigantische steden te krijgen, moet de AI dagenlang "trainen", wat een lange tijd is. Zelfs na training is de uiteindelijke route van de AI voor de grootste problemen nog steeds ongeveer 20% duurder (in termen van afstand) dan de allerbeste oplossing die een traditionele methode uiteindelijk zou kunnen vinden als deze onbeperkte tijd zou krijgen. Sterker nog, zodra de optimalisatietijd van slechts een paar minuten verstrijkt, halen de traditionele methoden de AI in door betere routes te vinden die de AI niet kan evenaren zonder aanzienlijk meer training.

Het team heeft ook getest hoe robuust hun AI is wanneer de regels veranderen. Ze ontdekten dat de AI ongelooflijk betrouwbaar is binnen de specifieke testcondities die zijn gebruikt: het is de AI nooit mislukt om een oplossing te geven, zelfs niet wanneer de traditionele computer opgaf en "onmogelijk" zei voor dezelfde verdeling van problemen. Echter, als het stadsontwerp drastisch verandert — bijvoorbeeld van een willekeurige verspreiding van huizen naar een patroon waarbij iedereen in een nauwe cirkel woont — neemt de prestatie van de AI enigszins af, ho although het nog steeds de traditionele methoden verslaat tijdens het eerste uur van het oplossen.

Kortom, het artikel suggereert dat deze deep learning-aanpak een krachtig nieuw hulpmiddel is voor real-time logistiek. Het vervangt de oude methoden niet volledig, vooral niet voor de grootste, meest complexe puzzels waar het absolute perfecte antwoord nodig is. Maar voor situaties waarin je nu een snelle, betrouwbare oplossing nodig hebt — zoals een koeriersdienst die reageert op verkeer of een plotselinge piek in bestellingen — is deze AI een gamechanger, die een robuuste, snelle oplossing biedt waar traditionele tools vaak vastlopen of falen.

Technische Samenvatting: Deep Reinforcement Learning voor CPDPTW

Probleemdefinitie

Het artikel behandelt het Capaciteits- en Tijdvensterbeperkte Pickup and Delivery Problem (CPDPTW). Dit is een combinatorisch optimalisatieprobleem waarbij een vloot voertuigen goederen van specifieke ophaallocaties naar afleverlocaties moet transporteren. Het probleem wordt gekenmerkt door drie primaire real-world beperkingen:

Capaciteit: Voertuigen hebben een maximale volumelimit ( $Q$ ).
Tijdvensters: Klanten zijn alleen beschikbaar tijdens specifieke tijdsloten.
Pickup and Delivery (PDP): In tegenstelling tot standaard Vehicle Routing Problems (VRP), kunnen goederen worden opgehaald bij een depot of een klant en worden afgeleverd bij een andere klant, wat strikte sequentiebepaling vereist (ophalen vóór afleveren).

De auteurs merken op dat hoewel klassieke benaderingen (Mixed-Integer Programming, heuristieken) bestaan, deze moeite hebben met grootschalige instanties (bijv. >200 knopen) onder real-world beperkingen, vaak kampend met hoge computationele belastingen, een gebrek aan flexibiliteit bij het verwerken van nieuwe beperkingen, of het niet vinden van haalbare oplossingen binnen een redelijke tijdspanne.

Methodologie

De auteurs stellen een Deep Reinforcement Learning (DRL) benadering voor op basis van een aangepaste JAMPR (Joint Attention Model for Pickup and Routing) architectuur.

Modelarchitectuur

Basis: Het model bouwt voort op het JAMPR-framework, dat het Attention Model (AM) en de Pointer Networks uitbreidt. Het maakt gebruik van een encoder-decoder structuur met self-attention mechanismen.
Toestandsrepresentatie: Het probleem wordt gemodelleerd als een Markov Decision Process (MDP).
- Encoder: Encodeert knoopkenmerken (coördinaten, vraag, tijdvensters) in verborgen embedding vectoren.
- Context ( $C(t)$ ): Bevat de probleemgrafiek-embedding, depot index, de laatst toegevoegde knoop en de resterende voertuigcapaciteit.
- Uitgebreide Context: Om PDP en tijdvensters te verwerken, incorporeert het model specifieke embeddings voor geconstrueerde routes en voertuigkenmerken (resterende capaciteit, huidige knoop, huidige tijd) in volledig verbonden neurale netwerken. Dit maakt de parallelle constructie van meerdere routes mogelijk.
Actieruimte: De actie wordt gedefinieerd als een paar $(r, i)$ , dat de selectie van een knoop $i$ vertegenwoordigt om toe te voegen aan een actieve route $r$ . Een feasibility mask (haalbaarheidsmasker) wordt toegepast om ervoor te zorgen dat beperkingen (capaciteit, tijdvensters en PDP-volgorde) niet worden geschonden.
Policy: De decoder berekent attention scores voor haalbare knopen. Deze scores worden gebruikt voor greedy selectie of gesampled via een softmax-distributie tijdens de training.

Aanpassingen voor CPDPTW

De auteurs hebben specifieke aanpassingen geïntroduceerd in het standaard JAMPR-model om de PDP-natuur van het probleem aan te pakken:

PDP Masking: Een extra masker werd toegevoegd aan de feasible() functie om de aflevervolgorde-beperkingen af te dwingen (een ophaalactie moet plaatsvinden vóór de bijbehorende aflevering).
Soft Constraint Handling: Omdat de auteurs erkennen dat het vinden van een 100% haalbare oplossing voor alle klanten soms onmogelijk is in harde formuleringen, hebben zij een SOFT setting geadopteerd. De uiteindelijke kostenfunctie is een lineaire combinatie van de totale afgelegde afstand en het aantal gemiste klanten (respectievelijk gewogen 13:10). Dit zorgt ervoor dat het model altijd een oplossing produceert, zelfs als deze incompleet is.

Training en Data

Data Generatie: Instanties werden gegenereerd op basis van de Solomon R201 distributie. Probleemgroottes varieerden van 50 tot 1000 knopen. Vrachtwagencapaciteiten en tijdshorizonten werden geschaald volgens de probleemgrootte.
Training: Modellen werden getraind met reinforcement learning met early stopping criteria (geen kostenreductie over 10 stappen). De trainingstijden varieerden aanzienlijk per probleemgrootte, variërend van 3 uur voor 50-knopen problemen tot meer dan 336 uur voor 1000-knopen problemen.
Baseline: Het voorgestelde model werd vergeleken met Google OR-Tools, een standaard heuristische solver die wordt gebruikt in real-world toepassingen.

Belangrijkste Resultaten

De prestaties werden geëvalueerd over drie categorieën van probleemgrootte:

1. Kleine omvang (50 knopen)

Prestaties: Het getrainde JAMPR-model leverde een snelle optimale oplossing, waarbij het de heuristische oplossing versloeg in kosten tijdens de eerste seconden van de optimalisatie.
Kosten: Naarmate de optimalisatietijd toenam, benaderden de resultaten van het JAMPR-model geleidelijk die van OR-Tools. Na uitgebreide training (723 epochs), verschilden de uiteindelijke resultaten van de OR-Tools baseline met niet meer dan 0,3%.
Haalbaarheid: JAMPR loste 100% van de instanties op, terwijl OR-Tools in toenemende mate niet in staat was oplossingen te vinden naarmate de complexiteit van het probleem groeide.

2. Middelgrote omvang (100–200 knopen)

Prestaties: Het model leverde snelle suboptimale oplossingen die superieur waren aan metaheuristieken in de eerste seconden van de optimalisatie (15–200% betere kosten dan OR-Tools).
Convergentie: Hoewel de prestaties van het model snel een plateau bereikten, presteerde het consistent beter dan OR-Tools qua snelheid. OR-Tools had aanzienlijk langere optimalisatietijden nodig om vergelijkbare kostenniveaus te benaderen.
Haalbaarheid: JAMPR behield een faleningspercentage van 0% en loste alle instanties op, terwijl OR-Tools er niet in slaagde haalbare oplossingen te vinden voor een groeiend percentage instanties naarmate de omvang toenam.

3. Grote omvang (400–1000 knopen)

Prestaties: Voor hoogdimensionale problemen leverde het neurale model nog steeds een snelle suboptimale oplossing die aanzienlijk beter was dan OR-Tools in de eerste 60 seconden (waar OR-Tools vaak nog geen enkele oplossing had gevonden).
Beperkingen: Naarmate de optimalisatietijd toenam, haalden metaheuristieken (OR-Tools) uiteindelijk het neurale model in. Het uiteindelijke resultaat van JAMPR met maximale optimalisatietijd verloor ongeveer 20% van de padkosten vergeleken met de metaheuristiek.
Trainingskosten: Training voor grote instanties was computationeel duur (bijv. 336 uur voor 1000 knopen), wat de mogelijkheid beperkte om het model volledig te optimaliseren binnen een redelijke tijd op enkele GPU's.

Robuustheidsanalyse

Distributieverschuiving: Het model toonde robuustheid tegen veranderingen in datadistributie. Bij testen met een mix van uniforme en normale distributies, behield het model zijn vermogen om snelle suboptimale oplossingen te bieden, zelfs met tot 25% van de data uit de nieuwe distributie.
Metrische Invariantie: De prestaties van het model bleven consistent wanneer de afstandsberekeningen werden gewisseld van Euclidische naar Manhattan-metrieken.

Betekenis en Claims

Het artikel claimt de eerste succesvolle toepassing te zijn van een deep reinforcement learning benadering (specifiek een aangepast JAMPR-model) voor het oplossen van het CPDPTW-probleem.

De auteurs benadrukken drie belangrijke bijdragen:

Snelheid vs. Kwaliteit Trade-off: Het model biedt een snelle suboptimale oplossing (in tienden van seconden) die vaak superieur is aan klassieke heuristieken in de beginfase van de optimalisatie. Dit is bijzonder waardevol voor dynamische systemen met strikte tijdslimieten.
Robuustheid en Haalbaarheid: In tegenstelling tot traditionele metaheuristieken, die mogelijk geen enkele haalbare oplossing vinden voor grote of complexe instanties, garandeert het neurale model een oplossing (zelfs als deze gedeeltelijk is, onder de SOFT setting waarbij gemiste klanten worden bestraft) voor alle probleeminstanties, ongeacht de omvang.
Schaalbaarheid van de Bestaan van Oplossingen: Het faalpercentage van het neurale model blijft nul over alle geteste groottes, terwijl het faalpercentage van OR-Tools toeneemt met de probleemgrootte.

De auteurs concluderen dat hoewel deep RL-modellen momenteel aanzienlijke trainingstijd vereisen voor grootschalige problemen en mogelijk nog niet de uiteindelijke optimaliteit van metaheuristieken kunnen evenaren voor zeer grote instanties, ze een veelbelovende richting vormen voor real-time routingoptimalisatie waar snelheid en de existentie van een oplossing cruciaal zijn. Ze suggereren dat toekomstig werk zich kan richten op het combineren van deze RL-modellen met Mixed-Integer Programming (MIP) solvers of het gebruik van geleerde partitioneringspolicies om hoogdimensionale problemen effectiever aan te pakken.