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?