Driving Distance Matrix calculation

I used the Microsoft Bing API to return the driving distances between various addresses in a matrix.

My next step is to create a formula to return the sequence of addresses in the order I should goto based on shortest distance between each point (also referred to as the traveling salesman problem). Also looking to return the distance between each point.

See attached spreadsheet, with a "before" and "after" section. Address1 is my starting address.

Any ideas what formula to use in Excel 365 to get the output? Thanks.

I'm not aware of any formula (or combination of formulas) that can efficiently solve the traveling salesman problem. From what I understand of the TSP, its complexity is NP-hard or similar, so that one would not expect to find a simple string of calculations that solves the problem.

Most Excel based solutions that I see proposed involve using Excel's Solver utility (or similar solver engine). The overall solution involves:

1) Formulas to compute "total distance" based on visiting the nodes in a given order.
2) Other formulas to compute any constraints on the problem
3) Call the solver engine and tell it to minimize the total distance by trying different sequences of nodes. Keep trying until the solver engine decides it is done.

Here's one tutorial I found: http://blog.excelmasterseries.com/20...blem-with.html There are several others out there by putting something like "traveling salesman Excel" into your favorite search engine.

I know you've marked this as solved but I've only just started playing with solver and thought this was a good opportunity to try it out. I changed the names of the destinations to numbers just so I could set solver parameters around them but you can still link the numbers to named destinations. I put the solver parameters as an image into the spreadsheet too. The requirement for the destinations to add up to 15 is not required as I also have settings that they are integers between 1 and 5 and must all be different so you could remove the sum = 15 if you wanted.

EDIT: I am curious though why your matrix isn't symmetrical. It implies some directions are longer in one direction thana the other which might account for one way streets and the like I guess.

If this problem should be treated as a "Travelling salesman" problem the salesman should end up in the same city (address) as he started from.

This is easily fixed in the uploaded solver solution add a formula to cell A16 i.e. "A16=A11" and copy the formulas in "B15:C15" to "B16".

And the shortest distance for the travelling salesman is 61.1 as opposed to 63.2 if he travels 1, 2, 3, 4, 5.

The setting "AllDifferent" is an interesting one. FrontlineSolvers Excel Online Help has this comment about it:

A constraint such as*A1:A5 = alldifferent, where A1:A5 are decision variable cells, requires that these cells must be integers in the range 1 to N
(N = 5 in this example), with each variable*different*from all the others at the solution.* Hence, A1:A5 will contain a*permutation*of integers, such as 1,2,3,4,5
or 1,3,5,2,4.* An alldifferent constraint can be used to model problems involving ordering or sequencing of choices, such as the Traveling Salesman Problem.

So using AllDifferent for range A11:A15 removes the need for an integer constraint as well as the upper and lower limits.

Alf

Thanks Alf,

I tried removing the constraint that the sum = 15 (as that seemed superfluous in this instance) but interestingly I got some weird results.

I agree with your solution too on the returning to home.