Steam Train TSP Solver
, 10 juli 2010Wanneer een handelsreiziger, startende vanuit zijn thuisstad, iedere stad uit een gegeven lijst exact één keer wil bezoeken alvorens naar huis terug te keren, is het aannemelijk dat hij de volgorde waarin hij de steden bezoekt, zo kiest dat het totaal van de af te leggen afstanden zo klein mogelijk is.
Het handelsreizigersprobleem of ook TSP genoemd, is een interessant en veel onderzocht NP-hard probleem uit de theoretische informatica en tevens het onderwerp voor ons Trimesteroverschrijdend project. Meer over het handelsreizigersprobleem kan je lezen op Wikipedia.
Trimesteroverschrijdend Project
Samen met Tom Desair werd Steam Train TSP Solver ontwikkeld; een applicatie geschreven in C++ voor het exact- en benaderend oplossen van het handelsreizigersprobleem. De TSP algoritmen die werden geïmplementeerd zijn:
- Branch and bound met eenvoudige ondergrens
- Branch and bound met MST ondergrens
- Branch and bound met 1-tree ondergrens
- Branch and bound met 1-tree lagrangean relaxation ondergrens
- Closest insertion
- De savings heuristiek
- Genetisch TSP algoritme
- Random Tabu Search
- A* voor het TSP
- MST benaderingsalgoritme
Steam train TSP SolverMeer info en screenshots van dit project zijn te bezichtigen op de Project pagina (UHasselt). Deze pagina wordt niet meer bijgewerkt.
Echte oplossingen
Voor wie zoekt naar een programma om het handelsreizigersprobleem voor een bepaald TSP probleem op te lossen, kan best eens kijken naar Concorde TSP Solver.