I'm currently developing an algorithm that solves the vehicle routing problem with time windows and the possibility for clients to be delivered to multiple locations.
Right now, I'm trying to find the shortest path in term of cost for a given order of clients. For the moment, I made an algorithm that labels each location with the routes that can go to this location.
Here is a scheme for an example I have (I only completed the first four columns):
- each column represents a client and its locations
- black arrows represent rounds that do
depot -> Emplacement X -> depot - green arrows represent rounds that do
depot -> Emplacement X -> Emplacement Y -> depot - red arrows represent rounds that do
depot -> Emplacement X -> Emplacement Y -> Emplacement Z -> depot - there are probably examples with bigger rounds
- crossed out arrows are for emplacements that can't be reached (because of the time window)
With my example, the shortest path to only deliver the first two clients costs 265 and does:
depot -> Emplacement 3 -> Emplacement 16 -> depot(the round costs 265)
And the shortest path to only deliver the first three clients costs 508 and does:
depot -> Emplacement 3 -> depot(the round costs 186)depot -> Emplacement 13 -> Emplacement 11 -> depot(the round costs 322)
What would be the best approach for creating an algorithm that finds the shortest path to deliver every client using the labels generated by my algorithm?
Edit: I tried doing recursion to try each possible route and keep the best. This solution kind of works when there are few clients and few locations but when there are a lot of clients/locations, the computation time explodes
