我正在尝试使用 python 中的 OR-tools 库解决车辆路径问题
3.10.12使用所使用的设置，求解器崩溃。我不明白问题是什么，如果我只使用一辆车就不会发生这种情况。
我已经阅读了这个问题（https://github.com/google/or-tools/issues/3975），即使使用此命令：
search_parameters.local_search_operators.use_shortest_path_swap_active = "BOOL_FALSE"此问题仅存在于高于
9.4.1874terminate called after throwing an instance of 'std::bad_alloc' what(): std::bad_alloc Aborted
from typing import List
from google.protobuf import duration_pb2
from ortools.constraint_solver import routing_enums_pb2
from ortools.constraint_solver import pywrapcp
from datetime import time
class Location:
def __init__(self, id) -> None:
self.id = id
def isDepot(self) -> bool:
return False # Default implementation returns False
def isStep(self) -> bool:
return False # Default implementation returns False
class Magazzino(Location):
def __init__(self, id) -> None:
super().__init__( 0)
def isDepot(self) -> bool:
return True
class Step(Location):
def __init__(self, id , type, seq_ordine) -> None:
super().__init__(id )
self.id_step = id # step.id_step
self.id_ordine = 1 # step.id_ordine
self.tipo_step = type # step.tipo_step
self.seq_ordine = seq_ordine # step.seq_ordine
def isStep(self) -> bool:
return True
class VRPSolver:
def __init__(self, steps : List[Step], depots : List[Magazzino] ):
self.steps = steps
combined_locations = depots + steps
self.step_id_to_index = { loc.id: idx for idx, loc in enumerate(combined_locations) if loc.isStep()} # Map custom IDs to indices
self.index_to_obj = {idx: obj for idx , obj in enumerate(combined_locations)} # Reverse map
print("STEP_ID_TO_INDEX:" , self.step_id_to_index)
self.data = {
'distance_matrix': [[ 0, 21, 209, 106, 132, 121],
[ 21, 0, 220, 127, 122, 128],
[209, 220, 0, 214, 341, 311],
[106, 127, 214, 0, 188, 116],
[132, 122, 341, 188, 0, 94],
[121, 128, 311, 116, 94, 0]],
'time_matrix': [[ 0, 19, 193, 98, 122, 112],
[ 19, 0, 203, 117, 113, 118],
[193, 203, 0, 198, 315, 287],
[ 98, 117, 198, 0, 174, 107],
[122, 113, 315, 174, 0, 87],
[112, 118, 287, 107, 87, 0]],
'num_vehicles': 4,
'depot': 0,
'vehicle_capacities': [ 100 ] * 4,
'pickups_deliveries': [],
'vehicle_constraints' : {}
}
# self.vehicle_constraint() # RIMOSSO PERCHé CHIAMATO DAL LOGIC
self.consequential_constraint()
print(self.data)
def consequential_constraint(self):
order_steps = {}
for s in self.steps:
if s.id_ordine not in order_steps:
order_steps[s.id_ordine] = []
order_steps[s.id_ordine].append(s)
print("ORDER_STEP",order_steps)
# Determine pickup and delivery pairs
for order in order_steps.values():
pickups = {s for s in order if s.tipo_step == 'R'}
deliveries = {s for s in order if s.tipo_step == 'C'}
for p in pickups:
for d in deliveries:
if d.seq_ordine > p.seq_ordine :
self.add_pickup_delivery(p.id, d.id)
print("PICKUP : " + str(p.id) + " C : " + str(d.id))
def add_pickup_delivery(self, pickup_id, delivery_id):
pickup_index = self.step_id_to_index[pickup_id]
delivery_index = self.step_id_to_index[delivery_id]
self.data['pickups_deliveries'].append([pickup_index, delivery_index])
def solve(self):
manager = pywrapcp.RoutingIndexManager(
len(self.data['distance_matrix']), self.data['num_vehicles'], self.data['depot']
)
routing = pywrapcp.RoutingModel(manager)
##### TIME ######
def time_callback(from_index, to_index):
from_node = manager.IndexToNode(from_index)
to_node = manager.IndexToNode(to_index)
return self.data['time_matrix'][from_node][to_node]
time_callback_index = routing.RegisterTransitCallback(time_callback)
# Add Time Dimension
routing.AddDimension(
time_callback_index,
60, # Allow for some waiting time
30000, # Large enough to not overly restrict route maximum time
False, # Don't force start cumul to zero. This doesn't force the vehicle to start right at the time at the depot
'Time'
)
time_dimension = routing.GetDimensionOrDie('Time')
time_dimension.SetGlobalSpanCostCoefficient(1) # Adjust this to give time some influence but less than distance
###### DISTANCE ######
def distance_callback(from_index, to_index):
from_node = manager.IndexToNode(from_index)
to_node = manager.IndexToNode(to_index)
return self.data['distance_matrix'][from_node][to_node]
transit_callback_index = routing.RegisterTransitCallback(distance_callback)
routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)
# Add distance dimension
routing.AddDimension(
transit_callback_index, 0, 10000, True, 'Distance'
)
distance_dimension = routing.GetDimensionOrDie('Distance')
distance_dimension.SetGlobalSpanCostCoefficient(1)
# Add pickup and delivery
for request in self.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(
distance_dimension.CumulVar(pickup_index) <= distance_dimension.CumulVar(delivery_index)
)
search_parameters = pywrapcp.DefaultRoutingSearchParameters()
search_parameters.first_solution_strategy = (
routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC # Less intensive strategy
)
search_parameters.local_search_metaheuristic = (
routing_enums_pb2.LocalSearchMetaheuristic.TABU_SEARCH # Change the metaheuristic
)
search_parameters.local_search_operators.use_shortest_path_swap_active = "BOOL_FALSE"
search_parameters.time_limit.seconds = 1 # Limit the search time
search_parameters.log_search = True # Enable logging
solution = routing.SolveWithParameters(search_parameters)
if solution:
return solution
def main():
all_magazzini = [ Magazzino(id=0),
Magazzino(id=1 ) ]
all_step = []
all_step.append(Step(1, 'C', 4))
all_step.append(Step(2, 'R', 1))
all_step.append(Step(3, 'C', 3))
all_step.append(Step(4, 'R', 2))
solver = VRPSolver( steps= all_step, depots = all_magazzini )# , vehicles = vehicles, depot=0, locations=locations)
sol = solver.solve()
print(sol)
pass
if __name__ == "__main__":
main()
我尝试过使用9.4以上的所有版本，但都不起作用。
我也尝试了建议的解决方案
search_parameters.local_search_operators.use_shortest_path_swap_active = "BOOL_FALSE"但什么都没有改变。
我尝试过不同的 local_search_metaheuristic。
该错误是由于为同一个提货输入了不同的交货而引起的。 通过这样做，最新版本无法解决问题，引发上述异常。
出于某种我不知道的原因，9.4 版本能够解决该问题，尽管该解决方案不是最佳的。
为了克服这个问题，需要复制节点，以便每个节点仅位于 1 个 P&D 对中