Solving OVRP?

[hopewise]

Provided that at OVRP, the vehicle does not return to the depot, Is it possible to solve Open Vehicle Routing Problem with or-tools?

[Mizux]

Simply add a dummy node with zero distance from all others and use it as a depot ?

if it is just for the return you can use the constructor taking a vector of start nodes and end nodes for all vehicles.

e.g. node 0: real depot node 1: dummy depot

def arc_cost_evaluator(a, b)
  if a == 1 or b == 1:
    return 0
  ...

num_vehicle = 5
starts = [ 0 for i in range(num_vehicle) ] 
ends = [ 1 for i in range(num_vehicle) ]
...
routing = pywrapcp.RoutingModel(num_locations, num_vehicles, starts, ends)

[hopewise]

thanks, so at your example above, all ends are dummy nodes? (as OVRP has no end locations provided) while starts are real nodes as all busses starts from specific location?

that's it to solve OVRP?

[Mizux]

Yes, only ends point to the same (ubiquitous) dummy end node.

Depends on what you want to model. Since you said you want open ends (but not necessary open start) So I use two nodes one start node as depot, and one dummy node as end. After you can mix as you want or even use a different location nodes for each vehicles...

[hopewise]

So, as for num_locations at your example, I suppose it will be populated as:

[0] = depot (the start location) [1] = dummy [2 .. n ] = location, where n is number of students that busses will be picking up.

correct?

[paultrow]

See https://developers.google.com/optimization/routing/routing_tasks#allowing-arbitrary-start-and-end-locations

[hopewise]

Thanks!