Beware of the Classical Benchmark Instances for the Traveling Salesman Problem with Time Windows

Dit paper stelt dat klassieke benchmarkinstanties voor het Traveling Salesman Problem met tijdvensters niet langer representatief zijn voor evaluatie, omdat een nieuwe exacte methode deze binnen enkele seconden oplost en hun structuur dusdanig exploiteerbaar is dat resultaten misleidend goed lijken.

De kern

Waarschuwing: De "Klassieke Proefkaarten" voor de Koerier met Strikte Tijden zijn Verouderd

Stel je voor dat je een koerier bent die een vrachtwagen bestuurt. Je moet op een dag 50 of meer klanten bezoeken. Elke klant heeft een heel specifiek tijdsvenster: je mag niet te vroeg komen (dan moet je wachten), en je mag absoluut niet te laat komen. Je start bij het depot, doet al je bezorgingen en moet weer terugkeren.

De grote vraag voor computerwetenschappers is: Wat is de snelste route?

Er zijn twee manieren om dit te meten:

1. De "Maken-tijd" (Makespan): Hoe laat ben je precies terug bij het depot? (De klok op de muur).
2. De "Duur" (Duration): Hoe lang heb je daadwerkelijk gereden en gewacht? (De brandstofmeter).

Het Probleem: De Oude Testkaarten zijn "Gemanipuleerd"

In dit artikel zegt de auteur, Francisco Soulignac, iets heel opmerkelijks: De standaard testkaarten die al 40 jaar worden gebruikt, zijn niet meer eerlijk.

Het is alsof je een auto wilt testen op snelheid, maar je kiest een circuit waar de weg perfect vlak is, er geen stoplichten zijn en de wind altijd meeblaast. Als je auto daar razendsnel is, denk je misschien: "Wauw, wat een snelle auto!" Maar in de echte wereld, met hellingen en file, zou die auto misschien vastlopen.

De auteur heeft een heel simpel, slim algoritme bedacht. Het werkt als een terugwaartse zoektocht. In plaats van te bedenken: "Waar kan ik naartoe als ik nu vertrek?", denkt het algoritme: "Als ik nu terug moet zijn, waar moet ik dan vorige week zijn geweest?"

Het resultaat is verbazingwekkend:

• Op de oude, klassieke testkaarten (met 50+ klanten) lost dit simpele algoritme elk probleem op in minder dan 10 seconden.
• Het is zo snel dat het zelfs de moeilijkste problemen uit die oude sets oplost die andere super-complexere algoritmen niet aankonden.

Waarom werkt dit zo goed? (De "Structuur" van de Kaart)

De auteur legt uit dat deze oude testkaarten een verborgen zwakheid hebben. Ze zijn gegenereerd met een specifieke methode waarbij de tijdvensters (de tijden waarop je mag komen) te strak of te voorspelbaar zijn.

• De Analogie: Stel je voor dat je een doolhof hebt. In de oude testkaarten zijn de muren zo geplaatst dat er eigenlijk maar één logische weg is die werkt. Je hoeft niet echt na te denken; je kunt gewoon de muren volgen en je komt er wel.
• Het simpele algoritme van de auteur ziet deze "muur" direct en loopt er zo doorheen.
• Andere, complexere algoritmen proberen misschien elke mogelijke weg uit, wat veel tijd kost, maar omdat de "muur" zo duidelijk is, winnen ze toch.

De Gevaarlijke Valstrik voor Machine Learning

Vandaag de dag gebruiken veel bedrijven en onderzoekers Machine Learning (AI) om deze routes te plannen. Om die AI te trainen, gebruiken ze juist diezelfde oude testkaarten om "moeilijke" voorbeelden te genereren.

Het gevaar:
Als je een AI traint op deze oude kaarten, leert de AI niet hoe je een echt moeilijk doolhof oplost. Het leert alleen hoe je die specifieke, voorspelbare muren omzeilt.

• Het is alsof je een student laat studeren voor een examen, maar je geeft hem alleen de antwoorden van de vorige jaren. De student haalt een 10, maar als je hem een nieuw type vraag geeft, faalt hij.
• De auteur waarschuwt: Als je een algoritme of AI beoordeelt op deze oude kaarten, denk je misschien dat het super slim is. Maar in de echte wereld, waar de tijdvensters willekeuriger en "losser" zijn, zou het algoritme waarschijnlijk falen.

