CVRP with vehicles blocking each other

Question

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.)

Answer 1

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).