在 Google or-tools 中用两种车型解决时间受限的 CVRP
Solving Time-constrained CVRP with two vehicle types in Google or-tools
我正在为时间受限的 CVRP 建模。问题是在受车辆（送货）容量和总花费时间（每辆车）约束的情况下，最小化总行程时间（不包括包裹投递时间）。丢包时间是指在每个节点需要花费的额外时间，花费的总时间等于行程时间加上这个额外时间。我有以下适用于单一车辆类型案例的模型。这里我想介绍一下两车类型的概念，就是说我有一套V1型车和一套V2型车。车辆类型的唯一区别是每次旅行的成本。令x表示V1的单位时间旅行成本，y表示V2的单位时间旅行成本。我怎样才能设计模型以使其包含这个额外的方面？
from ortools.constraint_solver import routing_enums_pb2
from ortools.constraint_solver import pywrapcp
def create_data_model(n_vehicles):
"""Stores the data for the problem."""
data = {}
data['time_matrix'] = TT #travel time
data['num_vehicles'] = n_vehicles
data['depot'] = 0
data['demands'] = demands
data['vehicle_capacities'] = vehicle_capacities
data['service_time'] = service_time
return data
def print_solution(data, manager, routing, solution):
"""Prints solution on console."""
print(f'Objective: {solution.ObjectiveValue()}')
max_route_time = 0; tour = {i:[] for i in range(data['num_vehicles'])}
for vehicle_id in range(data['num_vehicles']):
index = routing.Start(vehicle_id)
plan_output = 'Route for vehicle {}:\n'.format(vehicle_id)
route_time = 0
while not routing.IsEnd(index):
plan_output += ' {} -> '.format(manager.IndexToNode(index))
tour[vehicle_id].append(manager.IndexToNode(index))
previous_index = index
index = solution.Value(routing.NextVar(index))
if previous_index != 0 and previous_index <= len(data['service_time'])-1:
service_time = data['service_time'][previous_index]
else:
service_time = 0
route_time += (routing.GetArcCostForVehicle(
previous_index, index, vehicle_id) + service_time)
plan_output += '{}\n'.format(manager.IndexToNode(index))
tour[vehicle_id].append(manager.IndexToNode(index))
plan_output += 'Travel time of the route: {} sec\n'.format(route_time)
print(plan_output)
max_route_time = max(route_time, max_route_time)
print('Maximum of the route time: {} sec'.format(max_route_time))
return(tour)
def main(n_vehicles):
number_of_veh = [n_vehicles][0]
solution_found = False
while solution_found == False:
"""Entry point of the program."""
# Instantiate the data problem.
data = create_data_model(number_of_veh)
# Create the routing index manager.
manager = pywrapcp.RoutingIndexManager(len(data['time_matrix']),
data['num_vehicles'], data['depot'])
# Create Routing Model.
routing = pywrapcp.RoutingModel(manager)
# Create and register a transit callback.
def time_callback(from_index, to_index):
"""Returns the time between the two nodes."""
# Convert from routing variable Index to time matrix NodeIndex.
from_node = manager.IndexToNode(from_index)
to_node = manager.IndexToNode(to_index)
return data['time_matrix'][from_node][to_node]
transit_callback_index = routing.RegisterTransitCallback(time_callback)
# Define cost of each arc.
routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)
# Create and register a transit callback.
def time_callback2(from_index, to_index):
"""Returns the time between the two nodes."""
# Convert from routing variable Index to time matrix NodeIndex.
from_node = manager.IndexToNode(from_index)
to_node = manager.IndexToNode(to_index)
if from_node != 0:
return data['time_matrix'][from_node][to_node] + data['service_time'][from_node]
else:
return data['time_matrix'][from_node][to_node]
transit_callback_index2 = routing.RegisterTransitCallback(time_callback2)
# Add Time constraint.
dimension_name = 'Time'
routing.AddDimension(
transit_callback_index2,
0, # no slack
Operational_hours*3600, # vehicle maximum travel time
True, # start cumul to zero
dimension_name)
time_dimension = routing.GetDimensionOrDie(dimension_name)
def demand_callback(from_index):
"""Returns the demand of the node."""
# Convert from routing variable Index to demands NodeIndex.
from_node = manager.IndexToNode(from_index)
return data['demands'][from_node]
demand_callback_index = routing.RegisterUnaryTransitCallback(
demand_callback)
routing.AddDimensionWithVehicleCapacity(
demand_callback_index,
0, # null capacity slack
data['vehicle_capacities'], # vehicle maximum capacities
True, # start cumul to zero
'Capacity')
# Setting first solution heuristic.
search_parameters = pywrapcp.DefaultRoutingSearchParameters()
search_parameters.first_solution_strategy = (
routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC)
search_parameters.local_search_metaheuristic = (
routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH)
search_parameters.time_limit.FromSeconds(VRP_time_limit)
# Solve the problem.
solution = routing.SolveWithParameters(search_parameters)
# Print solution on console.
if solution:
tour = print_solution(data, manager, routing, solution)
solution_found = True
else:
print('No solution found! Increasing the vehicle numbers by one and resolving.\n')
solution_found = False
number_of_veh += 1
return(tour, number_of_veh)
编辑
根据@Mizux 的回答，我编写了以下内容，产生了以下错误。
from ortools.constraint_solver import routing_enums_pb2
from ortools.constraint_solver import pywrapcp
def create_data_model(n_vehicles):
"""Stores the data for the problem."""
data = {}
TT = np.array(df.values)
data['time_matrix'] = TT
data['num_vehicles'] = n_vehicles
data['depot'] = 0
data['demands'] = demands
if len(vehicle_capacities) < n_vehicles:
data['vehicle_capacities'] = [vehicle_capacities[0]]*n_vehicles
else:
data['vehicle_capacities'] = vehicle_capacities
data['service_time'] = service_time
return data
def print_solution(data, manager, routing, solution):
"""Prints solution on console."""
print(f'Objective: {solution.ObjectiveValue()}')
max_route_time = 0; tour = {i:[] for i in range(data['num_vehicles'])}
for vehicle_id in range(data['num_vehicles']):
index = routing.Start(vehicle_id)
plan_output = 'Route for vehicle {}:\n'.format(vehicle_id)
route_time = 0
while not routing.IsEnd(index):
plan_output += ' {} -> '.format(manager.IndexToNode(index))
tour[vehicle_id].append(manager.IndexToNode(index))
previous_index = index
index = solution.Value(routing.NextVar(index))
if previous_index != 0 and previous_index <= len(data['service_time'])-1:
service_time = data['service_time'][previous_index]
else:
service_time = 0
route_time += (routing.GetArcCostForVehicle(
previous_index, index, vehicle_id) + service_time)
plan_output += '{}\n'.format(manager.IndexToNode(index))
tour[vehicle_id].append(manager.IndexToNode(index))
plan_output += 'Travel time of the route: {} sec\n'.format(route_time)
print(plan_output)
max_route_time = max(route_time, max_route_time)
print('Maximum of the route time: {} sec'.format(max_route_time))
return(tour)
def main(n_vehicles, cost1, cost2):
number_of_veh = [n_vehicles][0]
solution_found = False
while solution_found == False:
Num_of_Class6 = int(n_vehicles*Percent_of_Class6)
Num_of_Hybrid = n_vehicles - Num_of_Class6
V = list(range(n_vehicles))
V2 = list(set(np.random.choice(V, size=Num_of_Class6, replace=False)))
V1 = list(set(V)-set(V2))
"""Entry point of the program."""
# Instantiate the data problem.
data = create_data_model(number_of_veh)
# Create the routing index manager.
manager = pywrapcp.RoutingIndexManager(len(data['time_matrix']),
data['num_vehicles'], data['depot'])
# Create Routing Model.
routing = pywrapcp.RoutingModel(manager)
'''Major Diff Starts Here'''
# Create and register a transit callback.
def time_callback(from_index, to_index, cost):
"""Returns the time between the two nodes."""
# Convert from routing variable Index to time matrix NodeIndex.
from_node = manager.IndexToNode(from_index)
to_node = manager.IndexToNode(to_index)
return data['time_matrix'][from_node][to_node]*cost
range_extender_callback = partial(time_callback, cost=cost1)
class6_callback = partial(time_callback, cost=cost2)
transit_callback_index_V1 = routing.RegisterTransitCallback(range_extender_callback)
transit_callback_index_V2 = routing.RegisterTransitCallback(class6_callback)
'''Major Diff Ends Here'''
# Define cost of each arc.
for v in V1:
routing.SetArcCostEvaluatorOfVehicle(transit_callback_index_V1, v)
for v in V2:
routing.SetArcCostEvaluatorOfVehicle(transit_callback_index_V2, v)
# Create and register a transit callback.
def time_callback2(from_index, to_index):
"""Returns the time between the two nodes."""
# Convert from routing variable Index to time matrix NodeIndex.
from_node = manager.IndexToNode(from_index)
to_node = manager.IndexToNode(to_index)
if from_node != 0:
return data['time_matrix'][from_node][to_node] + data['service_time'][from_node]
else:
return data['time_matrix'][from_node][to_node]
transit_callback_index2 = routing.RegisterTransitCallback(time_callback2)
# Add Time constraint.
dimension_name = 'Time'
routing.AddDimension(
transit_callback_index2,
0, # no slack
Operational_hours*3600, # vehicle maximum travel time
True, # start cumul to zero
dimension_name)
time_dimension = routing.GetDimensionOrDie(dimension_name)
def demand_callback(from_index):
"""Returns the demand of the node."""
# Convert from routing variable Index to demands NodeIndex.
from_node = manager.IndexToNode(from_index)
return data['demands'][from_node]
demand_callback_index = routing.RegisterUnaryTransitCallback(
demand_callback)
routing.AddDimensionWithVehicleCapacity(
demand_callback_index,
0, # null capacity slack
data['vehicle_capacities'], # vehicle maximum capacities
True, # start cumul to zero
'Capacity')
# Setting first solution heuristic.
search_parameters = pywrapcp.DefaultRoutingSearchParameters()
search_parameters.first_solution_strategy = (
routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC)
search_parameters.local_search_metaheuristic = (
routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH)
search_parameters.time_limit.FromSeconds(VRP_time_limit)
# Solve the problem.
solution = routing.SolveWithParameters(search_parameters)
# Print solution on console.
if solution:
tour = print_solution(data, manager, routing, solution)
solution_found = True
else:
print('No solution found! Increasing the vehicle numbers by one and resolving.\n')
solution_found = False
number_of_veh += 1
return(tour, number_of_veh, V1, V2)
main(n_vehicles, cost1, cost2)
输出为：
Beginning the Googe OR-tools to solve the problem.
---------------------------------------------------------------------------
TypeError Traceback (most recent call last)
<ipython-input-15-0447402a4e3d> in <module>
166 return(tour, number_of_veh, V1, V2)
167
--> 168 final_tour,number_of_veh, V1, V2 = main(n_vehicles, cost1, cost2)
<ipython-input-15-0447402a4e3d> in main(n_vehicles, cost1, cost2)
104 routing.SetArcCostEvaluatorOfVehicle(transit_callback_index_V1, v)
105 for v in V2:
--> 106 routing.SetArcCostEvaluatorOfVehicle(transit_callback_index_V2, v)
107
108 # Create and register a transit callback.
~/.local/lib/python3.7/site-packages/ortools/constraint_solver/pywrapcp.py in SetArcCostEvaluatorOfVehicle(self, evaluator_index, vehicle)
5224 def SetArcCostEvaluatorOfVehicle(self, evaluator_index: "int", vehicle: "int") -> "void":
5225 r""" Sets the cost function for a given vehicle route."""
-> 5226 return _pywrapcp.RoutingModel_SetArcCostEvaluatorOfVehicle(self, evaluator_index, vehicle)
5227
5228 def SetFixedCostOfAllVehicles(self, cost: "int64_t") -> "void":
TypeError: in method 'RoutingModel_SetArcCostEvaluatorOfVehicle', argument 3 of type 'int'
只需注册两个公交回调（即每种车辆类型一个）
然后使用AddDimension() 的重载来传递一个已注册的中转回调索引数组。
为了解决这个问题，我按照Mizux的回答。我有以下 MWE 以供将来考虑。我希望它对某人有所帮助！
from ortools.constraint_solver import routing_enums_pb2
from ortools.constraint_solver import pywrapcp
import numpy as np
from functools import partial
n_vehicles = 4 #Number of vehicles
max_vehicle_tt = 3600 #Maximum travel time for each vehicle (excludes service times)
data = {}
data['time_matrix'] = np.array([[ 0, 1187, 1200, 1110, 1134, 892, 1526, 903, 1482, 1544],
[1232, 0, 13, 90, 67, 426, 537, 419, 493, 555],
[1218, 57, 0, 82, 73, 412, 523, 405, 479, 541],
[1177, 90, 90, 0, 23, 370, 481, 364, 438, 500],
[1187, 80, 67, 23, 0, 380, 491, 374, 448, 509],
[ 870, 390, 403, 314, 337, 0, 729, 17, 686, 747],
[1539, 557, 543, 485, 495, 733, 0, 726, 53, 68],
[ 882, 384, 397, 307, 331, 17, 723, 0, 679, 741],
[1496, 514, 500, 442, 451, 689, 53, 683, 0, 122],
[1584, 602, 588, 530, 539, 777, 68, 771, 122, 0]])
data['num_vehicles'] = n_vehicles
data['depot'] = 0
data['demands'] = [0, 4, 4, 3, 1, 4, 12, 1, 24, 20]
data['vehicle_capacities'] = [30]*data['num_vehicles']
data['service_time'] = [0, 18, 18, 27, 25, 11, 92, 6, 239, 143]
def print_solution(data, manager, routing, solution):
"""Prints solution on console."""
print(f'Objective: {solution.ObjectiveValue()}')
max_route_time = 0; tour = {i:[] for i in range(data['num_vehicles'])}
for vehicle_id in range(data['num_vehicles']):
index = routing.Start(vehicle_id)
plan_output = 'Route for vehicle {}:\n'.format(vehicle_id)
route_time = 0
while not routing.IsEnd(index):
plan_output += ' {} -> '.format(manager.IndexToNode(index))
tour[vehicle_id].append(manager.IndexToNode(index))
previous_index = index
index = solution.Value(routing.NextVar(index))
if previous_index != 0 and previous_index <= len(data['service_time'])-1:
service_time = data['service_time'][previous_index]
else:
service_time = 0
route_time += (routing.GetArcCostForVehicle(
previous_index, index, vehicle_id) + service_time)
plan_output += '{}\n'.format(manager.IndexToNode(index))
tour[vehicle_id].append(manager.IndexToNode(index))
plan_output += 'Travel time of the route: {} sec\n'.format(route_time)
print(plan_output)
max_route_time = max(route_time, max_route_time)
print('Maximum of the route time: {} sec'.format(max_route_time))
return(tour)
def main(n_vehicles, cost1, cost2):
np.random.seed(0)
Num_of_Class6 = int(n_vehicles*0.6)
Num_of_Hybrid = n_vehicles - Num_of_Class6
V = list(range(n_vehicles))
V2 = list(set(np.random.choice(V, size=Num_of_Class6, replace=False)))
V1 = list(set(V)-set(V2))
print('V1:%s'%V1); print('V2:%s'%V2)
# Create the routing index manager.
manager = pywrapcp.RoutingIndexManager(len(data['time_matrix']),
data['num_vehicles'], data['depot'])
# Create Routing Model.
routing = pywrapcp.RoutingModel(manager)
# Create and register a transit callback.
def time_callback(from_index, to_index, cost):
"""Returns the time between the two nodes."""
# Convert from routing variable Index to time matrix NodeIndex.
from_node = manager.IndexToNode(from_index)
to_node = manager.IndexToNode(to_index)
return data['time_matrix'][from_node][to_node]*cost
range_extender_callback = partial(time_callback, cost=cost1)
class6_callback = partial(time_callback, cost=cost2)
transit_callback_index_V1 = routing.RegisterTransitCallback(range_extender_callback)
transit_callback_index_V2 = routing.RegisterTransitCallback(class6_callback)
# Define cost of each arc.
for v in V1:
routing.SetArcCostEvaluatorOfVehicle(transit_callback_index_V1, int(v))
for v in V2:
routing.SetArcCostEvaluatorOfVehicle(transit_callback_index_V2, int(v))
# Create and register a transit callback to limit the total travel+service time
def time_callback2(from_index, to_index):
"""Returns the time between the two nodes."""
# Convert from routing variable Index to time matrix NodeIndex.
from_node = manager.IndexToNode(from_index)
to_node = manager.IndexToNode(to_index)
if from_node != 0:
return data['time_matrix'][from_node][to_node] + data['service_time'][from_node]
else:
return data['time_matrix'][from_node][to_node]
transit_callback_index2 = routing.RegisterTransitCallback(time_callback2)
# Add Time constraint.
dimension_name = 'Time'
routing.AddDimensionWithVehicleCapacity(
transit_callback_index2,
0, # no slack
[max_vehicle_tt]*data['num_vehicles'], # vehicle maximum travel time
True, # start cumul to zero
dimension_name)
time_dimension = routing.GetDimensionOrDie(dimension_name)
def demand_callback(from_index):
"""Returns the demand of the node."""
# Convert from routing variable Index to demands NodeIndex.
from_node = manager.IndexToNode(from_index)
return data['demands'][from_node]
demand_callback_index = routing.RegisterUnaryTransitCallback(
demand_callback)
routing.AddDimensionWithVehicleCapacity(
demand_callback_index,
0, # null capacity slack
data['vehicle_capacities'], # vehicle maximum capacities
True, # start cumul to zero
'Capacity')
# Setting first solution heuristic.
search_parameters = pywrapcp.DefaultRoutingSearchParameters()
search_parameters.first_solution_strategy = (
routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC)
search_parameters.local_search_metaheuristic = (
routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH)
search_parameters.time_limit.FromSeconds(1)
# Solve the problem.
solution = routing.SolveWithParameters(search_parameters)
# Print solution on console.
if solution:
tour = print_solution(data, manager, routing, solution)
return(tour, V1, V2)
else:
print('No solution found!\n')
tour,V1,V2 = main(n_vehicles,0.5,0.7)
奖励：使用以下函数检查关键解决方案指标。
pairs = {}; serv_time = {}; tt ={}; cont_to_obj = {}
for i,j in tour.items():
if len(j) > 2:
serv_time[i] = sum([data['service_time'][k] for k in j])
print('Service time for vehicle %s: %s.'%(i,serv_time[i]))
num_deliveries = sum([data['demands'][k] for k in j])
print('Number of deliveries for vehicle %s: %s.'%(i,num_deliveries))
pairs[i] = list(zip(j,j[1:]))
tt[i] = sum([data['time_matrix'][k] for k in pairs[i]])
print('Travel time for vehicle %s: %s.'%(i,tt))
print('Total time for vehicle %s: %s'%(i,serv_time[i]+tt[i]))
if i in V1:
cont_to_obj[i] = sum([int(data['time_matrix'][k]*0.002244) for k in pairs[i]])
else:
cont_to_obj[i] = sum([int(data['time_matrix'][k]*0.0080517) for k in pairs[i]])
print('Contribution to the obj. fun. for vehicle %s: %s\n'%(i,cont_to_obj[i]))
我正在为时间受限的 CVRP 建模。问题是在受车辆（送货）容量和总花费时间（每辆车）约束的情况下，最小化总行程时间（不包括包裹投递时间）。丢包时间是指在每个节点需要花费的额外时间，花费的总时间等于行程时间加上这个额外时间。我有以下适用于单一车辆类型案例的模型。这里我想介绍一下两车类型的概念，就是说我有一套V1型车和一套V2型车。车辆类型的唯一区别是每次旅行的成本。令x表示V1的单位时间旅行成本，y表示V2的单位时间旅行成本。我怎样才能设计模型以使其包含这个额外的方面？
from ortools.constraint_solver import routing_enums_pb2
from ortools.constraint_solver import pywrapcp
def create_data_model(n_vehicles):
"""Stores the data for the problem."""
data = {}
data['time_matrix'] = TT #travel time
data['num_vehicles'] = n_vehicles
data['depot'] = 0
data['demands'] = demands
data['vehicle_capacities'] = vehicle_capacities
data['service_time'] = service_time
return data
def print_solution(data, manager, routing, solution):
"""Prints solution on console."""
print(f'Objective: {solution.ObjectiveValue()}')
max_route_time = 0; tour = {i:[] for i in range(data['num_vehicles'])}
for vehicle_id in range(data['num_vehicles']):
index = routing.Start(vehicle_id)
plan_output = 'Route for vehicle {}:\n'.format(vehicle_id)
route_time = 0
while not routing.IsEnd(index):
plan_output += ' {} -> '.format(manager.IndexToNode(index))
tour[vehicle_id].append(manager.IndexToNode(index))
previous_index = index
index = solution.Value(routing.NextVar(index))
if previous_index != 0 and previous_index <= len(data['service_time'])-1:
service_time = data['service_time'][previous_index]
else:
service_time = 0
route_time += (routing.GetArcCostForVehicle(
previous_index, index, vehicle_id) + service_time)
plan_output += '{}\n'.format(manager.IndexToNode(index))
tour[vehicle_id].append(manager.IndexToNode(index))
plan_output += 'Travel time of the route: {} sec\n'.format(route_time)
print(plan_output)
max_route_time = max(route_time, max_route_time)
print('Maximum of the route time: {} sec'.format(max_route_time))
return(tour)
def main(n_vehicles):
number_of_veh = [n_vehicles][0]
solution_found = False
while solution_found == False:
"""Entry point of the program."""
# Instantiate the data problem.
data = create_data_model(number_of_veh)
# Create the routing index manager.
manager = pywrapcp.RoutingIndexManager(len(data['time_matrix']),
data['num_vehicles'], data['depot'])
# Create Routing Model.
routing = pywrapcp.RoutingModel(manager)
# Create and register a transit callback.
def time_callback(from_index, to_index):
"""Returns the time between the two nodes."""
# Convert from routing variable Index to time matrix NodeIndex.
from_node = manager.IndexToNode(from_index)
to_node = manager.IndexToNode(to_index)
return data['time_matrix'][from_node][to_node]
transit_callback_index = routing.RegisterTransitCallback(time_callback)
# Define cost of each arc.
routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)
# Create and register a transit callback.
def time_callback2(from_index, to_index):
"""Returns the time between the two nodes."""
# Convert from routing variable Index to time matrix NodeIndex.
from_node = manager.IndexToNode(from_index)
to_node = manager.IndexToNode(to_index)
if from_node != 0:
return data['time_matrix'][from_node][to_node] + data['service_time'][from_node]
else:
return data['time_matrix'][from_node][to_node]
transit_callback_index2 = routing.RegisterTransitCallback(time_callback2)
# Add Time constraint.
dimension_name = 'Time'
routing.AddDimension(
transit_callback_index2,
0, # no slack
Operational_hours*3600, # vehicle maximum travel time
True, # start cumul to zero
dimension_name)
time_dimension = routing.GetDimensionOrDie(dimension_name)
def demand_callback(from_index):
"""Returns the demand of the node."""
# Convert from routing variable Index to demands NodeIndex.
from_node = manager.IndexToNode(from_index)
return data['demands'][from_node]
demand_callback_index = routing.RegisterUnaryTransitCallback(
demand_callback)
routing.AddDimensionWithVehicleCapacity(
demand_callback_index,
0, # null capacity slack
data['vehicle_capacities'], # vehicle maximum capacities
True, # start cumul to zero
'Capacity')
# Setting first solution heuristic.
search_parameters = pywrapcp.DefaultRoutingSearchParameters()
search_parameters.first_solution_strategy = (
routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC)
search_parameters.local_search_metaheuristic = (
routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH)
search_parameters.time_limit.FromSeconds(VRP_time_limit)
# Solve the problem.
solution = routing.SolveWithParameters(search_parameters)
# Print solution on console.
if solution:
tour = print_solution(data, manager, routing, solution)
solution_found = True
else:
print('No solution found! Increasing the vehicle numbers by one and resolving.\n')
solution_found = False
number_of_veh += 1
return(tour, number_of_veh)
编辑
根据@Mizux 的回答，我编写了以下内容，产生了以下错误。
from ortools.constraint_solver import routing_enums_pb2
from ortools.constraint_solver import pywrapcp
def create_data_model(n_vehicles):
"""Stores the data for the problem."""
data = {}
TT = np.array(df.values)
data['time_matrix'] = TT
data['num_vehicles'] = n_vehicles
data['depot'] = 0
data['demands'] = demands
if len(vehicle_capacities) < n_vehicles:
data['vehicle_capacities'] = [vehicle_capacities[0]]*n_vehicles
else:
data['vehicle_capacities'] = vehicle_capacities
data['service_time'] = service_time
return data
def print_solution(data, manager, routing, solution):
"""Prints solution on console."""
print(f'Objective: {solution.ObjectiveValue()}')
max_route_time = 0; tour = {i:[] for i in range(data['num_vehicles'])}
for vehicle_id in range(data['num_vehicles']):
index = routing.Start(vehicle_id)
plan_output = 'Route for vehicle {}:\n'.format(vehicle_id)
route_time = 0
while not routing.IsEnd(index):
plan_output += ' {} -> '.format(manager.IndexToNode(index))
tour[vehicle_id].append(manager.IndexToNode(index))
previous_index = index
index = solution.Value(routing.NextVar(index))
if previous_index != 0 and previous_index <= len(data['service_time'])-1:
service_time = data['service_time'][previous_index]
else:
service_time = 0
route_time += (routing.GetArcCostForVehicle(
previous_index, index, vehicle_id) + service_time)
plan_output += '{}\n'.format(manager.IndexToNode(index))
tour[vehicle_id].append(manager.IndexToNode(index))
plan_output += 'Travel time of the route: {} sec\n'.format(route_time)
print(plan_output)
max_route_time = max(route_time, max_route_time)
print('Maximum of the route time: {} sec'.format(max_route_time))
return(tour)
def main(n_vehicles, cost1, cost2):
number_of_veh = [n_vehicles][0]
solution_found = False
while solution_found == False:
Num_of_Class6 = int(n_vehicles*Percent_of_Class6)
Num_of_Hybrid = n_vehicles - Num_of_Class6
V = list(range(n_vehicles))
V2 = list(set(np.random.choice(V, size=Num_of_Class6, replace=False)))
V1 = list(set(V)-set(V2))
"""Entry point of the program."""
# Instantiate the data problem.
data = create_data_model(number_of_veh)
# Create the routing index manager.
manager = pywrapcp.RoutingIndexManager(len(data['time_matrix']),
data['num_vehicles'], data['depot'])
# Create Routing Model.
routing = pywrapcp.RoutingModel(manager)
'''Major Diff Starts Here'''
# Create and register a transit callback.
def time_callback(from_index, to_index, cost):
"""Returns the time between the two nodes."""
# Convert from routing variable Index to time matrix NodeIndex.
from_node = manager.IndexToNode(from_index)
to_node = manager.IndexToNode(to_index)
return data['time_matrix'][from_node][to_node]*cost
range_extender_callback = partial(time_callback, cost=cost1)
class6_callback = partial(time_callback, cost=cost2)
transit_callback_index_V1 = routing.RegisterTransitCallback(range_extender_callback)
transit_callback_index_V2 = routing.RegisterTransitCallback(class6_callback)
'''Major Diff Ends Here'''
# Define cost of each arc.
for v in V1:
routing.SetArcCostEvaluatorOfVehicle(transit_callback_index_V1, v)
for v in V2:
routing.SetArcCostEvaluatorOfVehicle(transit_callback_index_V2, v)
# Create and register a transit callback.
def time_callback2(from_index, to_index):
"""Returns the time between the two nodes."""
# Convert from routing variable Index to time matrix NodeIndex.
from_node = manager.IndexToNode(from_index)
to_node = manager.IndexToNode(to_index)
if from_node != 0:
return data['time_matrix'][from_node][to_node] + data['service_time'][from_node]
else:
return data['time_matrix'][from_node][to_node]
transit_callback_index2 = routing.RegisterTransitCallback(time_callback2)
# Add Time constraint.
dimension_name = 'Time'
routing.AddDimension(
transit_callback_index2,
0, # no slack
Operational_hours*3600, # vehicle maximum travel time
True, # start cumul to zero
dimension_name)
time_dimension = routing.GetDimensionOrDie(dimension_name)
def demand_callback(from_index):
"""Returns the demand of the node."""
# Convert from routing variable Index to demands NodeIndex.
from_node = manager.IndexToNode(from_index)
return data['demands'][from_node]
demand_callback_index = routing.RegisterUnaryTransitCallback(
demand_callback)
routing.AddDimensionWithVehicleCapacity(
demand_callback_index,
0, # null capacity slack
data['vehicle_capacities'], # vehicle maximum capacities
True, # start cumul to zero
'Capacity')
# Setting first solution heuristic.
search_parameters = pywrapcp.DefaultRoutingSearchParameters()
search_parameters.first_solution_strategy = (
routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC)
search_parameters.local_search_metaheuristic = (
routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH)
search_parameters.time_limit.FromSeconds(VRP_time_limit)
# Solve the problem.
solution = routing.SolveWithParameters(search_parameters)
# Print solution on console.
if solution:
tour = print_solution(data, manager, routing, solution)
solution_found = True
else:
print('No solution found! Increasing the vehicle numbers by one and resolving.\n')
solution_found = False
number_of_veh += 1
return(tour, number_of_veh, V1, V2)
main(n_vehicles, cost1, cost2)
输出为：
Beginning the Googe OR-tools to solve the problem.
---------------------------------------------------------------------------
TypeError Traceback (most recent call last)
<ipython-input-15-0447402a4e3d> in <module>
166 return(tour, number_of_veh, V1, V2)
167
--> 168 final_tour,number_of_veh, V1, V2 = main(n_vehicles, cost1, cost2)
<ipython-input-15-0447402a4e3d> in main(n_vehicles, cost1, cost2)
104 routing.SetArcCostEvaluatorOfVehicle(transit_callback_index_V1, v)
105 for v in V2:
--> 106 routing.SetArcCostEvaluatorOfVehicle(transit_callback_index_V2, v)
107
108 # Create and register a transit callback.
~/.local/lib/python3.7/site-packages/ortools/constraint_solver/pywrapcp.py in SetArcCostEvaluatorOfVehicle(self, evaluator_index, vehicle)
5224 def SetArcCostEvaluatorOfVehicle(self, evaluator_index: "int", vehicle: "int") -> "void":
5225 r""" Sets the cost function for a given vehicle route."""
-> 5226 return _pywrapcp.RoutingModel_SetArcCostEvaluatorOfVehicle(self, evaluator_index, vehicle)
5227
5228 def SetFixedCostOfAllVehicles(self, cost: "int64_t") -> "void":
TypeError: in method 'RoutingModel_SetArcCostEvaluatorOfVehicle', argument 3 of type 'int'
只需注册两个公交回调（即每种车辆类型一个）
然后使用AddDimension() 的重载来传递一个已注册的中转回调索引数组。
为了解决这个问题，我按照Mizux的回答。我有以下 MWE 以供将来考虑。我希望它对某人有所帮助！
from ortools.constraint_solver import routing_enums_pb2
from ortools.constraint_solver import pywrapcp
import numpy as np
from functools import partial
n_vehicles = 4 #Number of vehicles
max_vehicle_tt = 3600 #Maximum travel time for each vehicle (excludes service times)
data = {}
data['time_matrix'] = np.array([[ 0, 1187, 1200, 1110, 1134, 892, 1526, 903, 1482, 1544],
[1232, 0, 13, 90, 67, 426, 537, 419, 493, 555],
[1218, 57, 0, 82, 73, 412, 523, 405, 479, 541],
[1177, 90, 90, 0, 23, 370, 481, 364, 438, 500],
[1187, 80, 67, 23, 0, 380, 491, 374, 448, 509],
[ 870, 390, 403, 314, 337, 0, 729, 17, 686, 747],
[1539, 557, 543, 485, 495, 733, 0, 726, 53, 68],
[ 882, 384, 397, 307, 331, 17, 723, 0, 679, 741],
[1496, 514, 500, 442, 451, 689, 53, 683, 0, 122],
[1584, 602, 588, 530, 539, 777, 68, 771, 122, 0]])
data['num_vehicles'] = n_vehicles
data['depot'] = 0
data['demands'] = [0, 4, 4, 3, 1, 4, 12, 1, 24, 20]
data['vehicle_capacities'] = [30]*data['num_vehicles']
data['service_time'] = [0, 18, 18, 27, 25, 11, 92, 6, 239, 143]
def print_solution(data, manager, routing, solution):
"""Prints solution on console."""
print(f'Objective: {solution.ObjectiveValue()}')
max_route_time = 0; tour = {i:[] for i in range(data['num_vehicles'])}
for vehicle_id in range(data['num_vehicles']):
index = routing.Start(vehicle_id)
plan_output = 'Route for vehicle {}:\n'.format(vehicle_id)
route_time = 0
while not routing.IsEnd(index):
plan_output += ' {} -> '.format(manager.IndexToNode(index))
tour[vehicle_id].append(manager.IndexToNode(index))
previous_index = index
index = solution.Value(routing.NextVar(index))
if previous_index != 0 and previous_index <= len(data['service_time'])-1:
service_time = data['service_time'][previous_index]
else:
service_time = 0
route_time += (routing.GetArcCostForVehicle(
previous_index, index, vehicle_id) + service_time)
plan_output += '{}\n'.format(manager.IndexToNode(index))
tour[vehicle_id].append(manager.IndexToNode(index))
plan_output += 'Travel time of the route: {} sec\n'.format(route_time)
print(plan_output)
max_route_time = max(route_time, max_route_time)
print('Maximum of the route time: {} sec'.format(max_route_time))
return(tour)
def main(n_vehicles, cost1, cost2):
np.random.seed(0)
Num_of_Class6 = int(n_vehicles*0.6)
Num_of_Hybrid = n_vehicles - Num_of_Class6
V = list(range(n_vehicles))
V2 = list(set(np.random.choice(V, size=Num_of_Class6, replace=False)))
V1 = list(set(V)-set(V2))
print('V1:%s'%V1); print('V2:%s'%V2)
# Create the routing index manager.
manager = pywrapcp.RoutingIndexManager(len(data['time_matrix']),
data['num_vehicles'], data['depot'])
# Create Routing Model.
routing = pywrapcp.RoutingModel(manager)
# Create and register a transit callback.
def time_callback(from_index, to_index, cost):
"""Returns the time between the two nodes."""
# Convert from routing variable Index to time matrix NodeIndex.
from_node = manager.IndexToNode(from_index)
to_node = manager.IndexToNode(to_index)
return data['time_matrix'][from_node][to_node]*cost
range_extender_callback = partial(time_callback, cost=cost1)
class6_callback = partial(time_callback, cost=cost2)
transit_callback_index_V1 = routing.RegisterTransitCallback(range_extender_callback)
transit_callback_index_V2 = routing.RegisterTransitCallback(class6_callback)
# Define cost of each arc.
for v in V1:
routing.SetArcCostEvaluatorOfVehicle(transit_callback_index_V1, int(v))
for v in V2:
routing.SetArcCostEvaluatorOfVehicle(transit_callback_index_V2, int(v))
# Create and register a transit callback to limit the total travel+service time
def time_callback2(from_index, to_index):
"""Returns the time between the two nodes."""
# Convert from routing variable Index to time matrix NodeIndex.
from_node = manager.IndexToNode(from_index)
to_node = manager.IndexToNode(to_index)
if from_node != 0:
return data['time_matrix'][from_node][to_node] + data['service_time'][from_node]
else:
return data['time_matrix'][from_node][to_node]
transit_callback_index2 = routing.RegisterTransitCallback(time_callback2)
# Add Time constraint.
dimension_name = 'Time'
routing.AddDimensionWithVehicleCapacity(
transit_callback_index2,
0, # no slack
[max_vehicle_tt]*data['num_vehicles'], # vehicle maximum travel time
True, # start cumul to zero
dimension_name)
time_dimension = routing.GetDimensionOrDie(dimension_name)
def demand_callback(from_index):
"""Returns the demand of the node."""
# Convert from routing variable Index to demands NodeIndex.
from_node = manager.IndexToNode(from_index)
return data['demands'][from_node]
demand_callback_index = routing.RegisterUnaryTransitCallback(
demand_callback)
routing.AddDimensionWithVehicleCapacity(
demand_callback_index,
0, # null capacity slack
data['vehicle_capacities'], # vehicle maximum capacities
True, # start cumul to zero
'Capacity')
# Setting first solution heuristic.
search_parameters = pywrapcp.DefaultRoutingSearchParameters()
search_parameters.first_solution_strategy = (
routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC)
search_parameters.local_search_metaheuristic = (
routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH)
search_parameters.time_limit.FromSeconds(1)
# Solve the problem.
solution = routing.SolveWithParameters(search_parameters)
# Print solution on console.
if solution:
tour = print_solution(data, manager, routing, solution)
return(tour, V1, V2)
else:
print('No solution found!\n')
tour,V1,V2 = main(n_vehicles,0.5,0.7)
奖励：使用以下函数检查关键解决方案指标。
pairs = {}; serv_time = {}; tt ={}; cont_to_obj = {}
for i,j in tour.items():
if len(j) > 2:
serv_time[i] = sum([data['service_time'][k] for k in j])
print('Service time for vehicle %s: %s.'%(i,serv_time[i]))
num_deliveries = sum([data['demands'][k] for k in j])
print('Number of deliveries for vehicle %s: %s.'%(i,num_deliveries))
pairs[i] = list(zip(j,j[1:]))
tt[i] = sum([data['time_matrix'][k] for k in pairs[i]])
print('Travel time for vehicle %s: %s.'%(i,tt))
print('Total time for vehicle %s: %s'%(i,serv_time[i]+tt[i]))
if i in V1:
cont_to_obj[i] = sum([int(data['time_matrix'][k]*0.002244) for k in pairs[i]])
else:
cont_to_obj[i] = sum([int(data['time_matrix'][k]*0.0080517) for k in pairs[i]])
print('Contribution to the obj. fun. for vehicle %s: %s\n'%(i,cont_to_obj[i]))