We are facing problem in sequencing geocodes to reach destination(Single destination for all pickup) with minimum cost.
Lets assume we have a Set of n geocodes as a pick up locations and a destination location. There is no origin. Maximum n can be up to 20.
The goal is to sequence all geocodes in such a way to visit all the geocodes in order to reach the destination with the overall minimum cost(which can be distance or time).
First we tried a brute force solution:
We use Google distance matrix API, to get distance matrix of n*n having distances of each geocodes to other. Generated all the permutations of the pickup, and then checked for the combination with minimum distance.
But this solution is only limited to 7 pickups or else it will take so much time.
Another solution that we were implementing is to use Google direction API, they provide a way to optimise the waypoints but we have to pass the origin and destination both. But in our case there is no origin defined.
We tried selecting some random origin like choosing the farthest node as the origin but these solutions are not working, in real life use case geocodes can be on opposite end of roads and taking U turn can a bigger factor which might degrade our cost.
Is there any way that we can use this Google direction API feature for our use case? Our we should shift to some other approach?