TSP2

Top  Previous  Next

Function TSP2(nodenum: integer; TSPtype: smallint; maxseconds: integer): single;

 

Calculates the optimum order to visit a list of nodes. TSP2 uses a 2-optimum algorithm.

 

The cost between two nodes are calculated in both directions, but the average is used in the optimization.

 

Nodenum is the number of nodes in the optimization (2<=nodenum<=NodeListLimit).

 

With 2 GB RAM and with a call to extravarcreate, the limit for nodenum is app. 14000. With no call to extravarcreate, the limit is appr. 20000. That many nodes requires several hours of optimization time.

 

TSPtype = 0 or 10:

A route is calculated, which starts at the first node and ends at the last node in the list. The order of the other nodes are optimized.

 

TSPtype = 1 or 11:

A round trip is calculated, where the order of all nodes are optimized.

 

TSPtype = 2 or 12:

A trip is calculated, where only the first node is fixed. The last node on the route will be somewhere far from the first node. This method requires more computing time than type 0 and 1, when ATSP=false.

 

If TSPtype = 10, 11 or 12 straight line distances are used in the optimization. This is a lot faster, but also less accurate.

 

Maxseconds can be used to limit the total time used for the optimization. Please note that this only applies to the part of the TSP function that actually does the optimization - calculation of the distance matrix is always processed first. Specify 0 to let the procedure run until all possibilities has been tested.

 

The function returns the minimum cost.

 

At the same time the "extra" variable is calculated for the whole route. Get this with function TSP2extra.

 

The new (optimum) order of the nodes can be retrieved with function NodeListGetNewPos. Please note this is different from the now obsolete TSP function.

 

Example input data:

NodeList[1] = 10

NodeList[2] = 17

NodeList[3] = 8

NodeList[4] = 5

NodeList[5] = 12

NodeList[6] = 20

 

The optimization calculates, that the optimum order is node 8, 17, 5, 12, 20, 10. This is returned in this way:

 

Example output data:

NodeListGetNewPos[1] = 3

NodeListGetNewPos[2] = 2

NodeListGetNewPos[3] = 4

NodeListGetNewPos[4] = 5

NodeListGetNewPos[5] = 6

NodeListGetNewPos[6] = 1

 

It is also possible to look it up the other way around, i.e. which position on the ordered list has the Nth node on the list:

 

NodeListGetOldPos[1] = 6

NodeListGetOldPos[2] = 2

NodeListGetOldPos[3] = 1

NodeListGetOldPos[4] = 3

NodeListGetOldPos[5] = 4

NodeListGetOldPos[6] = 5

 

The table below shows how well the algorithm performs for 88 standard test datasets from TSPlib. As an example there are 9 datasets with 201-300 nodes. After 1 minute of optimization, the average result is 1.5% worse than true optimum. If the optimization was stopped already after 3 seconds, the average result was 1.6% worse than true optimum. More than 1 minute will not improve it further (unless you have more than 300 nodes). All test runs with <45 nodes was solved to 100% optimality.

 

Nodes

Test runs

3 sec

1 min

10 min

30 min

4 hours

1-200

40

100.7





201-300

9

101.6

101.5




301-1000

14

103.7

102.7

102.5



1001-1250

5

104.9

104.1

103.5

103.4


1251-2350

14

105.9

104.8

104.2

103.8

103.6

2351-6000

6

106.3

105.9

105.2

104.9

104.8

 

If you enter a node number more than once, a short distance will be used for the distance between each occurrence.

 

With many nodes, the processing time increases a lot - especially for mode 0, 1 and 2.

 

Entering node number 0, triggers error -38 and so does nodes in a subnet.

 

Use OnTSPProgress event for tracking progress.

 

Possible error codes: -10 -30 -38 -40 -41 -43 -50

Versions: Standard Pro

ActiveX / VCL / CLX component: RWcalc