Google apis for divide the route between n number of locations

Question

I have a use case that is

1. Laundry company has one shop location.
2. Laundry company has 3 trucks (n trucks).
3. Laundry company has n locations to deliver the washed cloths.

with Google directions API I was able to find the optimal route between the locations. But the problem is there I can use only one truck since all the points are added to the API and find the best path.

I want to divide the path into 3 routes and assign each truck. What I am trying to achieve here is possible with the Google APIs or do I need some other tools algorithms for that?

Any help! Thanks in advance!

Answer 1

Interesting problem... To get you started, the code snipped below implements the Agglomeration Heirarchical Clustering algorithm, which iteratively combines the two points having the shortest distance, into the same group. This implementation makes heavy use of the Set object, in order to bring the complexity of memory and time to O(n^2).

Couple of notes...

• You will have to come up with your own cost function, such as Google API calls to determine the distance or time of travel between each set of destinations.
• The algorithm as implemented considers the distance between points to be equal regardless of the direction. That is, this algorithm does not take into account a situation whereby, say, due to one way streets, traveling from A -> B is 1 mile but B -> A is 2 miles. Or as another example, if the cost function is based on time, this algorithm does not take into account a trip with all right hand turns in one direction versus all left hand turns in the other direction.
• DISCLAIMER: This algorithm only provides a generally optimal clustering solution. For a relatively small number of employees and destinations, such as the case presented in the question, this is probably sufficient, but it is up to the user of this algorithm to determine the optimal cost function for travel between the destinations, and to verify and accept the results, as obviously there can be a multitude of factors involved in optimizing the workload (with business ramifications) that this algorithm cannot fully take into account.

function agglomerativeHierachicalClustering( data, costFunction, targetClusters ) {

  // Let's keep track of the number of clusters, which initially is the total
  // number of data points.  Additionally, for each data point, let's track
  // the cluster with which it belongs.  This is O(n).
  let n = data.length;
  let clusterCount = n;
  let clustersByDataIndex = Array.from( Array( n ).keys()).map( i => new Set( [ i ] ) );
  
  // Next, let's call the user defined cost function to determine the distances
  // between each point.  Note that this will compute the cost of data point i
  // to j, but not j to i.  This is O(n^2).  Then, sort the costs from low to
  // high, in preparation for agglomerating the data points.  This is O(n log n).
  let costMatrix = [];
  
  for ( let i = 0; i < n; i++ ) {
    for ( let j = i + 1 ; j < n; j++ ) {
      costMatrix.push( {dataIndex: { i: i, j: j }, cost: costFunction( data[ i ], data[ j ] ) } );
    }
  }
  
  costMatrix.sort( ( a, b ) => a.cost - b.cost );
  
  // Simply walk the sorted cost matrix, combining the points that are closest
  // to each other into sets of data points, adjusting the cluster count as the
  // sets are combined.  This is between O(n) and O(n^2).
  for ( i = 0; i < costMatrix.length; i++ ) {
    if ( clusterCount <= targetClusters ) {
      break;
    }
    let cm = costMatrix[ i ].dataIndex;
    if ( clustersByDataIndex[ cm.i ] !== clustersByDataIndex[ cm.j ] ) {
      for ( let s of clustersByDataIndex[ cm.j ] ) {
        clustersByDataIndex[ cm.i ].add( s );
        clustersByDataIndex[ s ] = clustersByDataIndex[ cm.i ];
       }
       clusterCount--;
    }
  }
  
  // Finally, reduce the cluster index to unique clusters and return the result.
  return [ ...new Set( clustersByDataIndex ) ];

}

myData = [
  { name: 'A', x:20, y:40},
  { name: 'B', x:30, y:35},
  { name: 'C', x:35, y:45},
  { name: 'D', x:40, y:40},
  { name: 'E', x:55, y:20},
  { name: 'F', x:05, y:25},
  { name: 'G', x:10, y:05},
  { name: 'H', x:60, y:00}
];

console.log( 'The data points are...' );
console.log( myData );

function myCost( a, b ) {
  return Math.abs( ( b.x - a.x ) ** 2 + ( b.y - a.y ) ** 2 );
}

let result = agglomerativeHierachicalClustering( myData, myCost, 3 );

console.log( 'The clusters are...' );
for ( let i = 0; i < result.length; i++ ) {
  console.log( [ ...result[ i ] ].map( x => myData[ x ].name) );
}

Now that the destinations are separated into groups based on their proximity, each group of destinations can now be put through the Google Traveling Salesman Problem API to obtain an optimal route for each driver.