Travelling salesman with start and end points for 30 points

Question

I am doing a route optimisation for delivery vehicles and failing dismally. Please see problem statement below. My current solution uses FindShortestTour, but this does not have defined start and end points.

Data is received from the calling application in the following format: {"Unique Identifier used by server", Original order, Task locked, Latitude, Longitude}

The first point will always have the unique identifier "00000000-0000-0000-0000-000000000000" and represents the depot. This point will always have an order of 1 and always be locked.

A number of tasks may be locked in their given order at the beginning of the list. The Task locked is a boolean represented by 1 - locked, 0 - unlocked. These locked tasks are not included in the optimisation as they are fixed in their given order at the beginning of the scheduled.

The route is to be optimised finding the shortest path starting at the last locked point and ending back at the depot, traversing all other unlocked points. Depot is always locked and will be used if there are no other locked tasks.

The output is to be in the following format: {"Unique Identifier used by server", Original order, Distance to Next Task in km} and is to be arranged in the optimal order. The order will always start with the depot the traverse locked Tasks in their given order. This will be followed by unlocked tasks optimised from the last locked to the depot. This list will not contain the final depot point as the distance returned is the distance to next task. i.e. The last ordered task distance will be the distance from itself to the depot.

The calculation needs to be able to handle the optimisation of 30 points in under a minute as accurately as possible.

input = {{"00000000-0000-0000-0000-000000000000", 1., 
    1., -26.17132739, 
    28.21375807}, {"817463b3-e330-4405-9008-e21821e6c121", 2., 
    1., -26.2055333333333, 
    28.420565}, {"36418378-a9ef-49d7-be5a-3a54264a8479", 3., 
    0., -25.99202013, 
    27.53309061}, {"49595197-11e5-463a-8f7b-6cd294c33f43", 4., 
    0., -26.14895194, 
    27.92271447}, {"83fd029b-0313-4519-a785-ff7b9843c85c", 5., 
    0., -26.169355, 
    28.2079083333333}, {"612bf08a-1679-4feb-8fee-d12deb49803a", 6., 
    0., -25.6755766666667, 
    28.0820533333333}, {"382f1997-5efe-42c1-99f5-bcb8da30e1c8", 7., 
    0., -26.8742866666667, 
    28.25047}, {"883d68f2-b50f-48ca-b065-febfc6ea9546", 8., 
    0., -26.0938733333333, 
    28.1937966666667}, {"1bf089bf-acae-4a41-8c4b-e120cef8a148", 9., 
    0., -25.9877716666667, 
    28.0691433333333}, {"6958e90b-d42a-4c13-b6ec-78bbdd301aba", 10., 
    0., -25.7661166666667, 
    28.2811033333333}, {"2f2c5d25-c1de-449e-b779-dd95699d83ed", 11., 
    0., -26.0474216666667, 
    28.0060766666667}, {"a11feb01-f067-49aa-b99d-50879229c423", 12., 
    0., -25.7949916666667, 
    28.29928}, {"729b8bfb-029a-483a-814a-1575a6fe47bc", 13., 
    0., -26.0258616666667, 
    28.0692033333333}, {"732771dd-55fd-4074-a097-2665686f67d8", 14., 
    0., -26.772045, 
    28.49977}, {"0690914d-ba34-4086-b5ae-feda7ed6d22b", 15., 
    0., -26.044905, 
    28.0346666666667}, {"5de23f0e-9a05-40af-8e1e-f887d5a06452", 16., 
    0., -26.4070083333333, 
    28.138515}, {"3e95a2ac-9985-4753-a4cc-5372ca44ed12", 17., 
    0., -25.64392423, 
    28.13148167}, {"d2e0bce2-8061-4b57-b983-aa409c1532fe", 18., 
    0., -26.42138814, 
    28.1074221}, {"0259d54a-0782-4ac8-a5f6-42af6e3edbc3", 19., 
    0., -25.78637, 28.28066}, {"f686b23a-de85-4004-ae70-8d2703336b5d",
     20., 0., -26.043795, 
    28.1197816666667}, {"e8bca7d4-69ad-4477-8791-9daedbc563c9", 21., 
    0., -26.2624883333333, 28.17859}};


outputReturned = {{"00000000-0000-0000-0000-000000000000", 1., 
   21.020}, {"817463b3-e330-4405-9008-e21821e6c121", 2., 
   26.772045}, {"732771dd-55fd-4074-a097-2665686f67d8", 14., 
   63.26}, {"382f1997-5efe-42c1-99f5-bcb8da30e1c8", 7., 
   27.24}, ..., {"83fd029b-0313-4519-a785-ff7b9843c85c", 5., 0.62}}

