Het Handelsreizigersprobleem is een klassieke puzzel die wiskundigen en logistiek experts al decennia lang uitdaagt. Stel je een bezorger voor die een specifieke lijst steden precies één keer moet bezoeken en weer naar huis moet terugkeren, terwijl hij probeert de kortst mogelijke route te vinden om brandstof en tijd te besparen. Hoewel de regels eenvoudig zijn, groeit het aantal mogelijke routes zo explosief met elke toegevoegde stad dat zelfs de krachtigste supercomputers moeite hebben om het absolute beste pad te vinden voor grote groepen. Dit is waarom het probleem wordt beschouwd als een centrale test voor elke nieuwe methode om complexe puzzels op te lossen. In de afgelopen jaren hebben wetenschappers zich tot kunstmatige intelligentie gewend, specifiek een type leren dat nabootst hoe het menselijk brein patronen verwerkt, om deze uitdaging aan te pakken. Deze leersystemen berekenen niet elke mogelijke optie; in plaats daarvan bestuderen ze duizenden voorbeelden om een reeks regels te leren die meestal leiden tot een zeer goede, zo niet perfecte, oplossing. Het doel is om een systeem te creëren dat snel genoeg is om nuttig te zijn in het echte leven, maar slim genoeg is om niet vast te lopen op een slechte route.

Een team onderzoekers uit Shanghai heeft een nieuwe aanpak voor dit probleem ontwikkeld die balans vindt tussen snelheid en nauwkeurigheid op een innovatieve manier. Hun werk, getiteld DA-GAT-CADS, pakt een specifieke moeilijkheid aan die eerdere pogingen heeft gehinderd: de spanning tussen het kijken naar nabijgelegen opties en het kijken naar verre opties. Op een stadskaart is de volgende stop op een goede route meestal een buur, maar soms moet de bestuurder enkele nabijgelegen steden overslaan om twee verre clusters van steden met elkaar te verbinden. Oudere AI-modellen moesten vaak kiezen tussen twee extremen. Ze konden elke niet-bezochte stad bekijken om er zeker van te zijn dat ze een verre verbinding niet misten, maar dit was traag en rekentechnisch zwaar. Of ze konden alleen naar de dichtstbijzijnde buren kijken om tijd te besparen, maar dit zorgde er vaak voor dat ze de cruciale langeafstandssprongen misten die nodig zijn om de tour efficiënt af te ronden. De onderzoekers realiseerden zich dat de oplossing niet was om één kant te kiezen, maar om een systeem te bouwen dat de lokale buurt gebruikt als een veilige standaard, terwijl het een mechanisme gereed houdt om uit te reiken wanneer de situatie daarom vraagt.

De kern van hun nieuwe methode bestaat uit twee hoofdonderdelen die samenwerken. Ten eerste bouwt het systeem een mentale kaart van de steden op basis van hun geometrische lay-out, specifiek door gebruik te maken van een wiskundige structuur genaamd Delaunay-triangulatie. Denk hierbij aan het trekken van lijnen tussen steden die van nature dicht bij elkaar liggen, waardoor een web van lokale verbindingen ontstaat. De onderzoekers ontwierpen een encoder die nauwlettend let op deze lokale lijnen, waarbij de werkelijke afstand tussen steden wordt gebruikt om te wegen hoe belangrijk elke verbinding is. Dit zorgt ervoor dat het systeem de directe geografie van het probleem begrijpt. Echter, ze voegden ook een lichtgewicht globale feedbackloop toe, waardoor het systeem een gevoel van de gehele kaart in zijn geest kan houden, niet alleen de directe omgeving. Deze combinatie helpt het systeem een sterk begrip van de posities van de steden op te bouwen zonder overweldigd te worden door onnodige details.

