Services & ResourcesWolfram ForumsMathGroup Archive

[Date Index] [Thread Index] [Author Index]

FindShortestTour Function- Roundtrip & Constructive Heuristic

• To: mathgroup at smc.vnet.net
• Subject: [mg123325] FindShortestTour Function- Roundtrip & Constructive Heuristic
• From: Chrissi87 <c.curtaz at googlemail.com>
• Date: Thu, 1 Dec 2011 05:53:48 -0500 (EST)
• Delivered-to: l-mathgroup@mail-archive0.wolfram.com

Dear readers,
I have two different questions, both belonging the "FindShortestTour"
Funktion:

1. I refer to an example if the "FindShortesTour" Funktion,
http://reference.wolfram.com/mathematica/ref/FindShortestTour.html,
you can find it under "Method".
The example:

d = SparseArray[{{1, 2} -> 1, {2, 1} -> 1, {6, 1} -> 1, {6, 2} -> 1,
{5, 1} -> 1, {1, 5} -> 1, {2, 6} -> 1, {2, 3} -> 10, {3, 2} ->10, {3,
5} -> 1, {5, 3} -> 1,  {3, 4} -> 1, {4, 3} -> 1, {4, 5} -> 15, {4, 1} -
> 1, {5, 4} -> 15, {5, 2} -> 1, {1, 4} -> 1, {2, 5} -> 1, {1, 6} ->
1}, {6, 6}, Infinity];

In: {len, tour} = FindShortestTour[{1, 2, 3, 4, 5, 6},
DistanceFunction -> (d[[#1, #2]] &)]

Out: {6,{1,5,3,4,2,6}}

I would like to know now, if it is possible to change the calculation
in that way, that at the end of the tour the last point will also be
the first point.Lets say I have to start at knot 1 and at the end of
my tasks I have to return to knot 1.  So it would be a travelling
salesman problem, but with the shortest tour to visit all knot. I know
there is a travelling salesman function but for me it does not work,
because I want to use the different Algoriths (Or Opt, Creedy...)
which one can use with the "FindShortestTour" Funktion.

2. My second question refers to the different Heuristics to calculate
the Shortest Tour.
There is a group (CCA, Creedy...) which is known in the literature as
a Constructive Heruristic  and there is a second group (Or Opt, Two
Opt..) which are improvement algorithtms.
When one calculates by hand a problem like this, one has to construct
a tour with a constructive heuristic (most not very good) and then
make it better with an Improvement heuristic.
I guess Mathematika is doing the same. Still, it is possible calculate
the problem tight from the beginning with an Improvement algorithm.
My question is now, What is the constructive algorithm mathematika
uses? I really would like to know this.

Thank u in advace for all your help.

• Follow-Ups:
  • Re: FindShortestTour Function- Roundtrip & Constructive
    • From: Virgil Stokes <vs@it.uu.se>