Wat is de oplossing?

De auteur stelt voor om nieuwe, echte moeilijke kaarten te maken.

• In plaats van strakke tijdsvensters, moeten we kaarten maken waar de tijdsvensters wijd zijn (je mag op veel momenten komen) of waar de situatie chaotischer is.
• Op deze nieuwe kaarten faalt het simpele algoritme van de auteur direct. Dat is goed! Dat betekent dat we nu eindelijk kunnen zien welke algoritmen echt slim zijn en welke alleen maar goed zijn in het oplossen van oude raadsels.

Conclusie in het Kort

1. De oude testkaarten zijn te makkelijk: Ze hebben een structuur die door simpele methoden makkelijk te hacken is.
2. Wees voorzichtig: Als je een nieuw algoritme of een AI beoordeelt op deze oude kaarten, krijg je een vals gevoel van succes.
3. De toekomst: We moeten harder trainen met "losse" tijdsvensters. Alleen dan weten we of onze koeriers (algoritmen) echt klaar zijn voor de realiteit.

Kortom: Stop met het testen van je auto op een lege parkeerplaats; ga hem testen op een bergweg met regen.

Technische samenvatting

Hier is een gedetailleerde technische samenvatting van het artikel "Beware of the Classical Benchmark Instances for the Traveling Salesman Problem with Time Windows" van Francisco J. Soulignac, in het Nederlands.

Probleemstelling

Het artikel richt zich op het Traveling Salesman Problem with Time Windows (TSPTW), waarbij een voertuig een reeks klanten moet bezoeken binnen vooraf gedefinieerde tijdvensters. Het voertuig mag vroeg arriveren en wachten, maar niet te laat. Er worden drie varianten van het probleem onderzocht, afhankelijk van de te minimaliseren doelstelling:

1. TSPTW-M (Makespan): Minimaliseren van de totale tijd tot terugkeer op het depot (completiestijd).
2. TSPTW-D (Duration): Minimaliseren van de totale reistijd (tijd tussen vertrek en terugkeer, inclusief wachttijden).
3. TSPTW-TT (Travel Time): Minimaliseren van de pure reistijd (exclusief wachttijden).

De kern van het artikel is een kritische evaluatie van de klassieke benchmark-instanties (zoals die van López-Ibáñez en Blum, 2023), die decennialang zijn gebruikt om algoritmen te testen. De auteur betoogt dat deze instanties, vooral die met 50 of meer klanten, niet langer representatief zijn omdat hun structuur te eenvoudig is voor geavanceerde zoekmethoden en dat ze leiden tot vertekende conclusies over de prestaties van nieuwe algoritmen (inclusief die voor machine learning).

Methodologie

De auteur presenteert een eenvoudige, exacte methode gebaseerd op informed search (geïnformeerde zoektocht) voor het oplossen van TSPTW-M.

• Algoritme 1 (Terugwaartse Best-First Search):

  • Het algoritme doorzoekt een boom van partiële routes in terugwaartse richting (van het einddepot naar het startdepot).
  • Het prioriteert partiële routes die het einddepot eerder bereiken.
  • Pruning-strategieën:
    • Onbereikbare knopen: Een voorverwerkingsstap berekent een functie $U(v, t)$ die bepaalt welke knopen onmogelijk voor knoop $v$ kunnen komen binnen een bepaald tijdsvenster.
    • Dominantie: Een partiële route wordt verworpen als er een andere route bestaat met dezelfde bezochte knopen die een eerdere aankomsttijd garandeert of een latere vertrektijd toelaat zonder de deadline te schenden.
  • Het algoritme is een beslissingsmethode: het zoekt naar een route die binnen een bepaalde bovengrens ($ub$) aankomt.

• Algoritme 2 (Oplosser voor TSPTW-M):

  • Herhaalt Algoritme 1 met een dalende bovengrens voor de makespan totdat de optimale oplossing wordt gevonden.

• Algoritme 3 (Oplosser voor TSPTW-D):

  • Lost het duration-probleem op door een sliding window-benadering.
  • Het voert Algoritme 2 uit voor verschillende vertrektijden ($t_0$) binnen het planningshorizon.
  • Het gebruikt lokale zoekheuristieken (swap, 2-opt, shift) om de vertrektijden te initialiseren en te optimaliseren, waardoor het aantal keer dat het dure exacte algoritme moet worden uitgevoerd, wordt geminimaliseerd.

