我是 OR-Tools 库的新手。我正在尝试解决容量和时间窗口限制的提货和交付问题。该代码在 5 个位置节点（2 个提货和 2 个交付位置以及 1 个仓库位置）上运行良好。但是，当我将节点数更改为 17（具有 1 个仓库位置）时，代码不起作用，并且内核在 Python 3.5 的 Spyder 编辑器中死机而没有给出任何错误。而且，如果我在终端中运行它，它会产生以下输出。
terminate called after throwing an instance of 'std::bad_alloc'
what(): std::bad_alloc
Aborted (core dumped)
系统规格为：OS-Ubuntu 16.04 LTS，Python 版本 - 3.5.2，OR-Tools 版本 - 7.7，RAM - 8GB，图形 - 2GB AMD Radeon。我通过结合 OR-Tools 网站上给出的示例代码的相关部分来编写代码。以下是 16 个节点不工作的代码：
from __future__ import print_function
from ortools.constraint_solver import routing_enums_pb2
from ortools.constraint_solver import pywrapcp
def create_data_model():
"""Stores the data for the problem."""
data = {}
data['time_matrix'] = [
[0, 6, 9, 8, 7, 3, 6, 2, 3, 2, 6, 6, 4, 4, 5, 9, 7],
[6, 0, 8, 3, 2, 6, 8, 4, 8, 8, 13, 7, 5, 8, 12, 10, 14],
[9, 8, 0, 11, 10, 6, 3, 9, 5, 8, 4, 15, 14, 13, 9, 18, 9],
[8, 3, 11, 0, 1, 7, 10, 6, 10, 10, 14, 6, 7, 9, 14, 6, 16],
[7, 2, 10, 1, 0, 6, 9, 4, 8, 9, 13, 4, 6, 8, 12, 8, 14],
[3, 6, 6, 7, 6, 0, 2, 3, 2, 2, 7, 9, 7, 7, 6, 12, 8],
[6, 8, 3, 10, 9, 2, 0, 6, 2, 5, 4, 12, 10, 10, 6, 15, 5],
[2, 4, 9, 6, 4, 3, 6, 0, 4, 4, 8, 5, 4, 3, 7, 8, 10],
[3, 8, 5, 10, 8, 2, 2, 4, 0, 3, 4, 9, 8, 7, 3, 13, 6],
[2, 8, 8, 10, 9, 2, 5, 4, 3, 0, 4, 6, 5, 4, 3, 9, 5],
[6, 13, 4, 14, 13, 7, 4, 8, 4, 4, 0, 10, 9, 8, 4, 13, 4],
[6, 7, 15, 6, 4, 9, 12, 5, 9, 6, 10, 0, 1, 3, 7, 3, 10],
[4, 5, 14, 7, 6, 7, 10, 4, 8, 5, 9, 1, 0, 2, 6, 4, 8],
[4, 8, 13, 9, 8, 7, 10, 3, 7, 4, 8, 3, 2, 0, 4, 5, 6],
[5, 12, 9, 14, 12, 6, 6, 7, 3, 3, 4, 7, 6, 4, 0, 9, 2],
[9, 10, 18, 6, 8, 12, 15, 8, 13, 9, 13, 3, 4, 5, 9, 0, 9],
[7, 14, 9, 16, 14, 8, 5, 10, 6, 5, 4, 10, 8, 6, 2, 9, 0],
]
data['time_windows'] = [
(0, 1800), # depot
(0, 1800), # 1
(0, 1800), # 2
(0, 1800), # 3
(0, 1800), # 4
(0, 1800), # 5
(0, 1800), # 6
(0, 1800), # 7
(0, 1800), # 8
(0, 1800), # 9
(0, 1800), # 10
(0, 1800), # 11
(0, 1800), # 12
(0, 1800), # 13
(0, 1800), # 14
(0, 1800), # 15
(0, 1800), # 16
]
data['pickups_deliveries'] = [
[1, 6], #2
[2, 10], #4
[4, 3], #1
[5, 9], #2
[7, 8], #5
[15, 11], #3
[13, 12], #1
[16, 14], #3
[6, 15], #5
[7, 14], #6
[12, 9], #3
]
data['demands'] = [0, 2, 4, -1, 1, 2, 3, 11, -5, -5, -4, -3, 2, 1, -9, -2, 3]
data['vehicle_capacities'] = [20, 20, 20, 20]
data['num_vehicles'] = 4
data['depot'] = 0
return data
def print_solution(data, manager, routing, solution):
"""Prints solution on console."""
time_dimension = routing.GetDimensionOrDie('Time')
total_time = 0
for vehicle_id in range(data['num_vehicles']):
index = routing.Start(vehicle_id)
plan_output = 'Route for vehicle {}:\n'.format(vehicle_id)
while not routing.IsEnd(index):
time_var = time_dimension.CumulVar(index)
plan_output += '{0} Time({1},{2}) -> '.format(
manager.IndexToNode(index), solution.Min(time_var),
solution.Max(time_var))
index = solution.Value(routing.NextVar(index))
time_var = time_dimension.CumulVar(index)
plan_output += '{0} Time({1},{2})\n'.format(manager.IndexToNode(index),
solution.Min(time_var),
solution.Max(time_var))
plan_output += 'Time of the route: {}min\n'.format(
solution.Min(time_var))
print(plan_output)
total_time += solution.Min(time_var)
print('Total time of all routes: {}min'.format(total_time))
def main():
"""Solve the VRP with time windows."""
# Instantiate the data problem.
data = create_data_model()
# 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 travel 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)
# Add Time Windows constraint.
time = 'Time'
routing.AddDimension(
transit_callback_index,
30000, # allow waiting time
3000, # maximum time per vehicle
False, # Don't force start cumul to zero.
time)
time_dimension = routing.GetDimensionOrDie(time)
# Add time window constraints for each location except depot.
for location_idx, time_window in enumerate(data['time_windows']):
if location_idx == 0:
continue
index = manager.NodeToIndex(location_idx)
time_dimension.CumulVar(index).SetRange(time_window[0], time_window[1])
# Add time window constraints for each vehicle start node.
for vehicle_id in range(data['num_vehicles']):
index = routing.Start(vehicle_id)
time_dimension.CumulVar(index).SetRange(data['time_windows'][0][0],
data['time_windows'][0][1])
# Instantiate route start and end times to produce feasible times.
for i in range(data['num_vehicles']):
routing.AddVariableMinimizedByFinalizer(
time_dimension.CumulVar(routing.Start(i)))
routing.AddVariableMinimizedByFinalizer(
time_dimension.CumulVar(routing.End(i)))
# Define Transportation Requests.
for request in data['pickups_deliveries']:
pickup_index = manager.NodeToIndex(request[0])
delivery_index = manager.NodeToIndex(request[1])
routing.AddPickupAndDelivery(pickup_index, delivery_index)
routing.solver().Add(
routing.VehicleVar(pickup_index) == routing.VehicleVar(
delivery_index))
routing.solver().Add(
time_dimension.CumulVar(pickup_index) <=
time_dimension.CumulVar(delivery_index))
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)
# Solve the problem.
solution = routing.SolveWithParameters(search_parameters)
# Print solution on console.
if solution:
print_solution(data, manager, routing, solution)
print("Status", routing.status())
if __name__ == '__main__':
main()
我正在用以下 5 个节点的情况替换 create_data_model() 函数，这是有效的：
def create_data_model():
"""Stores the data for the problem."""
data = {}
data['time_matrix'] = [
[0, 6, 9, 8, 7],
[6, 0, 8, 3, 2],
[9, 8, 0, 11, 10],
[8, 3, 11, 0, 1],
[7, 2, 10, 1, 0],
]
data['time_windows'] = [
(0, 180), # depot
(0, 180), # 1
(0, 180), # 2
(0, 180), # 3
(0, 180), # 4
]
data['pickups_deliveries'] = [
[1, 3], #2
[2, 4], #4 ripler
#3
]
data['demands'] = [0, 2, 4, -2, -4]
data['vehicle_capacities'] = [2, 7]
data['num_vehicles'] = 2
data['depot'] = 0
return data