• We’re currently investigating an issue related to the forum theme and styling that is impacting page layout and visual formatting. The problem has been identified, and we are actively working on a resolution. There is no impact to user data or functionality, this is strictly a front-end display issue. We’ll post an update once the fix has been deployed. Thanks for your patience while we get this sorted.

FOUND! Algorithm question: Traveling Salesman...

X

xirtam

Diamond Member
Before you ask, no, this isn't homework.

I'm looking for an implementation of an 3-opt solution to the traveling salesman problem. Don't care about language, could even be in pseudocode.

Thanks a bunch.

Problem description is here per google search.
 
I looked at various TSP aprpoaches for an Operations Research class as an undergrad but never got around to finishing my Turbo Pascal code for an attempt at a geomertic-partitioning solution.

I assume you've already tried Googling with words like "source" and "algorithm" added?
 
I've used genetic algorithms, which isn't the best way to solve a simple tsp problem. But the, mine wasn't simple (multiple salesmen, moving cities).

I'm not familiar with the 3-opt approach??
 
Yeah, Dave, tried googling, came upon some stuff but not what I'm looking for yet. Still googling.

Well there's the k-opt system of optimization, which is after getting a fundamental route, implementing a system of switching nodes until the best path is found. 3-opt switches 3 nodes at a time, if I understand it correctly (and that's a really basic way to explain it, but you get the idea.)

Right now I'm almost done with a 2-opt algorithm and I want to see if anybody's done a 3-opt before. It'd be helpful. I'd like to do some efficiency tests.

Edit: Found it, thanks.
 
Originally posted by: xirtam
Yeah, Dave, tried googling, came upon some stuff but not what I'm looking for yet. Still googling.

Well there's the k-opt system of optimization, which is after getting a fundamental route, implementing a system of switching nodes until the best path is found. 3-opt switches 3 nodes at a time, if I understand it correctly (and that's a really basic way to explain it, but you get the idea.)

Right now I'm almost done with a 2-opt algorithm and I want to see if anybody's done a 3-opt before. It'd be helpful. I'd like to do some efficiency tests.

Edit: Found it, thanks.
Click to expand...

Linkage?
 
Doh! Now I don't remember where I downloaded it. PM me if you want the code or the URL when I find it.
 
You must log in or register to reply here.

TRENDING THREADS

Back
Top