Construct, Merge, Solve & Adapt with Reinforcement Learning for the min-max Multiple Traveling Salesman Problem

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

De Probleemstelling: De Uitdaging van de Koeriers

Stel je voor dat je een grote pizzabakkerij runt met één centrale keuken (het depot). Je hebt m koeriers (de verkopers) die pizza's moeten bezorgen bij n verschillende huizen in de stad.

Elke koerier moet:

Starten bij de keuken.
Een aantal huizen bezoeken (elk huis precies één keer).
Terugkeren naar de keuken.

Het doel is niet alleen om de kortste totale afstand te vinden, maar om eerlijkheid te garanderen. Je wilt voorkomen dat één koerier een enorme route heeft (bijvoorbeeld urenlang rijden) terwijl een ander maar een paar straten aflegt. Je wilt de langste route van allemaal zo kort mogelijk maken. Dit heet het Min-Max Multiple Traveling Salesman Problem.

Het probleem is dat dit wiskundig ontzettend moeilijk is. Als je 100 huizen en 10 koeriers hebt, zijn er meer mogelijke routes dan er atomen in het heelal zijn. Computers kunnen dit niet zomaar "uitrekenen".

De Oplossing: Een Slimme Mix (RL-CMSA)

De auteurs van dit paper hebben een nieuwe methode bedacht, genaamd RL-CMSA. Je kunt dit zien als een slimme, lerende projectmanager die een team van koeriers aanstuurt. De methode werkt in een cyclus van zes stappen, die we kunnen vergelijken met het organiseren van een grote uitjesdag.

1. Bouwen (Construct) – De "Gokjes"

De manager maakt eerst een paar mogelijke plannen. Maar hij doet dit niet willekeurig. Hij gebruikt een soort intuïtie (Reinforcement Learning).

De Analogie: Stel je voor dat je vrienden in groepjes wilt verdelen voor een spel. Je weet dat mensen die dicht bij elkaar wonen, vaak in hetzelfde groepje zitten. De manager leert dit patroon: "Als huis A en huis B vaak samen in een goed plan zaten, dan is de kans groot dat ze weer bij elkaar horen." Hij gebruikt deze kennis om nieuwe, veelbelovende routes te "gokken".

2. Samenvoegen (Merge) – De "Selectie"

Nu heeft hij veel verschillende routes gegenereerd. Hij gooit ze niet weg, maar legt ze in een pool (een verzameling).

De Analogie: Het is alsof hij alle mogelijke stukken van een puzzel op tafel legt. Hij houdt alleen de beste stukken bij en gooit de slechte weg. Als twee stukken precies hetzelfde zijn, houdt hij alleen het kortste stukje over.

3. Oplossen (Solve) – De "Wiskundige Puzzel"

Nu komt de kracht van de computer. De manager neemt de beste stukken uit de pool en probeert ze met een wiskundige formule (een MILP-oplosser) perfect aan elkaar te plakken.

De Analogie: Het is alsof je een enorm legpuzzel hebt, maar je mag alleen de stukken gebruiken die je al op tafel hebt liggen. De computer zoekt razendsnel naar de perfecte manier om deze specifieke stukken tot één groot plaatje te maken.

4. Verbeteren (Improve) – De "Finishing Touch"

Soms is het plaatje net niet perfect. Misschien zit er een koerier die een stukje te ver moet rijden. De manager maakt kleine aanpassingen: hij verplaatst een huis van de ene route naar de andere, of wisselt twee huizen in.

De Analogie: Het is als het bijspijkeren van een tent. Je ziet dat één paal scheef staat, dus je schuift hem een beetje op zodat de tent strakker staat.

5. Leren (Learn) – De "Ervaring"

Dit is het slimme deel. Als de manager een heel goed plan heeft gevonden, onthoudt hij: "Hey, deze huizen zaten samen in een goed plan! De volgende keer moet ik ze vaker bij elkaar zetten."

De Analogie: Het is als een speler in een computerspel die een "high score" haalt. Hij onthoudt welke knoppen hij precies op dat moment drukte, zodat hij het de volgende keer weer kan doen.

6. Aanpassen (Adapt) – De "Verjonging"

Oude plannen die al lang niet meer gebruikt zijn, worden verwijderd uit de pool. Nieuwe, frisse plannen krijgen een kans.

De Analogie: Het is als een team dat regelmatig nieuwe leden aannemt en oude, niet-functionerende leden laat gaan, zodat het team altijd up-to-date en scherp blijft.

Wat vonden ze?

De auteurs hebben hun nieuwe methode getest tegen de beste bestaande methode (een zogenaamd "Hybride Genetisch Algorithm").

