2
$\begingroup$

Currently I am developing a piece of software that solves the vehicle routing problem.

The task is the following:

  • I have several vehicles along the town
  • I have lots of destination points along the town
  • Vehicles have delievering product on board, and the product is uniform (it doesn't matter if you receive it from vehicle A versus vehicle B)
  • Let assume that vehicles can not run out of products
  • The number of destination points is greater than the number of available vehicles
  • I need to calculate optimal routes through multiple points for every vehicle to minimize the average transportation time

My naive approach is the following:

  • find nearest points for each vehicle using k-means clustering with the raw euclidean distance between map points (LngLat points)
  • for each vehicle for each destination point from the set of vehicle's nearest destination points calculate optimal routes using other destination points as intermediate points and find routes with smallest avarage transportation time (optimal route from point A to point B crossing several intermediate points can be received from Google Maps API so it is not necessary to use TSP algorithm for it).

It seems that this approach may give results which are not optimal.

Is there better approach which provides better accuracy and/or smaller amount of API requests?

$\endgroup$
  • $\begingroup$ What has to be transported from where to where? $\endgroup$ – Raphael Sep 12 '14 at 15:37
  • 3
    $\begingroup$ Note that the one-vehicle version of the problem is essentially metric TSP which means that it's hard but a lot of work has been done on heuristics and approximations. $\endgroup$ – David Richerby Sep 12 '14 at 15:51
  • 2
    $\begingroup$ @zavg How do you know that the route found by Google is optimal? Note that if you are essentially asking "how do I improve my implementation?", you are offtopic for Computer Science. "How do I improve my algorithm?" is ontopic, and helpful pointers have already been given. $\endgroup$ – Raphael Sep 12 '14 at 16:45
  • 2
    $\begingroup$ I'm happy that this is an algorithms question, rather than implementation, not least because the Google Maps API is something of a red herring. GMaps doesn't re-order destinations: e.g., if you ask for a route Los Angeles-Boston-San Francisco-New York, it gives you exactly that and doesn't say "Hey, why not do LA-SFO-Boston-NY instead?". So, you're asking how to solve an NP-hard problem with access to an oracle for a problem in P, which is just as hard as solving it without the oracle. Also, how do you define optimal? Traffic conditions might change while you're running the algorithm. $\endgroup$ – David Richerby Sep 12 '14 at 20:46
  • 1
    $\begingroup$ @DavidRicherby There is optimizeWaypoints option in GMaps API v3. If it is set to true, the DirectionService will attempt to re-order the supplied intermediate waypoints to minimize overall cost of the route. So the result will contain the re-ordered permutation of the input waypoints. For example, if the input was: Origin: Los Angeles Waypoints: Dallas, Bangor, Phoenix Destination: New York then the optimized output will be ordered as follows: Origin: Los Angeles Waypoints: Phoenix, Dallas, Bangor Destination: New York. $\endgroup$ – zavg Sep 13 '14 at 11:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.