Finding paths in directed graph

[johannesfknx]

I am dealing with a problem that looks like a VRP at first glance, but differs from most VRPs.

Several vehicles are to execute orders and deliveries in a network of nodes. It is important that the vehicles do not collide with each other on the way from start->order->delivery (see #4335). Therefore, I cannot use the shortest distance between order and delivery, but have to use an additional time dimension at each intermediate node to check whether two vehicles are at a node at the same time. The input for the problem is therefore not a distance matrix with shortest distances, but an adjacency matrix in which unconnected nodes have the distance sys.maxsize (representing a directed graph).

Since it is not possible that multiple vehicles visit a node more than once with the or-tools routing library, I would have to copy each node by the number of vehicles. This leads to a very complex problem, which cannot be solved within minutes. (Order of magnitude 500 nodes, 20 vehicles)

Would it be possible to solve the problem more efficiently with the CP-SAT solver if you define the model yourself? Or is the routing library still recommended? If so, are there alternative ideas on how to prevent the duplication of nodes?

Thanks in advance