Het resultaat: Hun nieuwe methode (RL-CMSA) werkt beter, vooral als het aantal huizen en koeriers groot wordt.
De snelheid: Het is vaak sneller dan de oude methode.
De stabiliteit: De oude methode gaf soms heel goede resultaten en soms slechte (afhankelijk van het geluk). De nieuwe methode geeft consistent goede resultaten. Het is alsof de nieuwe manager altijd een solide plan heeft, terwijl de oude manager soms een briljant plan heeft en soms een ramp.

Waarom werkt het zo goed?

De auteurs leggen uit dat hun methode slim omgaat met de "verwarring" van de routes.

Als je weinig koeriers hebt, zijn de routes heel lang en moeilijk te combineren. Hier werkt de nieuwe methode iets minder goed.
Maar als je veel koeriers hebt (wat vaak het geval is in moderne bezorgdiensten), worden de routes korter. De computer kan dan makkelijker zien welke stukjes bij elkaar horen. De nieuwe methode gebruikt dit om razendsnel de perfecte verdeling te vinden.

Conclusie

Kortom: De auteurs hebben een slimme, lerende computerprogramma bedacht dat beter in staat is om grote bezorgproblemen eerlijk en efficiënt op te lossen dan de huidige stand van de techniek. Het combineert het beste van twee werelden: het creatieve "gokken" van een menselijke planner en de rekenkracht van een wiskundige computer.

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

Titel: Construct, Merge, Solve & Adapt met Versterkingsleer voor het min-max Multiple Traveling Salesman Probleem

Auteurs: Guillem Rodríguez-Corominas, Maria J. Blesa, en Christian Blum.

1. Het Probleem

Het paper richt zich op het Multiple Traveling Salesman Problem (mTSP), een uitbreiding van het klassieke TSP waarbij $m$ tours moeten worden gevonden die allemaal starten en eindigen bij een gemeenschappelijk depot, waarbij elke klant precies één keer wordt bezocht.

Specifiek behandelt de studie de min-max variant op symmetrische grafieken met één depot.

Doel: Het minimaliseren van de lengte van de langste tour onder de $m$ tours.
Toepassing: Deze doelstelling is cruciaal voor het balanceren van werklasten in scenario's zoals leveringen op de "last mile" met identieke voertuigen, gecoördineerd patrouilleren met meerdere robots, UAV-missieplanning en technici-routering.
Complexiteit: Het probleem is NP-hard. Exacte algoritmen schalen slecht voor grote instanties, waardoor metaheuristieken noodzakelijk zijn.

2. Methodologie: RL-CMSA

De auteurs stellen een hybride aanpak voor genaamd RL-CMSA (Reinforcement Learning - Construct, Merge, Solve & Adapt). Dit is een iteratief framework dat bestaat uit zes fasen, zoals geïllustreerd in Figuur 1 van het paper:

A. Construct (Opbouwen)

In deze fase worden $n_{solutions}$ kandidaat-oplossingen gegenereerd via een probabilistisch proces met twee stappen:

Clustering: Steden worden gegroepeerd in $m$ $m$ clusters (één per voertuig). Dit gebeurt niet willekeurig, maar wordt geleid door Q-waarden (geleerde kansen) die de compatibiliteit van stedenpaars aangeven.
- Centra worden geselecteerd met een bias op basis van afstand en Q-waarden.
- Steden worden toegewezen aan clusters op basis van een kostfunctie die rekening houdt met de afstand, de gemiddelde Q-compatibiliteit met bestaande leden van de cluster, en een schatting van de impact op de maximale tourlengte.
Route: Voor elke cluster wordt een route geconstrueerd met een snelle "greedy insertion" heuristiek, gevolgd door lokale zoekoptimalisatie (2-opt en Or-opt) binnen de route.

B. Merge (Samenvoegen)

De gegenereerde routes worden toegevoegd aan een pool van kandidaat-routes ( $R_{cand}$ ).

Duplicaatverwijdering: Routes die dezelfde steden bezoeken, worden gehasht; alleen de kortste route per unieke stedenverzameling wordt bewaard.
Pruning: Routes die langer zijn dan de huidige beste maximale tourlengte worden verwijderd om de pool compact te houden.

C. Solve (Oplossen)

Een Mixed Integer Linear Programming (MILP) sub-probleem (set-covering formulering) wordt opgelost met de CPLEX solver.

Doel: Selecteer precies $m$ routes uit de pool $R_{cand}$ zodat alle steden worden bedekt en de lengte van de langste geselecteerde route wordt geminimaliseerd.
Dit combineert exacte optimalisatie met de diversiteit van de gegenereerde routes.

D. Improve (Verbeteren)

De oplossing uit de MILP-fase (die mogelijk overlappende steden bevat) wordt gefixt en verder geoptimaliseerd:

Remove: Verwijder dubbele steden uit routes om een geldige oplossing te garanderen.
Shift: Verplaats een stad van de ene route naar een andere om de totale lengte te verkleinen of de maximale lengte te reduceren.
Swap: Wissel twee steden tussen verschillende routes uit.