Het tweede deel van het systeem is de decoder, die verantwoordelijk is voor het daadwerkelijk kiezen van de volgende stad om te bezoeken. In plaats van blindelings elke stad te controleren of strikt vast te houden aan de dichtstbijzijnde buren, gebruikt dit systeem een dynamische bemonsteringsmethode. Het houdt altijd de niet-bezochte buren uit de lokale kaart aan als een veilige lijst van kandidaten. Maar het heeft ook een "poort" die kan openen om verre steden binnen te laten als de huidige route suggereert dat ze nodig zijn. Deze poort is niet vast; het leert te beslissen op basis van de staat van de tour. Als de bestuurder vastzit in een cluster van steden en een sprong naar een verre groep moet maken om een slechte route te vermijden, opent de poort zich wijder om die verre opties te overwegen. Als de lokale buren voldoende zijn, blijft de poort gesloten, waardoor de zoektocht gefocust en snel blijft. Dit besluitvormingsproces wordt getraind met een speciaal beloningssysteem dat het model straft voor het te restrictief zijn (het negeren van goede verre opties) of te expansief zijn (te veel steden controleren en tijd verspillen).

Toen de onderzoekers dit nieuwe systeem testten op groepen van vijftig, honderd en tweehonderd steden, lieten de resultaten een duidelijke verbetering zien in hoe de AI de balans tussen kwaliteit en snelheid bewaarde. Op een standaardtest met honderd steden verminderde hun methode het foutpercentage vergeleken met een standaardmodel van 0,65% naar 0,28%. Belangrijker nog, toen ze hun dynamische poortsysteem vergeleken met een vast systeem dat slechts een vast aantal buren bekijkt, vond de nieuwe methode betere routes terwijl er gemiddeld nog veel minder steden werden bekeken. Specifiek had het nieuwe systeem slechts ongeveer 24% van de niet-bezochte steden nodig om een oplossing van een kwaliteit te bereiken die bijna net zo goed was als het controleren van alle steden. Deze efficiëntie vertaalde zich in voordelen in de echte wereld: het systeem draaide sneller en gebruikte minder computergeheugen dan modellen die alle opties controleerden, zonder de kwaliteit van de uiteindelijke route op te offeren.

De studie onderzocht ook hoe gevoelig het systeem was voor zijn instellingen, specifiek hoe sterk het werd aangemoedigd om tijd te besparen versus het vinden van de perfecte route. Ze ontdekten dat ze door één enkele controle aan te passen, het gedrag van het systeem konden verschuiven. Als ze het te hard pushten om schaars te zijn, miste het belangrijke verre verbindingen en werden de routes slechter. Als ze het lieten te veel steden controleren, werd het traag. Echter, ze identificeerden een "sweet spot" waar het systeem hoge kwaliteit routes behield terwijl het aantal gecontroleerde steden laag bleef. Dit vermogen om de balans te stemmen suggereert dat de methode robuust en aanpasbaar is. Bovendien, toen het werd getest op echte kaartgegevens uit een publieke bibliotheek van benchmarkproblemen, presteerde het systeem competitief ten opzichte van andere geavanceerde methoden, wat bewees dat zijn geometrische intuïtie goed werkt, zelfs op kaarten die niet deel uitmaakten van zijn training.

De onderzoekers merken er zorgvuldig bij op dat hun werk een stap voorwaarts is in een specifief gebied: kleine tot middelgrote kaarten met steden die verspreid liggen in een plat vlak. Ze beweren niet het probleem voor elk mogelijk scenario of voor enorme, complexe netwerken te hebben opgelost. Hun bijdrage is een specifiek ontwerpprincipe: het gebruik van geometrie als een betrouwbaar anker voor lokale beslissingen, terwijl geleerd context wordt gebruikt om selectief verre opties te herstellen wanneer dat nodig is. Door de keuze welke steden te overwegen te behandelen als een flexibele, leerbare actie in plaats van een vaste regel, hebben ze een solver gecreëerd die zowel efficiënt als effectief is. Deze aanpak biedt een veelbelovend pad voor toekomstige logistieke en routingsystemen, waarbij het vinden van een zeer goede oplossing snel vaak waardevoller is dan wachten op een perfecte een.