Current poor solution here: https://dl.dropbox.com/u/9666857/Schedule.m

Edit The requirement boils down to a traveling salesman path problem.

I have a fixed start and end point with a list of intermediate points which need to be visited exactly once in an optimal order.

I have a working solution here

Answer 1

Could make the end point have distance zero from the depot. Say pt 2is your start point and pty 1 is the finish (depot). Then your example could have a route computed thusly.

pt2 = input[[All, 4 ;; -1]];
len = Length[pt2];

dists = Table[Norm[pt2[[j]] - pt2[[k]]], {j, 1, len}, {k, 1, len}];
dists[[1, 2]] = dists[[2, 1]] = 0.;

FindShortestTour[Range[len], 
 DistanceFunction -> (dists[[#1, #2]] &)]

(* Out[123]= {3.808066795204197, {1, 5, 8, 20, 13, 15, 11, 9, 12, 19, 10,
   17, 6, 3, 4, 21, 16, 18, 7, 14, 2}} *)

Now just reverse it to start at point 2 and end at the depot.

Answer 2

Note that FindShortestTour will not allow for start and end points because it is a tour, and thus you can cycle your staring and ending point by simply removing an edge in your Hamiltonian circuit. To find the shortest path for a given start and end point, I would recommend searching for "find shortest path" in the Documentation Center, which would lead one to the function of interest, FindShortestPath.

As speed seems to be an issue, consider changing the Method used by the function or implementing your own approximate algorithm. However, I don't think it would be necessary to go this far as you stated your problem is for 30 points.

EDIT: As requested, here is an approximate algorithm for the traveling salesman problem. If a significant speed/optimization is required, feel free to implement your own. In the method, start refers to the starting vertex, and adj refers to the adjacency matrix of the graph (you will have to create your own).

Here is a nearest-neighbor algorithm:

NearestNeighbor[start_Integer?Positive, adj_?MatrixQ]:=
    With[{len = Length[adj]},
        Module[{visited=ConstantArray[1, len], nearest, neighbors, mult, total = 0},
            {UndirectedEdge@@@Partition[NestList[(
                visited[[#]] = Infinity;
                neighbors = adj[[#]];
                mult=neighbors visited;
                nearest=Min[mult];
                total+=nearest;
                First@First[Position[mult, nearest]]
                )&,start,len-1],2,1],
            total}
        ]
    ]

You can easily create an adjacency matrix by telling Mathematica to do so after you have created a Graph object from your coordinates. Look up WeightedAdjacencyMatrix and Graph in the documentation. If you have a set of points pts, then it is fairly easy to do:

pts = RandomReal[1, {20, 2}];
wam[pts_, dist_: EuclideanDistance] := 
  Array[If[Equal[##], Infinity, 
     dist[pts[[#1]], pts[[#2]]]] &, {Length@pts, Length@pts}];
WeightedAdjacencyGraph[wam[pts]]

Answer 3

JVMTools has very powerful TSP functions, using initial and post-opt methods and exploiting concurrency by submitting competing algorithms in parallel, and chaining post-opt methods (also in parallel):

TSP Intro and TSP Power Examples

If you want specific start and end points, you could use the option "All", which will return all tours for the subdivision of the list of nodes, and then pick the first one. That is guaranteed to use the start and end points the user has provided. However, note that with fixed start and end points you may not necessarily get the shortest tour through all nodes. The author of JVMTools has specifically implemented it in a manner so that node list subdivision is used in parallel with the start-end edge as a viable candidate, so that it's not possible to "cheat" to create particularly good or bad solutions by specifying fixed start and end points. But, you can discard n-1 solutions and take only the first, that will use your start and end nodes.

FindShortestTour[] uses very simple algorithms. 20 points is small enough, but even with 20 points you are most likely not getting an optimal tour with any of the FST methods. They have a free trial version for JVMTools that is not feature-capped (only time-limited). Some of the algorithms available through JVMTools solve TSP problems with a few thousand nodes to optimality with amazing speed (like less than a minute).

Addition Mar 25:

Due to Lou's request, here is my code. I'm a bit hesitant to say/show too much about JVMTools, because it's my own commercial product, and I don't want to do "cheap plugs" in this venerable community, but due to Lou's request, here it comes. Geez, this is gonna get long, but I like the "Leonid method" :).

There's a few ways to do it. If all distances are Euclidean lengths and you want one of the best TSP algorithms in the world (MAOS, "multi-agent optimization system", similar to an ant-colony optimization system), you could simply submit

JTravellingSalesmanMAOS[Round[1000 input[[All,{4,5}]]],200,200,100,1,"EUC_2D"]//AbsoluteTiming

(*{1.374330,{3857.,{1,5,8,20,9,13,15,11,4,3,6,17,10,19,12,2,14,7,18,16,21}}}*)

This uses 200 agents, 200 as the size of the maximum learning cycle as termination condition, 100 as the number of cycles for the best cycle that no longer changes, 1 as the number of trials, and EUC_2D to specify the 2-dimensional Euclidean norm as distance function. Don't worry, if you understand a bit about multi-agent / ant colony optimization, these terms will not be intimidating. With JVMTools you can use that powerful algorithm without understanding too much about multi-agent optimization / ant colony optimization. MAOS is used by JVMTools with permission of the owners.

The tour is verified optimal, and the only reason it takes 1.4 seconds total time is because the data is encrypted with asymmetric 2048 cipher strength encryption on the client side and sent to the JVMTools server, where the MAOS algorithm runs (like a webservice) on a high-performance Fedora 18 system, and then the result is sent back. 1.4 seconds for 20 nodes is a prohibitively long run time, but the encryption takes constant time for long as well as short data lists, and JVMTools wasn't written for such toy problems. When choosing the MAOS algorithm in JVMTools there is some 1.4 second overhead for everything you send, due to the encryption. This is to ensure that the client data remains confidential when travelling over the public internet with proven unbreakable encryption (active attacks, passive attacks, eavesdropping attacks, chosen-plaintext attacks, chosen ciphertext attacks, man-in-the-middle attacks, padding attacks, ...), and for large problems this constant 1.4 second encryption overhead amortizes away.

But you can also model things in a more flexible way, by specifying the node pairs you want to consider (or drop) and explicitly setting the edge lengths. This may be more appropriate here, as the o/p has "non-standard" edge lengths.

points=input[[All,{4,5}]];
points=Table[{i,points[[i]]},{i,Length@points}];
pairs={#,EuclideanDistance[#[[1,2]],#[[2,2]]]}&/@Subsets[points,{2}];
indices={#[[1,1,1]],#[[1,2,1]]}&/@pairs;
costs=#[[2]]&/@pairs;
JTravellingSalesman[indices,costs,"Method"->"ConcurrentPostOpt"]//AbsoluteTiming

(*{0.041360,{1,21,16,18,7,14,2,12,19,10,17,6,3,4,11,15,13,9,20,8,5}}*)

It looks a bit more complicated than how you specify it when using the MAOS algorithm in JVMTools or FST in M, but in the end it gives you more flexibility, because a) you can specify the distances for each and every one of the n(n-1)/2=Binomial[n,2] theoretically feasible edges individually (assuming complete graph to start with), setting it to any (positive) number, including MaxDouble or 0, b) you can leave out index pairs, which means there is no edge (taken as infinity) -- which means it is no longer a complete graph. With FST you can only specify a distance function, not what I would call edge data. In addition, pairs then provides a "data overview" in a concise form of what you are about to submit as edge-by-edge data. You could literally edit that manually in a spreadsheet program and read in as a M symbol, if you want to model a complicated non-Eudlidean, highly non-convex structure. And although these lists can get long (generated or edited manually), there is no time delay when sending it over to the JVM, because both indices as well as costs are rectangular arrays of compatible type, thus internally they are packed arrays (auto-packed), and JLink/MathLink uses native array methods for primitives, giving you native speed.

Unless I miss something, the o/p did not specify the start node, only the end node (the first), so I can't address that specific case. All TSP functions in JVMTools assume that you want an optimal solution for the FULL cycle, this is by design and not an omission. But you can leave out edges and set arbitrary positive edge lengths, giving you full control over how to model it very individually.

The option ConcurrentPostOpt shown above did the following in 41 milliseconds:

• in thread 1, FarthestInsert is used as initial method, then 6NodeSwap is applied as post-opt, this is candidate 1. Next CheapestInsert is used as initial method, then 6NodeSwap is applied as post-opt, this is candidate 2.
• in thread 2 NearestNeighbor is used as initial method, then 6NodeSwapSingle is applied as post-opt, this is candidate 3.
• in thread 3 NearestNeighbor is used as initial method, then 6NodeSwapDouble is applied as post-opt, this is candidate 4.

The output is the best solution of candidates 1 through 4. As 6NodeSwap is extremely fast (yet effective), I have put two initial/post-opt pairs in one thread, as even both strategies one after the other is faster than the other two, meaning I can get 4 candidates by using only 3 threads.

The tour is verified optimal.

But with 20 nodes you can't really show any meaningful comparison. 20 nodes is a toy problem, a "micro-benchmark", which is not a meaningful comparison. The TSP functions in JVMTools were written for a few thousand nodes (a practical runtime/memory limitation is probably around 20 thousand nodes), where M can do nothing but throw in the towel.