[Lemon-user] TSP on incomplete path and different start / end -point

[Kovács Péter]

Hi Thomas,

If you extend the graph this way with edges corresponding to shortest 
paths, then note that the found TSP tours may visit nodes more than once 
in terms of the original graph. If it is not a problem, then you can 
apply this approach.

As far as I understand, you are actually looking for a Hamiltonian path 
from a start node to an end node instead of a tour (Hamiltonian cycle). 
Your approach seems to be practical, but may need some extra work.

Note that you can manually convert any tour to a path. Let s and e 
denote that start and end node, and let sp, sn, ep, en denote the 
previous and next node of s and e according to the tour. You can
(i) remove edges s-sp and e-ep, and add the edge sp-ep instead OR
(ii) remove edges s-sn and e-en, and add the edge sn-en instead.
Both way you get a path between s and e. Choose the one with the smaller 
total length. (E.g. in case of (i), the path is: <s..ep part of the 
tour>, ep-sp edge, <sp..t part of the tour in reverse order>.)

Furthermore, you can try other TSP solvers, not only ChristofidesTsp. 
You can check the available algorithms here:
http://lemon.cs.elte.hu/pub/doc/1.3.1/a00618.html

I suggest to give a try to Opt2Tsp. It can be started with a tour 
computed with other algorithm, e.g. with ChristofidesTsp. (Actually, 
Opt2Tsp applies transformations similar to the one described above.)

I hope this helps.

Anyway, it is really strange what you wrote about negative costs. The 
total cost of a tour is computed by simply summing the costs of the 
edges in the tour.

Regards,
Péter



> Hi all,
>
> maybe someone of you can point me in the right direction.
>
> I have an incomplete Graph for which I want a TSP solution.
> What I did so far:
> 1. Convert the graph to be complete
>     For this I calculate the distance between nodes not having an edge
> jet, using dijkstra.
>     Than I add a new edge with this length.
> 2. Set the distance between start end end node to be zero
> 3. Run the TSP algorithm
>
> Issue: The TSP is solved but start and end point are never visited one
> directly after another.
>
> Is this possible at all? I even tried to add a negative distance to the
> edge between start and end point.
> Interestingly here I get a negative length of the route even this edge
> is not used.
>
> Regards,
>
> Thomas
>
>
>
> _______________________________________________
> Lemon-user mailing list
> Lemon-user at lemon.cs.elte.hu
> http://lemon.cs.elte.hu/mailman/listinfo/lemon-user
>