Deze operaties gebruiken een probabilistische selectie (roulette wheel) gebaseerd op de winst ( $\Delta$ ), waarbij zowel verbetering van het hoofddoel (min-max) als secundaire doelen (totale lengte) worden gewogen.

E. Learn (Leren)

De Q-waarden worden bijgewerkt op basis van de kwaliteit van de gevonden oplossingen:

Als een paar steden $\{i, j\}$ samen voorkomt in een route van de beste oplossing ( $R_{best}$ ), wordt de Q-waarde verlaagd (versterkt: ze moeten vaker samen in een cluster).
Als ze niet samen voorkomen, wordt de Q-waarde verhoogd (afgeraden).
Dit sturen de clustering in de volgende iteraties naar veelbelovende gebieden.

F. Adapt (Aanpassen)

De pool $R_{cand}$ wordt beheerd via een verouderingsmechanisme (ageing):

Routes uit de nieuwe beste oplossing krijgen leeftijd 0.
Routes die niet in de beste oplossing staan, krijgen een leeftijd +1.
Routes die een maximale leeftijd ( $age_{max}$ ) bereiken, worden verwijderd. Dit zorgt voor een dynamische pool die zich aanpast aan de zoekrichting.

3. Belangrijkste Bijdragen

Hybride Framework: Integratie van versterkingsleer (Q-learning) in het CMSA-framework om de constructiefase te sturen, wat een balans biedt tussen exploratie en exploitatie.
Probabilistische Clustering: Een nieuwe methode om steden te clusteren die niet alleen op geometrische afstand, maar ook op geleerde co-occurrence-statistieken (Q-waarden) baseert.
Exacte Sub-probleem Oplossing: Het gebruik van een MILP-oplosser om de beste combinatie van routes te vinden uit een beperkte, maar kwalitatief hoogwaardige pool, in plaats van alleen te vertrouwen op lokale zoektochten.
Statistische Validatie: Uitgebreide experimenten met statistische tests (Wilcoxon signed-rank test) om de superioriteit te bewijzen.

4. Resultaten

De prestaties van RL-CMSA werden vergeleken met de state-of-the-art Hybrid Genetic Algorithm (HGA) [5] op twee soorten benchmarks:

Willekeurige instanties: Genereerd in een cirkel met het depot in het midden (om extreme gevallen te vermijden).
TSPLIB instanties: Bekende gestructureerde benchmarks (eil51, berlin52, eil76, rat99).

Kernbevindingen:

Kwaliteit: RL-CMSA presteert over het algemeen beter dan HGA, vooral bij het vinden van oplossingen met een lagere gemiddelde doelwaarde en een hogere frequentie van "beste gevonden oplossingen" (#b).
Schaalbaarheid: De prestatieverbetering van RL-CMSA wordt groter naarmate het aantal steden ( $n$ $n$ ) en het aantal verkopers ( $m$ $m$ ) toeneemt.
- Voor kleine $m$ (weinig routes, lange tours) presteert HGA soms beter of gelijkwaardig, omdat het combineren van lange routes moeilijker is voor de MILP-fase.
- Voor grote $m$ (veel routes, korte tours) domineert RL-CMSA duidelijk omdat de MILP-fase effectiever kan combineren.
Snelheid: RL-CMSA is over het algemeen sneller dan HGA voor het vinden van de beste oplossing, vooral bij $n=50$ en $n=100$ . Bij $n=200$ en grote $m$ is het ook sneller.
Robuustheid: Een analyse van de "Search Trajectory Network" (STN) toont aan dat RL-CMSA sneller convergeert naar een hoogwaardig zoekgebied en consistentere resultaten levert, terwijl HGA meer diversiteit toont maar minder vaak de absolute beste oplossing bereikt.
Statistiek: De gepaarde statistische tests bevestigen dat RL-CMSA significant superieur is in de meeste scenario's (vooral voor $n=100$ en $n=200$ met $m \ge 5\%$ ).

5. Betekenis en Conclusie

Het paper demonstreert dat het combineren van versterkingsleer met exacte optimalisatie binnen een iteratief framework zeer effectief is voor het min-max mTSP.

Innovatie: De adaptieve aard van de Q-waarden stelt het algoritme in staat om te "leren" welke steden samen horen, wat de zoekruimte efficiënter navigeert dan traditionele heuristieken.
Toekomst: De auteurs plannen om de route-pool te verrijken met grotere buurten en het leermechanisme uit te breiden naar hogere-orde route-eigenschappen (niet alleen paarsgewijze co-occurrences).

Kortom, RL-CMSA biedt een robuust en schaalbaar alternatief voor bestaande methoden, met name in complexe scenario's met veel voertuigen en grote probleemgroottes.