# Travelling salesman with start and end points for 30 points

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,
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

-
Hello, and welcome to Mathematica.SE! Please edit your question to contain a minimal example, say, with a small collection of cities for your problem. So we can most directly address the Mathematica question at hand, and not the logistics one. –  VF1 Mar 24 '13 at 19:59
@TheGwa: is this a typo in the headline? I'm only counting 20 or 21 points (depending on how you see this, it can be considered a 20 or 21 point problem). But where does the 30 in the title come from? –  Andreas Lauschke Mar 25 '13 at 18:24
@VF1 I am new to Mathematica and was hoping that giving the most possible information about my problem at hand would get me the most directed help. I have clarified the question and added my working solution to it too. Many thanks. –  TheGwa Mar 25 '13 at 22:21
@Andreas: Sorry I have edited the question. 30 points is what I need. –  TheGwa Mar 25 '13 at 22:22
Try with an intelligent goo: technologyreview.com/view/512821/… –  faysou Mar 26 '13 at 9:42

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.

-
But that's exactly my point. It's cheating if you can pick and choose your start and end nodes. The optimal tour is {{-25.6756,28.0821},{-25.6439,28.1315},{-25.7661,28.2811},{-25.7864,28.2807},{-2‌​5.795,28.2993},{-26.2055,28.4206},{-26.772,28.4998},{-26.8743,28.2505},{-26.4214,‌​28.1074},{-26.407,28.1385},{-26.2625,28.1786},{-26.1713,28.2138},{-26.1694,28.207‌​9},{-26.0939,28.1938},{-26.0438,28.1198},{-25.9878,28.0691},{-26.0259,28.0692},{-‌​26.0449,28.0347},{-26.0474,28.0061},{-26.149,27.9227},{-25.992,27.5331}}, verified optimal, and the longest edge is between start and end, the length is 3.22458 –  Andreas Lauschke Mar 25 '13 at 5:27
@Andreas The query stated that it was necessary to fix a start and end (and gave a straightforward justification for that). I made no claim to the effect that the tour I found was optimal in the TSP sense, only that it seemed fine for the stated purpose of the original post. As for "cheating", I have no idea how meeting (or trying to meet) a stated requirement falls into that category. –  Daniel Lichtblau Mar 25 '13 at 17:10
the o/p does not mention a specific start point -- unless I'm missing something (in that case please correct me). You pick the start point purely arbitrary, which gives you room to make your solution almost arbitrarily "good". As for you having no idea how meeting a stated requirement falls into the cheating category, I can only concur, but you merely CLAIM you are meeting a stated requirement. As I said, you pick your start node arbitrarily, giving you the option to pick and choose, thus making your tour (almost) arbitrarily "good" (or bad). –  Andreas Lauschke Mar 25 '13 at 17:17
@Andreas The statement has the route beginning at the last locked point, and ending at the depot (which I assumed to be the initial point, also categorized as locked). I simply reversed this, found a tour starting at the depot and ending at the last locked point which, in this example, was the second point. Then said to simply reverse that. I now notice that another point, #14, is also locked, so the basic idea seems about right but not the actual result. On a separate note, I'm not sure how preselecting a starting point leads to a better (let alone arbitrarily good) solution for a TSP. –  Daniel Lichtblau Mar 25 '13 at 17:24
@Andreas You are certainly correct. I confess I was oblivious to the possibility that our discussion had a point... –  Daniel Lichtblau Mar 25 '13 at 18:04

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]:=
Module[{visited=ConstantArray[1, len], nearest, neighbors, mult, total = 0},
{UndirectedEdge@@@Partition[NestList[(
visited[[#]] = Infinity;
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}];

-
Thanks VF1. I have tried to implement the shortest path algorithm from here: demonstrations.wolfram.com/… it is too slow for anything over 17 points however. I have tried the FindShortestPath function, but I can't work out how to create a graph from my list of coordinates. Could you please point me to an approximate algorithm for the shortest path problem. –  TheGwa Mar 24 '13 at 21:50
I have supplied the Nearest-Neighbor approximate algorithm. This takes in a weighted adjacency matrix. In order to convert a set of coordinates into a Mathematica Graph object, I recommend you take a look at the documentation for Graph, please read the rest of my answer. –  VF1 Mar 24 '13 at 23:31
Thank you for your input. It has helped me significantly in understanding a number of key concepts in Mathematica. It was not the solution I used in the end, but it helped greatly. –  TheGwa Mar 25 '13 at 22:25

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):

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).

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.

-
Why don't you post the anser by using your environment. It seems that we now have two different answers to one question :). Your website looks great. –  Lou Mar 25 '13 at 10:31
@Lou: done, see my addition above. –  Andreas Lauschke Mar 25 '13 at 17:06
Lauske Thanks for the edit. I learned alot and it seems more and more that Java and Mathematica form a very great couple indeed. Impressive. –  Lou Mar 25 '13 at 20:24
@Lou: indeed, M and the JVM are a match made in heaven. The M/.Net combination (qua NETLink) is also quite powerful, it's very, very similar. I mull writing a blog post here about using JLink. I think JLink is totally under-appreciated. –  Andreas Lauschke Mar 25 '13 at 20:33
@Andreas: This looks like a really amazing technology. Unfortunately I cannot install Java on the server due to security concerns, but I appreciate the input. I am sure it will help others greatly. –  TheGwa Mar 25 '13 at 22:27