0
$\begingroup$

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): scheme

  • 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:

  1. 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:

  1. depot -> Emplacement 3 -> depot (the round costs 186)
  2. 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

$\endgroup$
  • $\begingroup$ Your graphic is really hard to understand.Is this a traveling salesman problem ? $\endgroup$ – Vince Jun 1 at 13:55
  • $\begingroup$ It's a vehicle routing problem. For the graphic I adapted the graphic made by C. Prins for his splitting procedure (Slide 17/Page 18 of this PDF) $\endgroup$ – Thomas Jun 1 at 16:28

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.