Belangrijkste Bijdragen

1. Ontmaskering van de Klassieke Benchmarks: De auteur toont aan dat de klassieke benchmark-instanties (Asc, Dum, Gen, Lan, Ohl, DaS) met 50+ klanten structureel "zwak" zijn. Ze kunnen worden opgelost door een relatief simpel algoritme in minder dan 10 seconden.
2. Preprocessing-Valstrik: Elke geavanceerde methode die een variant van dit eenvoudige algoritme gebruikt als voorverwerkingsstap, zal schijnbaar uitstekende resultaten behalen op deze benchmarks, wat leidt tot misleidende conclusies over de algemene kracht van het algoritme.
3. Contrast met "Moeilijke" Instanties: Het algoritme faalt volledig op instanties met losse tijdvensters (zoals de Rif-benchmark van Fontaine, 2024, en Rifki et al., 2020), zelfs bij een klein aantal klanten (30-40). Dit bewijst dat de moeilijkheid van het probleem meer afhangt van de strakheid van de tijdvensters dan van het aantal klanten.
4. Advies voor Machine Learning: Veel ML-algoritmen worden getraind op datasets die zijn gegenereerd met procedures die lijken op die van de klassieke benchmarks (strakke vensters). Dit leidt tot overfitting op "gemakkelijke" patronen. De auteur waarschuwt dat trainingssets moeten variëren in de strakheid van tijdvensters ($\beta$-parameter) om robuuste modellen te krijgen.

Resultaten

De experimenten zijn uitgevoerd op een laptop (AMD Ryzen 7) met een tijdslimiet van 3 minuten per instantie voor TSPTW-M en 30 minuten voor TSPTW-D.

• TSPTW-M Resultaten:

  • Het voorgestelde algoritme lost alle klassieke benchmark-instanties met 50+ klanten op in gemiddeld minder dan 10 seconden.
  • Het lost zelfs de 4 openstaande instanties uit eerdere studies (Fontaine, 2024) op.
  • Paradox: Het algoritme faalt op 7 instanties met minder dan 50 klanten (vanwege geheugenuitputting bij losse vensters) en presteert slecht op de Rif-benchmark (met losse vensters), waar het zelfs de generieke methode van Rudich et al. (2023) verslaat.
  • De prestaties op de klassieke benchmarks (Lan, Dum, Gen, Ohl, DaS) zijn uitzonderlijk snel, wat suggereert dat deze instanties een "bias" bevatten die door het algoritme wordt uitgebuit.

• TSPTW-D Resultaten:

  • Door het TSPTW-M-algoritme als "off-the-shelf" methode te gebruiken, worden alle maar één van de klassieke instanties met 50+ klanten opgelost (inclusief 14 die eerder onopgelost waren).
  • De oplossingstijden blijven onder de 30 minuten per instantie.
  • Dit bevestigt dat de klassieke benchmarks ook voor de duration-variant te eenvoudig zijn.

Significantie en Conclusie

De paper concludeert dat de klassieke benchmark-instanties verouderd zijn voor het evalueren van moderne TSPTW-algoritmen.

• Representativiteit: De vraag of deze synthetische instanties werkelijke wereldproblemen vertegenwoordigen, blijft open. Realistische scenario's (zoals online stacker-crane problemen) hebben vaak strakke vensters, maar de huidige benchmarks zijn te gestructureerd en te makkelijk voor enumeratieve methoden.
• Aanbeveling: Voor een eerlijke evaluatie en training van algoritmen (zowel exact als ML-gebaseerd) moeten benchmarks worden aangevuld met instanties die variëren in de strakheid van tijdvensters. Het gebruik van parameters zoals $\beta$ (zoals voorgesteld door Fontaine en Rifki) om vensters te verbreden, is essentieel om "harde" instanties te genereren die echt de grenzen van een algoritme testen.
• Waarschuwing: Onderzoekers moeten oppassen met het claimen van state-of-the-art prestaties op basis van de klassieke benchmarks, aangezien deze resultaten mogelijk het gevolg zijn van het exploiteren van een specifieke bias in de datastructuur in plaats van een overlegende algoritme-ontwerp.