VRP - Minimizing Makespan - the total duration vehicles are on the road

[alirezatheh]

minimizing makespan minimizes the time the last vehicle will arrive to end node. 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)

[hklarner]

@AlirezaH320 any progress on this issue?

[Mizux]

For an example on how to use the GlobalSpan()
https://developers.google.com/optimization/routing/vrp#example

or you can compare with/without looking at vrp.py and vrp_gs.py
-> https://github.com/google/or-tools/tree/mizux/doc/doc#globalspan-on-distance-dimension

[hklarner]

@Mizux
I dont think using the global span is the same as minimizing the longest route as the global span constraint frequently leaves vehicles unused, even for very high coefficients. I have opened an issue with a minimal example about it here:

https://stackoverflow.com/questions/51207808/minimize-max-distance-among-vehicles

and here:

mapbox/node-or-tools#12

[Mizux]

For the record

from six.moves import xrange
import ortools.constraint_solver.pywrapcp
from ortools.constraint_solver import routing_enums_pb2

stops = 20
vehicles = 5
depot = 0

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

def cost_function(x,y):
    return 1

routing.SetArcCostEvaluatorOfAllVehicles(cost_function)

evaluator = cost_function
slack_max = 20
capacity = 20
fix_start_cumul_to_zero = True
name = 'time'
routing.AddDimension(evaluator, slack_max, capacity, fix_start_cumul_to_zero, name)

time_dimension = routing.GetDimensionOrDie(name)
time_dimension.SetGlobalSpanCostCoefficient(1000)

search_params = ortools.constraint_solver.pywrapcp.RoutingModel.DefaultSearchParameters()
#search_params.first_solution_strategy = (routing_enums_pb2.FirstSolutionStrategy.LOCAL_CHEAPEST_INSERTION)
search_params.first_solution_strategy = (routing_enums_pb2.FirstSolutionStrategy.PARALLEL_CHEAPEST_INSERTION)
#search_params.first_solution_strategy = (routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC)
assignment = routing.SolveWithParameters(search_params)

def print_solution(routing, assignment):
    """Prints assignment on console"""
    print('Objective: {}'.format(assignment.ObjectiveValue()))
    total_distance = 0
    for vehicle_id in xrange(vehicles):
        index = routing.Start(vehicle_id)
        plan_output = 'Route for vehicle {}:\n'.format(vehicle_id)
        distance = 0
        while not routing.IsEnd(index):
            plan_output += ' {} -> '.format(routing.IndexToNode(index))
            previous_index = index
            index = assignment.Value(routing.NextVar(index))
            distance += routing.GetArcCostForVehicle(previous_index, index, vehicle_id)
        plan_output += ' {}\n'.format(routing.IndexToNode(index))
        plan_output += 'Time of the route: {}h\n'.format(distance)
        print(plan_output)
        total_distance += distance
    print('Total Time of all routes: {}h'.format(total_distance))

print_solution(routing, assignment)

[athiselvam]

is that working code?

[Mizux]

Same sample but using the v7.x API...

#!/usr/bin/env python3
from six.moves import xrange
from ortools.constraint_solver import pywrapcp
from ortools.constraint_solver import routing_enums_pb2

stops = 20
vehicles = 5
depot = 0

# Create the routing index manager.
manager = pywrapcp.RoutingIndexManager(stops+1, vehicles, depot)

# Create Routing Model.
routing = pywrapcp.RoutingModel(manager)

def distance_callback(from_index, to_index):
    del from_index, to_index
    return 1

transit_callback_index = routing.RegisterTransitCallback(distance_callback)
routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)

slack_max = 20
capacity = 20
fix_start_cumul_to_zero = True
name = 'time'
routing.AddDimension(
        transit_callback_index,
        slack_max,
        capacity,
        fix_start_cumul_to_zero,
        name)

time_dimension = routing.GetDimensionOrDie(name)
time_dimension.SetGlobalSpanCostCoefficient(1000)

search_params = pywrapcp.DefaultRoutingSearchParameters()
#search_params.first_solution_strategy = (routing_enums_pb2.FirstSolutionStrategy.LOCAL_CHEAPEST_INSERTION)
search_params.first_solution_strategy = (routing_enums_pb2.FirstSolutionStrategy.PARALLEL_CHEAPEST_INSERTION)
#search_params.first_solution_strategy = (routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC)
assignment = routing.SolveWithParameters(search_params)

