Oplossen van het multi-depot gesloten-pad multiple traveling salesman-probleem met k-means++ hiërarchische clustering en neurale combinatorische netwerken

Slimmere routes voor veel chauffeurs

Van bestelwagens tot bezorgdrones en hulpkonvooien bij rampen: planners staan vaak voor een uitdaging — hoe kunnen meerdere voertuigen die vanuit verschillende locaties starten het werk van honderden of duizenden stops delen zonder brandstof of tijd te verspillen? Dit artikel presenteert een nieuwe manier om dat probleem te delen en te overwinnen, door een klassieke clusteringtruc te combineren met een modern neuraal netwerk, zodat computers binnen enkele seconden efficiënte routes kunnen uitzetten in plaats van minuten of uren.

De uitdaging van veel depots en veel chauffeurs

De studie pakt een veeleisende variant van het beroemde reizigersprobleem aan, waarbij er in plaats van één reiziger vele zijn, elk beginnend en eindigend bij een eigen basis. Samen moeten zij elke stad precies één keer bezoeken terwijl de totale afstand zo kort mogelijk blijft. Deze opzet weerspiegelt taken zoals het coördineren van vrachtwagenvloten, groepen robots of luchtige drones die het werk over een gebied verdelen. Omdat het aantal mogelijke routecombinaties explodeert naarmate steden en chauffeurs toenemen, worden exacte methoden te traag en hebben traditionele zoekmethoden vaak moeite of moeten ze kwaliteit inruilen voor snelheid.

Beperkingen van klassieke zoekmethoden en eenvoudige opsplitsing

Jarenlang hebben ingenieurs geleund op “metaheuristieken” zoals genetische algoritmen, mierenkoloniezoektocht en deeltjeszwermen. Deze bootsen natuurlijke processen na om vele kandidaat-routes te verkennen en ze geleidelijk te verbeteren. Ze zijn flexibel maar kennen twee grote nadelen: ze geven geen harde garanties over de kwaliteit van een oplossing en ze kunnen erg traag zijn voor grote kaarten, vooral wanneer elke nieuwe taak betekent dat de zoekopdracht opnieuw moet starten. Een populaire versnelling is eerst de steden te clusteren in regio’s met hulpmiddelen zoals k-means en vervolgens een kleiner probleem binnen elke cluster op te lossen. Hoewel deze split‑then‑solve-strategie helpt, wordt de uiteindelijke kwaliteit nog steeds beperkt door de onderliggende zoekmethode, en streven naar betere routes betekent doorgaans nog langere runtimes.

Een netwerk leren routeren, en het vervolgens helpen opschalen

Recente jaren brachten een ander idee: train een neuraal netwerk om direct goede routes uit te geven. Na training op veel voorbeeldindelingen van steden kan zo’n netwerk in één enkele voorwaartse stap een volledige tour voorstellen, vergelijkbaar met hoe een taalmodel een zin genereert. Deze neurale oplossers presteren indrukwekkend goed bij single-driverproblemen van bescheiden omvang, maar struikelen wanneer ze gevraagd worden veel chauffeurs te coördineren of wanneer het aantal steden veel groter is dan tijdens de training. De kernzet van de auteurs is zo’n neurale oplosser in een zorgvuldig tweeledig proces te plaatsen dat een enorme multi-chauffeurstaak herschikt in veel kleinere, vertrouwde subproblemen die het netwerk comfortabel aan kan.

Hoe de tweefasige methode werkt

De voorgestelde methode, KHC-NCN genoemd, begint met een verbeterde versie van k-means-clustering om steden toe te wijzen aan verschillende depots en chauffeurs. Als een resulterende regio te veel steden bevat voor de neurale oplosser om betrouwbaar aan te kunnen, splitst de methode die regio automatisch verder op in kleinere stukken, elk van een grootte die dicht bij wat het netwerk tijdens de training heeft gezien ligt. De coördinaten in elk stuk worden vervolgens geschaald naar een standaardvierkant zodat ze nog meer op de trainingsdata lijken. Het neurale netwerk produceert dan een route voor elk klein stuk. Ten slotte hecht een samenvoegstap deze subroutes aan elkaar tot een enkele lus voor elke chauffeur, waarbij eenvoudige geometrische regels worden gebruikt om stukken te verbinden op plekken waar dat de minste extra afstand toevoegt.

Snelheid en kwaliteit op echte benchmarkkaarten

De auteurs testen hun methode op een uitgebreide verzameling standaardkaarten uit een publieke benchmarkset die veel gebruikt wordt in routingsonderzoek. Zij vergelijken met vele gevestigde zoektechnieken en met zowel een toonaangevende handgemaakte oplosser als een andere neurale benadering. Over 44 testgevallen met verschillende kaartgroottes en aantallen chauffeurs vindt hun methode in bijna driekwart van de gevallen kortere totale routes en is daarbij ook dramatisch sneller, vaak met ordegroottes verschil. De methode houdt zich vooral goed wanneer het aantal steden oploopt tot honderden of duizenden, waar veel klassieke benaderingen vertragen of minder goede routes leveren.

Wat dit betekent voor routing in de echte wereld

In eenvoudige termen laat de studie zien dat het laten afhandelen van veel kleine, goed gevormde puzzels door een snel neuraal netwerk beter kan uitpakken dan veel tijd besteden aan één enorme puzzel. Door steden te clusteren op een manier die aansluit bij de comfortzone van het netwerk en vervolgens de deelscores slim te combineren, levert de methode routes die zowel kort als snel te berekenen zijn. Voor toepassingen zoals logistiek, multi-robotplanning en noodhulp wijst dit op een praktische manier om bijna in realtime routeplannen te krijgen die voertuigen en energie beter benutten dan veel bestaande hulpmiddelen.

Bronvermelding: Zhao, CS., Wong, LP. & Fung, C. Solving multi-depot closed-path multiple traveling salesman problem using k-means++ hierarchical clustering and neural combinatorial networks. Sci Rep 16, 15631 (2026). https://doi.org/10.1038/s41598-026-45824-3

Trefwoorden: voertuigroutering, neurale netwerken, clustering, optimalisatie, logistiek