All possible routes with distance matrix

Question

I'm currently using Google DistanceMatrix to get the distance between multiple points.

For example, I have 4 different points, to get the distance between each point, I give in the 4 points as both origins and destinations.

"destination_addresses" : [
        "201 W 75th St, New York, NY 10023, USA",
        "569-573 Columbus Ave, New York, NY 10024, USA",
        "142a E 79th St, New York, NY 10075, USA",
        "1350-1352 Madison Ave, New York, NY 10128, USA"
   ],
   "origin_addresses" : [
        "201 W 75th St, New York, NY 10023, USA",
        "569-573 Columbus Ave, New York, NY 10024, USA",
        "142a E 79th St, New York, NY 10075, USA",
        "30 E 95th St, New York, NY 10128, USA"
   ],
   ...

https://pastebin.com/fBKiKJrr

This gives me a 4 x 4 array, which makes sense. But now I want to find all possible routes from A to B, C and D.

So essentially I want to find and get the total distance and duration

 A -> B -> C -> D
    A -> B -> D -> C
    A -> C -> B -> D
    ...

I tried writing a recursive function, but failed at it. What would be the best way to do this?

Do all routes have to be of the same length 4 or do you allow shorter routes for instance A -> D -> B or A -> B? — user2314737, Aug 17 '17 at 10:29
@user2314737 It should always go through all locations, but always start from A. — liquid5109, Aug 18 '17 at 06:04

user2314737 · Answer 1 · 2017-08-17T11:09:20.503

Here's a solution for fixed length route. This is basically using a recursive function to generate all permutations of an array ( see also Generate permutations of JavaScript array)

var destination_addresses = [
    "201 W 75th St, New York, NY 10023, USA",
    "569-573 Columbus Ave, New York, NY 10024, USA",
    "142a E 79th St, New York, NY 10075, USA",
    "1350-1352 Madison Ave, New York, NY 10128, USA"
  ],
  origin_addresses = [
    "201 W 75th St, New York, NY 10023, USA",
    "569-573 Columbus Ave, New York, NY 10024, USA",
    "142a E 79th St, New York, NY 10075, USA",
    "30 E 95th St, New York, NY 10128, USA"
  ];

function permutate(arr) {
  if (arr.length < 2) return arr;
  var permutations = [];

  for (var i = 0; i < arr.length; i++) {
    var restArr = arr.slice(0, i).concat(arr.slice(i + 1, arr.length));

    for (var subPermutation of permutate(restArr))
      permutations.push([arr[i]].concat(subPermutation))

  }
  return permutations;
};

console.log(JSON.stringify(permutate([1, 2, 3])));

I used the array [1, 2, 3] but you can substitute it with destination_addresses.

If you're looking for the shortest route then this is a case of the travelling salesman problem and you will need to use some approximated algorithm for a viable solution.

I'm essentially looking for the shortest route, but I figured I would get all combinations first and then calculate the route length per combination — liquid5109, Aug 18 '17 at 06:05
@liquid5109 if you don't have many destinations it might be okay to use a brute-force search. Keep in mind that for `n` destinations you will have to examine `n!` possible combinations and that's a lot already for small `n`. — user2314737, Aug 18 '17 at 11:56
PS @liquid5109 Amazingly, Google seems to provide an approximate solution to the TSP as part of their directions API: https://developers.google.com/optimization/routing/tsp/tsp — user2314737, Aug 18 '17 at 11:58

All possible routes with distance matrix

1 Answers1