# FindShortestTour for charity (or: How can I optimize meal delivery with FindShortestTour?)

I've been wondering about this for a while - but never got around to asking - until I saw faleichik's incredible answer to Mathematica Minecraft.

I did some work at a not-for-profit a little while ago, which participated in a program called Meals On Wheels - wherein I helped to deliver food to those who are homebound. Myself and a partner would deliver meals to a daily list of addresses, sorted by name; not the most efficient route. The time to complete a route varied by as much as two hours because of it.

FindShortestTour, however, is only one (possible) part of the solution. I'd need to parse addresses, read map data, and handle the slight irregularities of NYC streets.

How can I use FindShortestTour to find the optimal meal delivery route, given a list of addresses?

-
"the slight irregularities of NYC streets" - so, not Manhattan? ;) – J. M. Jun 10 '13 at 6:31
@J. M. Well, Manhattan + one ways :) – R. M. Jun 10 '13 at 6:34
I'd suggest that, for this practical application, it isn't necessary to calculate a route that is guaranteed to be the shortest. It'll be easier to incorporate various hard and soft constraints if you instead take a more heuristic approach, e.g. simulated annealing. This will still return a solution very close to optimal, but will take much less time to do so. – Oleksandr R. Jun 10 '13 at 8:14
Until they switched to Google Maps a few years ago, the Champaign-Urbana MoW gave route "directions" that, seemingly, had never been tested. Optimal, perhaps. But invariably completely wrong. – Daniel Lichtblau Jun 10 '13 at 12:16
@J. M. I don't think many birds tried them out. The only ones following us on those desolate roads were vultures.. – Daniel Lichtblau Jun 10 '13 at 17:26

When I did a similar job, it wasn't really the distance that made the difference. It would sometimes be quicker to drive 30 miles into the country for a drop than to try to cross the city at rush hour or during the school run. So it might be worth trying to work out the times between each drop and then find the route that has the shortest total time, rather than do it by distances on a map.

Here, rather clumsily derived, is a list of the different routes between, say, 8 places:

numberOfPlaces = 8;
edges = DeleteCases[
Map[#[[1]] \[DirectedEdge] #[[2]] &,
Tuples[Range[1, numberOfPlaces], {2}]],
x_ \[DirectedEdge] x_ /; x == x]


and we can assign times in minutes for travelling between each place, here just randomly. This is a bit of work initially, but most drivers would be able to estimate the times quite quickly.

randomweights = RandomInteger[{0, 45}, Length[edges]]


{17, 38, 25, 17, 9, 42, 7, 42, 11, 14, 40, 17, 4, 23, 4, ... 40}

Combine these with the edges:

edgeWeightRules =
Rule, {edges, randomweights}] /.
(1 \[DirectedEdge] 4 -> n_) -> 1 \[DirectedEdge] 4 -> 200


