Conflict-free Pickup-Delivery VRP

[Jo F]

Hello, 

I am facing the challenge to model the following problem of Conflict-free Pickup-Delivery VRP which is described in a minimal example: 

• 2 vehicles (V1 and V2), starting from different position (1 and 2), ending at arbitrary positions
• 2 pickup-delivery orders ([P1, D1], [P2, D2])
• Network graph with nodes and arcs as depicted in Fig 1. 

With the common static VRPs described in the or-tools examples, it is possible to solve the problem and find routes as they are depicted in Fig 1. 

However, one major constraint to my problem is that the routing should be conflict-free (one node/arc can only be occupied by one vehicle at a time).

As shown in the example in Fig 1., if both vehicles start their routes at the same time, they would collide at node 8.

Fig 1.

How can I map this problem to a model with the functionalities available in or-tools? 

One of the ideas would be to split the problem into two parts: 

1. Finding optimal routes without time/collision constraints (as depicted in Fig. 1)
2. Schedule the routes to avoid collisions, e.g. by solving the job shop problem (see. Fig 2. )

Fig 2. 

However, it becomes obvious that there might be better routing solutions than with splitting up the problem into two parts. 

For example, by choosing different routes for both vehicles, a collision would be avoided without shifting the route execution in time:

• V1: 1->3->5->7->10
• V2: 2->4->7->8->9

Also, in more complex scenarios, by doing the scheduling after the routing, there might even be no solution at all without redefining the optimal routes. 

So my question would be if we can integrate the dynamic time-dependent constraint of "collision avoidance" directly into the routing? So that the model combines the node capacity constraint and the pick-up delivery problem?

In general, there is quite some literature out there about conflict-free vehicle routing. But I could not find an implementation of the problem with or-tools.

Thanks in advance