I have a standard CVRPTW (capacitated vehicle routing problem with time windows). The instance is given by a (not complete) graph $G$ with weighted $w$ directed edges $e \in E$, and I have a limited number of vehicles $v$ with a capacity $k$ and costumers $c_i$ with demands $d_i$ and time windows $[t_i^l,t_i^u]$ where they are able to be serviced at some nodes of the graph $c_i\in V(G)$. I want to visit all customers with tours not exceeding the capacity in demand and minimize the total distance travelled. So far this is a well known problem.

THE NEW CONSTRAINT: in my situation this is all on company premises and there are many roads that have only one lane or that are dead ends. So there might be a situation where multiple cars take the same one lane road in opposite directions at the same time and then they black each other.

Is there a way to deal with this or similar constraints, where the vehicles might interfere with each other? (I know, I could make one lane roads directed and contract dead ends and make them into one customer, but that is not what I want to do.)

  • 1
    $\begingroup$ I would add resource variables for each edge, and constrain the number of resources that can be used per time units, per edge. $\endgroup$ – Kuifje Jun 18 '20 at 11:52

These constraints should be treated in a "dynamic fashion". First you ignore them. Then you check whether your solution satisfies them or not (possibly some timing in your solution should be changed without changing routes themselves). I suppose that most of the time these constraints will be satisfied. If not, you need to find a minimal subset of arcs in your solution which are "responsible" for the conflict with the additional constraints. Then you add the constraint that at least one of these arcs should not participate in the solution (constraints of this kind are called "no-good" in the literature).

  • $\begingroup$ Thank you for your great answer! Do you know of any solvers that can do that, or have an idea for a good starting point, or do you think, that its best to tackle this from scratch (i.e. with an LP-Solver)... $\endgroup$ – Luke599999 Jun 18 '20 at 15:06
  • 1
    $\begingroup$ You may try our solver: vrpsolver.math.u-bordeaux.fr. It is well-suited for this approach. I do not know whether other VRP solvers (which are heuristic) support this kind of "no-good" constraints. Probably, OR-Tools support them. $\endgroup$ – Ruslan Sadykov Jun 19 '20 at 9:48

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.