Reizigersprobleem

Reizigersprobleem, ook wel Travelling Salesman Problem (TSP) genoemd, is een klassiek vraagstuk in de combinatorische optimalisatie. Gegeven een verzameling steden en een afstands- of kostenmatrix tussen elk paar, moet een tour worden gevonden die alle steden precies één keer bezoekt en terugkeert naar het startpunt, met de minimale totale afstand of kosten. Afstanden kunnen symmetrisch zijn (dij = dji) of niet, en in sommige varianten is de afstand Euclidisch (Euclidische TSP).

Het probleem is NP-hard; de beslissingsvorm, of er een tour bestaat met lengte ≤ L, is NP-complete. Er bestaan vele varianten: symmetrische TSP en asymmetrische TSP, en metrische TSP waarin de driehoeksongelijkheid geldt. In sommige gevallen geldt bovendien een Euclidische structuur, waarbij steden in een vlak met Euclidische afstandssystemen worden gemodelleerd.

Oplossingsmethoden: voor kleine tot middelgrote instances kunnen exacte algoritmen worden toegepast, zoals dynamische programmering (Held-Karp), branch-and-bound en cutting-plane-methoden, of ILP-formuleringen. Voor grotere instances worden vooral heuristieken en metaheuristieken gebruikt, waaronder local search (2-opt, 3-opt), genetische algoritmen, simulatieve annealing en ant colony optimization. Voor metrische TSP bestaat een bekende approxi-mimatiegrens van 1,5 via het Christofides-algoritme, wat een bovengrens garandeert op de oplossing.

Toepassingen: het TSP dient als model voor logistieke en routeplanningsproblemen, zoals het plannen van leveringsroutes en voertuigen, evenals als subprobleem in productieplanning en sommige bioinformatica-gerelateerde taken.

Historisch: het reizigersprobleem ontstond uit praktische logistieke vraagstukken en werd in de tweede helft van de twintigste eeuw uitgebreid bestudeerd; tegenwoordig is het een kernprobleem in algoritmen en operationeel onderzoek.