Libraries voor Traveling Salesman Problem

[Electrowolf]

Om maar meteen met de deur in huis te vallen; ik ben op zoek naar goede libraries om een traveling salesman path te berekenen. Dit is een iets specifiekere versie van TSP waarbij je niet bij je eerste stad hoeft te eindigen. Je zou het ook kunnen omschrijven als een minimum hamiltonian cycle.

Het probleem is dat ik niet zomaar een willekeurige heuristiek zoek maar eentje die 2-3% van het optimum ligt of zelfs een exact algoritme dat werkt met grafen tot en met 150 knopen. Ondertussen heb ik natuurlijk zelf al wel dingen gevonden maar geen van deze voldoen eigenlijk:

* http://code.google.com/p/java-traveling-salesman/ is 2-opt en komt niet dicht genoeg bij het optimum uit.
* http://www.adaptivebox.net/CILib/code/tspcodes_link.html heeft een mooie verzameling waar MAOS TSP interessant lijkt, maar helaas is hier te weinig informatie over hoe goed de oplossingen zijn.

Effectief is m'n vraag dan ook of er iemand is die nog andere libraries weet en/of hier ervaring mee heeft die een goede suggestie heeft voor eventuele andere oplossingen. Een library voor een exact algoritme tot en met 150 knopen zou helemaal koning zijn .

De taal maakt (nog) niet veel uit, zolang het maar imperatief blijft en niet dingen als LISP of fortran wordt.. .

Ik heb even zitten twijfelen waar dit moet (SEA of hier), maar aangezien dit over implementatie gaat komen we hier uit ;-).

[beany]

Electrowolf schreef op woensdag 13 juni 2012 @ 14:35:
Ik heb even zitten twijfelen waar dit moet (SEA of hier), maar aangezien dit over implementatie gaat komen we hier uit ;-).

Aangezien dit Programming is: wat heb je zelf al geprobeerd om dit met fysieke zelf geschreven code op te lossen? Waar liep je op vast? Kan je wat code tonen? Dit is namelijk vele malen interessanter dan een lib zoeken/vinden.

En hier staat uitgebreide informatie inclusief algoritme informatie: Wikipedia: Travelling salesman problem (zal je zelf ook wel gevonden hebben lijkt me)

[ Voor 19% gewijzigd door beany op 13-06-2012 15:12 ]

[[ti]]

Ik heb deze ooit eens gebruikt, maar weet niet of dat aan je eisen voldoet.

[Soultaker]

Ten eerste moet je bedenken dat jouw probleem (minimum-weight Hamiltonian path) eenvoudig is te herschrijven naar een TSP door een dummy vertex toe te voegen met een afstand 0 van/naar alle andere vertices. Die haal je uiteindelijk weer uit de oplossing en wat overblijft is je pad van minimale lengte. Daarmee heb je het probleem gereduceerd tot een standaardprobleem en kun je er makkelijker standaardtools op los laten.

Daarvoor kun je dan elke werkende tool. Over "MAOS_TSP" kan ik niets vinden, maar Concorde (staat ook in dat lijstje en wordt ook op Wikipedia genoemd) lijkt exacte oplossingen te genereren via integer linear programming. (Die library is alleen gratis voor academic research use, dus misschien voldoet dat niet per se aan je eisen.)

[Electrowolf]

Het punt is dat zelf code schrijven die goed genoeg is te lang duurt, vandaar dat ik naar libraries zoek. Verder klopt het dat het relatief makkelijk te reduceren is en was op zoek naar een lib voor de normale TSP ;-).

Raar dat ik over Concorde heen heb gekeken, als het exacte oplossingen bied is het redelijk wat ik zoek. Alleen even uitzoeken hoe ANSI C precies werkt .

[.oisyn]

Soultaker schreef op woensdag 13 juni 2012 @ 16:05:
Ten eerste moet je bedenken dat jouw probleem (minimum-weight Hamiltonian path) eenvoudig is te herschrijven naar een TSP door een dummy vertex toe te voegen met een afstand 0 van/naar alle andere vertices.

Geldt dat altijd? Is er in dat geval dan niet ook een oplossing krijgen waarbij er met afstand 0 via die vertex tussen twee andere vertices reist?

Volgens mij kun je beter directed edges toevoegen van elke vertex naar de startvertex met afstand 0.

.edit: ik bedenk me net, jouw oplossing werkt wel als de start-vertex niet uitmaakt (je start dan op de virtuele toegevoegde vertex waardoor bovenstaande opmerking niet opgaat). Als je echter een start-vertex wil specificeren dan moet je voor mijn oplossing gaan.

[ Voor 33% gewijzigd door .oisyn op 20-06-2012 17:26 ]

[Voutloos]

Soultakers trucje werkt alleen onder de Hamilton aanname. Als je halverwege langs het beginpunt zou mogen gaat het inderdaad peergevormd.

[.oisyn]

Zie mijn edit . Ik ging er vanuit dat de TS wil dat hij bij een specifieke vertex moet beginnen. Waar dat vandaan kwam weet ik niet, dat is ook helemaal geen vereiste van TSP.

[ Voor 29% gewijzigd door .oisyn op 20-06-2012 17:28 ]

[BtM909]

Electrowolf schreef op woensdag 13 juni 2012 @ 14:35:
Een library voor een exact algoritme tot en met 150 knopen zou helemaal koning zijn .

En het is hier geen persoonlijke afhaalchinees voor Electrowolf

Dit topic blijft open, vanwege de ongoing discussie. Maar je hebt in Programming gepost, dus zal je ook wat van je programming skills laten zien