3

It is suggested to use the span cost coefficient to minimize the max distance among vehicles

# Try to minimize the max distance among vehicles.
# /!\ It doesn't mean the standard deviation is minimized
distance_dimension.SetGlobalSpanCostCoefficient(100)

taken from https://developers.google.com/optimization/routing/vrp#example

This is particularly useful when the cost function is not based on distance (i.e. fuel usage) but on travel time and the goal is to have the last vehicle return to the depot as early as possible.

Q1: can I define the objective function to be the max cost among vehicles (not the sum of total cost and global span)?

If this is not possible I am wondering what the reason is. I could imagine that it is A) hard to implement such a constraint or B) I am missing some implicit disadvantage that results in bad solutions (compared with using the span constraint).

I noticed that the global span constraint, even if I set it to 1000 (but what does that even mean?), does not guarantee even that all vehicles are being used. Surely I can improve that solution by using more vehicles, right?

EDIT: Here is a minimal working example. 5 vehicles are available for servicing 20 stops. I define a uniform traveling time of 1h between stops, so the optimal solution is that each route contains 4 stops and all vehicles are back at the depot after 4h. Without the global span constraint one vehicles does all the work with a total time of 20h. With the global span constraint (coefficient=1000) two vehicles service 10 stops each.

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
capacity = 24
fix_start_cumul_to_zero = True
name = "time"
routing.AddDimension(evaluator, slack_max, capacity, fix_start_cumul_to_zero, name)

time_dimension = routing.GetDimensionOrDie("time")
time_dimension.SetGlobalSpanCostCoefficient(1000)

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

Output of solution plotter:

Route for vehicle 0: 0 -> 11 -> 12 -> 13 -> 14 -> 15 -> 16 -> 17 -> 18 -> 19 -> 0 Duration of route 0: 10 h

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

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

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

Route for vehicle 4: 0 -> 9 -> 8 -> 7 -> 6 -> 5 -> 4 -> 3 -> 2 -> 1 -> 0 Duration of route 4: 10 h

Total duration of all routes: 24 h

Karussell
  • 17,085
  • 16
  • 97
  • 197
Dispochefin
  • 39
  • 3
  • It appears they have a breakdown of how to prioritize travel time on the same page, https://developers.google.com/optimization/routing/cvrptw – Reroute Jul 06 '18 at 11:34
  • 1
    my understanding is that time windows are only feasibility constraints and do not affect the cost function. the line I am referring to is `time_dimension.CumulVar(index).SetRange(data.time_windows[0][0], data.time_windows[0][1])` – Dispochefin Jul 06 '18 at 11:58
  • @Dispochefin yes, but Globalspan(coef) affect the cost function adding `span * coef` to it. Note that during the first solution strategy step the span is not taking into account, so only the [time windows] constraints and arc cost, so in the next step the LNS should take into account the GlobalSpan to find a better solution -> need to create/add an example in the doc to show this behavior. – Mizux Jul 25 '18 at 09:17
  • Hi @Mizux ; do I understand your comment correctly please; that it is not possible to ensure that every vehicle is used (i.e. minimise max distance travelled by a vehicle) if using a FirstSolutionStrategy (in a problem aligned with https://developers.google.com/optimization/routing/vrp). Thanks – user20650 Jan 07 '20 at 15:41

0 Answers0