I moved my question from Theoretical Computer Science to this site - proposed by one of the users there - and I'm hoping don't be off-topic again.

At my university, I had chosen to write a term paper about Inventory Routing Problem (IRP). To get comfortable with this topic (I'm a software engineer), I started with some simpler problems like Traveling Salesman Problem (TSP) and afterwards with the Vehicle Routing Problem (VRP) which can be defined as simplified IRP problems.

To solve these kind of problems, I wrote an Ant Colony System algorithm with some adaption to the specific problem. But one thing I'm pretty unsure is how to deal with the start and end node of a TSP? Most literature have a strong constraint, that the depot (start/end node) has to be the same and is determined, which makes sense. But the algorithms (heuristics) just cover finding the shortest path. A lot of algorithms determines the starting point randomly. Are there any disadvantages if I define the starting point as fix? But the bigger question is can I add the last point (starting point) independently of the found route to calculate the total costs?

Let's say the algorithm find the cheapest way with D -> 2 -> 3 -> 1 (-> D) but recalculating these manually results in D -> 2 -> 1 -> 3 -> D because 1 -> 3 -> Dis faster than 3 -> 1 -> D. But how I have to include a fixed ending point in my algorithm? I guess it's independent of which specific algorithm.

If you don't understand my question please leave a comment and I try to rewrite it =)

  • 2
    $\begingroup$ I'm not sure I understand. Isn't is problem specific whether or not you can start anywhere you want or not? You can easily fix the starting vertex, and then run your heuristics. It shouldn't be a problem at all. $\endgroup$ – Juho Apr 2 '15 at 13:16
  • $\begingroup$ I am confused by your question: " can I add the last point (starting point) independently of the found route to calculate the total costs?" If the algorithm says D231D, but the shortest route is D213D, then the either algorithm is doing something wrong or you're defining the problem differently. If the algorithm finds the shortest path to be D231 and assumes you can go back to D for free, then it's not calculating a complete TSP solution (perhaps a shortest Hamiltonian path?), in which case starting node IS relevant (because it does not return to its starting point). $\endgroup$ – Alex Pritchard Jun 15 '15 at 16:46

The result of any algorithm for TSP is a tour, that is a cycle in the graph. When translating that answer into practice, you can pick any node as starting point without changing the cost of the tour at all.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.