Vehicle Routing Problem where distance constraint will depend on first visited node

user_6279450 0
Viewed 65

I am trying to solve the vehicle routing problem for cabs to pick-up employees and drop them off at the office using OR-Tools.

One of the requirement is that no employee should spend more them 'x' km off the route, i.e. if x = 10 km and employee A lives 10 km away from the office, then the distance traveled by cab after picking up employee A should not be more than 20 km(10km of x + 10km of distance from A to office).

So, if for the best route, the cab needs to pick employee A then B, and then C, but the total distance is turning out to be 25km, then it is not allowed, if it is up to 20 it is fine.

So the max distance allowed for any cab to travel will depend on who the first pickup is. Is there any way to implement such a scenario using OR-tools??

vehicle-routing traveling-salesman or-tools
1 Answers

In python, it should something like this:

x_pickup = manager.NodeToIndex(x_index)
x_drop = manager.NodeToIndex(y_index)
routing.solver().Add(
  distance_dimension.CumulVar(x_pickup) + 10 <=  
  distance_dimension.CumulVar(y_drop))
user_57102330
Related