I've set the value for traveling between places 1 and 4 to 200, for use later on. Next, draw a graph:

 cg = Graph[edges,
VertexLabels -> "Name",
VertexStyle -> Red,
EdgeWeight -> edgeWeightRules,
EdgeLabels -> edgeWeightRules,


This is not a physical map, but a picture showing the different travel times between different places. Then create a weighted adjacency graph:

wam = Normal[WeightedAdjacencyMatrix[cg]] /. 0 -> Infinity;
EdgeShapeFunction ->
GraphElementData[{"DotLine", "ArrowSize" -> .01}],
VertexLabels -> "Name",
EdgeWeight -> edgeWeightRules,
EdgeLabels -> edgeWeightRules,
EdgeLabelStyle -> Directive[Gray, Italic, 12],
VertexLabelStyle -> Directive[Black, 16],
EdgeStyle -> Directive[LightGray],


Apparently, a Hamiltonian cycle is not a two-wheeled delivery device, but a path visting every vertex exactly once:

FindHamiltonianCycle[wag, All]


{{1 -> 2, 2 -> 3, 3 -> 4, 4 -> 5, 5 -> 6, 6 -> 7, 7 -> 1}

so we should find all of them, and then sort them by the total time each one takes:

routes = Sort[{Total[# /. edgeWeightRules], #} & /@
FindHamiltonianCycle[wag, All]]


This returns a list of all possible cycles, with the quickest one first. So the quickest route that turns up at all locations once takes 54 minutes (that's driving past and throwing the items out of the window...:).

{54, {1 -> 6, 6 -> 4, 4 -> 3, 3 -> 5, 5 -> 7, 7 -> 2, 2 -> 1}}

Then it's possible to investigate the different routes, using a Manipulate to step through the Hamiltonian cycles:

Manipulate[
Column[{
Row[{"length of ", Last[routes[[n]]], " is ", First@routes[[n]]}],
HighlightGraph[
wag,
PathGraph[
Last@routes[[n]],
DirectedEdges -> True],
GraphHighlightStyle -> "Thick",
ImageSize -> 400]
}], {n, 1, Length[routes], 1}]


The artificially slowed-down route shows up as being part of the longest cycles.

At least this approach avoids the problems of trying to find routes through the one-way systems of cities.

-
Also, there's the left turn problem. While it can take longer than if you make both left and right turns, if you make only right turns, you'll save gas. – rcollyer Jun 10 '13 at 15:15
@rcollyer I remember seeing that a few years ago. I hope the OP can save as much gas us UPS can. :) – cormullion Jun 11 '13 at 7:41
And, the mythbusters verified it. :) – rcollyer Jun 11 '13 at 12:39
WHOA. This answer is incredible. Creating routes basically answered the question, but the manipulate really goes an extra mile. (do I sense a dash of british understatement?) – Alexander Riccio Jun 23 '13 at 10:37
:) you might... In fact, I found a better answer to this recently, which would have helped me. – cormullion Jun 23 '13 at 10:43

The FindShortestTour outputs leave a lot to be desired, in fact, none of the solutions shown for the coprime examples in the help browser are optimal. Some take half an hour to compute, and if you increase the number of nodes to a few dozen or hundred, it runs for a few days without providing good solutions. I assume you have plenty of needy people in NYC, not just some 20 or 30.

You could use the add-on package JVMTools, which has several highly advanced TSP functions. The outputs are generally optimal for a few hundred locations, and they are usually 1 - 3% longer than optimal for a few thousand locations, within seconds or minutes of running time. JVMTools was written for industrial-strength applications.

These TSP functions of JVMTools make maximum use of multi-threading, it will autosubmit as many competing calculations as you have cores on your machine, and you can always request more (threads = calculations), and then request output of either all solutions, or only the best. This is the TSP intro page and these are the TSP power examples.

You can assign arbitrary (non-negative!) distances, so you could use the Euclidean norm or the Manhattan-norm or anything else (Broadway doesn't exactly obey the Manhattan norm). You can "merge" points by setting a distance of 0 or model one-way streets by using a distance of infinity.

Free trial version

-
There are needy people in Broadway? Whodathunkit... ;) – J. M. Jun 10 '13 at 16:00
Psst - Columbia University is on Broadway :O – Alexander Riccio Jun 10 '13 at 22:12
ooh - In some sleep-deprived fog, I read it as nerdy. This just sounds strange. :eek: – Alexander Riccio Jun 23 '13 at 9:15

This is a very excellent question. I won't give an answer here (and I doubt I could give one), because I think that cormullion's answer is already really nice and beautiful.

One really interesting mathematical object on that matter are space-filling curves.

For Meals-on-Wheels in Atlanta John Bartholdi and his coworkers applied space-filling curves to give a reasonable solution to this TSP-problem.

A Minimal Technology Routing System for Meals On Wheels

Maybe you find somebody who has access to Interfaces journal (http://interfaces.journal.informs.org/content/13/3/1.abstract)

Stan Wagon has in his outstanding book Mathematica in Action written a whole chapter about space-filling curves with load's of examples for tour generation and tour improvement.

-