Minimizing Makespan - the total duration vehicles are on the road

[daniel-j-h]

At the moment users can pass in a durations matrix for costs and we will minimize the total number of vehicle driving hours. In contrast, this ticket is about minimizing the total duration vehicles are on the road.

---

Implementation:

Minimize the route's end cumul var. for the time dimension. This will minimize the overall completion time.

for (auto vehicle = 0; vehicle < model.vehicles(); ++vehicle)
  model.AddVariableMinimizedByFinalizer(model.CumulVar(model.End(vehicle), timeDimension));

[Herteby]

Oh right, so with the current implementation, vehicles may wait around at a location for any amount of time without incurring a cost? That seems like a big problem.

Is my guess right that that your solution would only run after the main optimization is done, when the routes have already been decided? That could lead to a lot of wait time remaining if you're using small time windows.

[daniel-j-h]

No - the time vehicles "wait" at a location is the service time (check the docs for durations.

The difference between the current implementation and minimizing the makespan as ticketed here is minimizing makespan minimizes the time the last vehicle will arrive back at the depot. Basically optimizing getting the full problem done as fast as possible.

Simple example highlighting what's getting minimized:

• Currently: 9 vehicles on the road for 2 hours, 1 vehicle on the road for 8 hours (26 hours -> min)
• Minimizing Makespan: 10 vehicles on the road for 2.6 hours (2.6 -> min) (26 hours)

[Herteby]

Aah, got you! :+1: Hmm, what I meant by wait time though is the time a vehicle may have to wait due to time windows. Not the service time, how long it takes to unload a package. This is not something you could program into the cost at the start like you do with travel time, so I am unsure if gets optimized for. And does one hour of waiting have the same cost as one hour of driving then?

[daniel-j-h]

We optimize based on costs only. Costs are applied to ways not to locations. What you could do is you could add secondary objectives and then e.g. minimize the arrival time at each location.

[hklarner]

@daniel-j-h My goal is to minimize the total duration on the road instead of the total number of driving hours. My understanding is that I have very little control over the cost function, i.e., I have to define the arc cost via

routing.SetArcCostEvaluatorOfAllVehicles(cost_function)

and the objective function will be either the total cost or the total cost plus the weighted global spans of each dimension on which I called

some_dimension.SetGlobalSpanCostCoefficient(SpanCoefficient)

Hence I can not simply define the objective function to be the max of all routes (instead of the sum).

Following your suggestion above, I create a new dimension, called "time", that uses the same evaluator as the cost but on which I also call AddVariableMinimizedByFinalizer for each vehicle. To keep it simple I choose constant 1 as the cost. A good solution for 5 drivers and 20 stops should be 4 stops for each driver. The solver still returns a solution in which 1 vehicle does all the work instead of using all available vehicles.

Here is a minimal example, followed by the output of the solution printer:

import ortools.constraint_solver.pywrapcp
import ortools.constraint_solver.routing_enums_pb2

stops = 20
vehicles = 5
depot = 0

routing = ortools.constraint_solver.pywrapcp.RoutingModel(stops, vehicles, depot)

def cost_function(x,y):
    return 1

routing.SetArcCostEvaluatorOfAllVehicles(cost_function)

evaluator = cost_function
slack_max = 24 * 60
capacity = 24 * 60
fix_start_cumul_to_zero = True
name = "time"
routing.AddDimension(evaluator, slack_max, capacity, fix_start_cumul_to_zero, name)

for vehicle in range(vehicles):
    routing.AddVariableMinimizedByFinalizer(routing.CumulVar(routing.End(vehicle), "time"))

search_params = ortools.constraint_solver.pywrapcp.RoutingModel.DefaultSearchParameters()
assignment = routing.SolveWithParameters(search_params)

Here is the output:

Route for vehicle 0: 0 -> 0 Duration of route 0: 1 min

Route for vehicle 1: 0 -> 0 Duration of route 1: 1 min

Route for vehicle 2: 0 -> 0 Duration of route 2: 1 min

Route for vehicle 3: 0 -> 0 Duration of route 3: 1 min

Route for vehicle 4: 0 -> 19 -> 18 -> 17 -> 16 -> 15 -> 14 -> 13 -> 12 -> 11 -> 10 -> 9 -> 8 -> 7 -> 6 -> 5 -> 4 -> 3 -> 2 -> 1 -> 0 Duration of route 4: 20 min

Total duration of all routes: 24 min