def print_solution(manager, routing, assignment):
    """Prints assignment on console"""
    print('Objective: {}'.format(assignment.ObjectiveValue()))
    total_distance = 0
    for vehicle_id in xrange(vehicles):
        index = routing.Start(vehicle_id)
        plan_output = 'Route for vehicle {}:\n'.format(vehicle_id)
        distance = 0
        while not routing.IsEnd(index):
            plan_output += ' {} -> '.format(manager.IndexToNode(index))
            previous_index = index
            index = assignment.Value(routing.NextVar(index))
            distance += routing.GetArcCostForVehicle(previous_index, index, vehicle_id)
        plan_output += ' {}\n'.format(manager.IndexToNode(index))
        plan_output += 'Time of the route: {}h\n'.format(distance)
        print(plan_output)
        total_distance += distance
    print('Total Time of all routes: {}h'.format(total_distance))

print_solution(manager, routing, assignment)

Still the same issue...

./plop.py
Objective: 11022
Route for vehicle 0:
 0 ->  10 ->  9 ->  8 ->  7 ->  6 ->  5 ->  4 ->  3 ->  2 ->  1 ->  0
Time of the route: 11h

Route for vehicle 1:
 0 ->  11 ->  12 ->  13 ->  14 ->  15 ->  16 ->  17 ->  18 ->  19 ->  20 ->  0
Time of the route: 11h

Route for vehicle 2:
 0 ->  0
Time of the route: 0h

Route for vehicle 3:
 0 ->  0
Time of the route: 0h

Route for vehicle 4:
 0 ->  0
Time of the route: 0h

Total Time of all routes: 22h

[Mizux]

the issue is most First Strategy only consider the arc cost and not the global function cost.

if you replace in the previous sample

search_params.log_search = True
search_params.time_limit.seconds = 30
search_params.local_search_metaheuristic = (
        routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH)

assignment = routing.SolveWithParameters(search_params)

you'll get

./plop.py
...
# ~30s later
I0417 10:45:27.368408 84388 search.cc:251] Solution #4505 (7024, objective maximum = 20022, time = 22554 ms, branches = 67535, failures = 16355, depth = 33, Cross, neighbors = 4716071, filtered neighbors = 4505, accepted neighbors = 4505, memory used = 31.79 MB, limit = 75%)
I0417 10:45:27.368937 84388 search.cc:251] Solution #4506 (6025, objective maximum = 20022, time = 22554 ms, branches = 67543, failures = 16357, depth = 33, Cross, neighbors = 4716091, filtered neighbors = 4506, accepted neighbors = 4506, memory used = 31.79 MB, limit = 75%)
...
I0417 10:46:27.504631 84534 search.cc:251] Solution #6341 (6024, objective maximum = 20022, time = 29998 ms, branches = 90476, failures = 22733, depth = 33, Exchange, neighbors = 6571135, filtered neighbors = 6341, accepted neighbors = 6341, memory used = 31.79 MB, limit = 99%)
I0417 10:46:27.505337 84534 search.cc:251] Finished search tree (time = 29999 ms, branches = 90481, failures = 22762, neighbors = 6571238, filtered neighbors = 6341, accepted neigbors = 6341, memory used = 31.79 MB)
I0417 10:46:27.505391 84534 search.cc:251] End search (time = 29999 ms, branches = 90481, failures = 22762, memory used = 31.79 MB, speed = 3016 branches/s)
Objective: 6024
Route for vehicle 0:
 0 ->  0
Time of the route: 0h

Route for vehicle 1:
 0 ->  8 ->  16 ->  12 ->  4 ->  19 ->  0
Time of the route: 6h

Route for vehicle 2:
 0 ->  18 ->  11 ->  13 ->  20 ->  2 ->  0
Time of the route: 6h

Route for vehicle 3:
 0 ->  9 ->  17 ->  15 ->  14 ->  10 ->  0
Time of the route: 6h

Route for vehicle 4:
 0 ->  3 ->  6 ->  7 ->  5 ->  1 ->  0
Time of the route: 6h

Total Time of all routes: 24h

note: it's always around the solution #4500 that the solver find the solution with max 6h on one node

[JinYaan]

@Mizux,
how I can show this: I0417 10:45:27.368408 84388 search.cc:251] Solution #4505 (7024, objective maximum = 20022, time = 22554 ms, branches = 67535, failures = 16355, depth = 33, Cross, neighbors = 4716071, filtered neighbors = 4505, accepted neighbors = 4505, memory used = 31.79 MB, limit = 75%) when I code with python? where is it from?

[lperron]

It is from the C++ layer, enable by the log_search or trace_search parameter.