OR-Tools 9.4.1874+版本多车辆VRP求解触发std::bad_alloc异常

我使用Python 3.10.12结合OR-Tools库求解车辆路径问题（VRP），当设置4辆车辆时求解器崩溃，抛出std::bad_alloc异常；仅使用1辆车辆时无此问题。

该异常仅在OR-Tools版本高于9.4.1874时出现。我已尝试以下方案但未解决问题：

• 查阅GitHub Issue #3975，设置search_parameters.local_search_operators.use_shortest_path_swap_active = "BOOL_FALSE"
• 更换TABU_SEARCH、GREEDY_DESCENT、SIMULATED_ANNEALING等局部搜索元启发式

相关代码如下：

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  )
    sol = solver.solve()
    print(sol)
    pass

if __name__ == "__main__":
    main()

内容的提问来源于stack exchange，提问作者Federico Raffoni