|
#!/usr/bin/env python3 |
|
# Copyright 2010-2021 Google LLC |
|
# Licensed under the Apache License, Version 2.0 (the "License"); |
|
# you may not use this file except in compliance with the License. |
|
# You may obtain a copy of the License at |
|
# |
|
# http://www.apache.org/licenses/LICENSE-2.0 |
|
# |
|
# Unless required by applicable law or agreed to in writing, software |
|
# distributed under the License is distributed on an "AS IS" BASIS, |
|
# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
|
# See the License for the specific language governing permissions and |
|
# limitations under the License. |
|
# [START program] |
|
"""Simple Vehicles Routing Problem (VRP) with travel break. |
|
|
|
This is a sample using the routing library python wrapper to solve a VRP |
|
problem. |
|
A description of the problem can be found here: |
|
http://en.wikipedia.org/wiki/Vehicle_routing_problem. |
|
|
|
We want a 15min break every 90min of travel |
|
Transits are in minutes. |
|
""" |
|
|
|
# [START import] |
|
from ortools.constraint_solver import pywrapcp |
|
from ortools.constraint_solver import routing_enums_pb2 |
|
# [END import] |
|
|
|
|
|
# [START solution_printer] |
|
def print_solution(manager, routing, solution): |
|
"""Prints solution on console.""" |
|
print(f'Objective: {solution.ObjectiveValue()}') |
|
print('Breaks:') |
|
intervals = solution.IntervalVarContainer() |
|
for i in range(intervals.Size()): |
|
brk = intervals.Element(i) |
|
if brk.PerformedValue(): |
|
print(f'{brk.Var().Name()}: ' + |
|
f'Start({brk.StartValue()}) Duration({brk.DurationValue()})') |
|
else: |
|
print(f'{brk.Var().Name()}: Unperformed') |
|
|
|
time_dimension = routing.GetDimensionOrDie('Time') |
|
travel_dimension = routing.GetDimensionOrDie('Travel') |
|
total_time = 0 |
|
total_travel = 0 |
|
for vehicle_id in range(manager.GetNumberOfVehicles()): |
|
index = routing.Start(vehicle_id) |
|
plan_output = f'Route for vehicle {vehicle_id}:\n' |
|
while not routing.IsEnd(index): |
|
time_var = time_dimension.CumulVar(index) |
|
time_slack_var = time_dimension.SlackVar(index) |
|
travel_var = travel_dimension.CumulVar(index) |
|
travel_slack_var = travel_dimension.SlackVar(index) |
|
plan_output += ' {0} Time({1},{2} slack:{3},{4}) Travel({5},{6} slack:{7},{8}) ->'.format( |
|
manager.IndexToNode(index), |
|
solution.Min(time_var), solution.Max(time_var), |
|
solution.Min(time_slack_var), solution.Max(time_slack_var), |
|
solution.Min(travel_var), solution.Max(travel_var), |
|
solution.Min(travel_slack_var), solution.Max(travel_slack_var)) |
|
previous_index = index |
|
index = solution.Value(routing.NextVar(index)) |
|
time_var = time_dimension.CumulVar(index) |
|
travel_var = travel_dimension.CumulVar(index) |
|
plan_output += ' {0} Time({1}) Travel({2})\n'.format( |
|
manager.IndexToNode(index), |
|
solution.Value(time_var), |
|
solution.Value(travel_var)) |
|
plan_output += 'Time of the route: {}m\n'.format(solution.Value(time_var)) |
|
print(plan_output) |
|
total_time += solution.Value(time_var) |
|
print('Total Time of all routes: {}m'.format(total_time)) |
|
# [END solution_printer] |
|
|
|
|
|
def main(): |
|
"""Entry point of the program.""" |
|
# Create the routing index manager. |
|
# [START index_manager] |
|
manager = pywrapcp.RoutingIndexManager( |
|
31, # number of locations |
|
4, # number of vehicles |
|
0) # depot |
|
# [END index_manager] |
|
|
|
# Create Routing Model. |
|
# [START routing_model] |
|
routing = pywrapcp.RoutingModel(manager) |
|
# [END routing_model] |
|
|
|
# Create and register a transit callback. |
|
# [START transit_callback] |
|
def time_callback(from_index, to_index): |
|
"""Returns the distance between the two nodes.""" |
|
# Convert from routing variable Index to distance matrix NodeIndex. |
|
from_node = manager.IndexToNode(from_index) |
|
to_node = manager.IndexToNode(to_index) |
|
service_time = 0 |
|
if from_node != 0: |
|
service_time = 15 |
|
travel_time = 15 |
|
return travel_time + service_time |
|
|
|
time_callback_index = routing.RegisterTransitCallback(time_callback) |
|
# [END transit_callback] |
|
|
|
# Add Time Windows constraint. |
|
# [START time_windows_constraint] |
|
time = 'Time' |
|
routing.AddDimension( |
|
time_callback_index, |
|
15, # allow waiting time |
|
500, # maximum time per vehicle |
|
False, # force start cumul to zero. |
|
time) |
|
time_dimension = routing.GetDimensionOrDie(time) |
|
#time_dimension.SetGlobalSpanCostCoefficient(100) |
|
|
|
# Travel callback |
|
def travel_callback(from_index, to_index): |
|
"""Returns the distance between the two nodes.""" |
|
# Convert from routing variable Index to distance matrix NodeIndex. |
|
from_node = manager.IndexToNode(from_index) |
|
to_node = manager.IndexToNode(to_index) |
|
travel_time = 15 |
|
return travel_time |
|
|
|
travel_callback_index = routing.RegisterTransitCallback(travel_callback) |
|
|
|
travel = 'Travel' |
|
routing.AddDimension( |
|
travel_callback_index, |
|
15, # allow waiting time |
|
500, # maximum time per vehicle |
|
True, # force start cumul to zero. |
|
travel) |
|
travel_dimension = routing.GetDimensionOrDie(travel) |
|
|
|
|
|
# Define cost of each arc. |
|
# [START arc_cost] |
|
routing.SetArcCostEvaluatorOfAllVehicles(travel_callback_index) |
|
# [END arc_cost] |
|
|
|
|
|
# Add mandatory break of 15min every 90min of travel |
|
# no service time in the travel only dimension |
|
node_visit_transit = [0] * routing.Size() |
|
solver = routing.solver() |
|
for v in range(manager.GetNumberOfVehicles()): |
|
breaks = [ |
|
solver.FixedDurationIntervalVar( |
|
91, # break start min |
|
91, # break start max |
|
15, # break duration: 15 min |
|
False, # optional: no |
|
f'Break for vehicle {v} at 90min'), |
|
solver.FixedDurationIntervalVar( |
|
181+15, # break start min |
|
181+15, # break start max |
|
15, # break duration: 15 min |
|
False, # optional: no |
|
f'Break for vehicle {v} at 180min'), |
|
solver.FixedDurationIntervalVar( |
|
271+15*2, # break start min |
|
271+15*2, # break start max |
|
15, # break duration: 15 min |
|
False, # optional: no |
|
f'Break for vehicle {v} at 270min'), |
|
] |
|
travel_dimension.SetBreakIntervalsOfVehicle( |
|
breaks, # breaks |
|
v, # vehicle index |
|
node_visit_transit) |
|
|
|
|
|
# link this travel.Slack to time.Slack |
|
for index in range(routing.Size()): |
|
if routing.IsEnd(index): # no slack in end node |
|
continue |
|
routing.AddToAssignment(time_dimension.SlackVar(index)) |
|
routing.AddToAssignment(travel_dimension.SlackVar(index)) |
|
solver.Add(time_dimension.SlackVar(index) == travel_dimension.SlackVar(index)) |
|
|
|
# Instantiate route start and end times to produce feasible times. |
|
# [START depot_start_end_times] |
|
for v in range(manager.GetNumberOfVehicles()): |
|
routing.AddVariableMinimizedByFinalizer(time_dimension.CumulVar(routing.End(v))) |
|
routing.AddVariableMinimizedByFinalizer(travel_dimension.CumulVar(routing.End(v))) |
|
|
|
for index in range(routing.Size()): |
|
if routing.IsStart(index) or routing.IsEnd(index): |
|
continue |
|
routing.AddVariableMinimizedByFinalizer(time_dimension.CumulVar(index)) |
|
routing.AddVariableMinimizedByFinalizer(travel_dimension.CumulVar(index)) |
|
# [END depot_start_end_times] |
|
|
|
# Setting first solution heuristic. |
|
# [START parameters] |
|
search_parameters = pywrapcp.DefaultRoutingSearchParameters() |
|
search_parameters.first_solution_strategy = ( |
|
routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC) |
|
if True: |
|
search_parameters.local_search_metaheuristic = ( |
|
routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH) |
|
#search_parameters.log_search = True |
|
search_parameters.time_limit.FromSeconds(10) |
|
|
|
# [END parameters] |
|
|
|
# Solve the problem. |
|
# [START solve] |
|
solution = routing.SolveWithParameters(search_parameters) |
|
# [END solve] |
|
|
|
# Print solution on console. |
|
# [START print_solution] |
|
if solution: |
|
print_solution(manager, routing, solution) |
|
else: |
|
print("No solution found !") |
|
# [END print_solution] |
|
|
|
|
|
if __name__ == '__main__': |
|
main() |
|
# [END program] |
