车辆路径问题中_get_start_solution函数触发IndexError求助

问题描述 #

实现车辆路径问题（VRP）时，执行_get_start_solution函数触发IndexError，错误发生在打印最终解决方案的语句中。

错误回溯 #

Traceback (most recent call last):
  File "C:\Users\hajar\Desktop\lns_v_test_epsilon\lns\test_alpha_gamma.py", line 128, in <module>
    main()
  File "C:\Users\hajar\Desktop\lns_v_test_epsilon\lns\test_alpha_gamma.py", line 124, in main
    test(epsilon, gamma, alpha)
  File "C:\Users\hajar\Desktop\lns_v_test_epsilon\lns\test_alpha_gamma.py", line 96, in test
    solution = alg.solve(problem, start_time,type="eps_greedy", method="TS",eps=epsilon, ensemble=[])
               ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "C:\Users\hajar\Desktop\lns_v_test_epsilon\lns\algorithm.py", line 704, in solve
    start_solution = self._get_start_solution(problem)
                     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "C:\Users\hajar\Desktop\lns_v_test_epsilon\lns\algorithm.py", line 802, in _get_start_solution
    f"Final solution: {solution.routes}, "
  File "C:\Users\hajar\Desktop\lns_v_test_epsilon\lns\solution.py", line 391, in __repr__
    self.earliest[i],
    ~~~~~~~~~~~~~^^^
IndexError: list index out of range

相关代码片段 #

_get_start_solution函数

def _get_start_solution(self, problem):
    """
    Generate an initial solution for the problem by assigning requests to vehicles
    based on vehicle capacity and customer demands.

    Parameters
    ----------
    problem : `Problem`
        The optimization problem containing vehicles and requests.

    Returns
    -------
    solution : `Solution`
        The initial solution object with routes for all vehicles.
    """
    # Initialize the solution object
    solution = Solution(problem)

    num_customers = len(problem.P)  # Number of customers (pickup points)
    print(f"Number of customers: {num_customers}")

    # Default vehicle capacity, adjust if capacity is stored elsewhere in problem
    vehicle_capacity = getattr(problem.vehicles[0], 'capacity', 100)  # Get vehicle capacity from the first vehicle
    print(f"Vehicle capacity: {vehicle_capacity}")

    # Initialize routes and remaining capacities for each vehicle
    routes = []
    capacities = []
    vehicle_id = 0  # Start vehicle IDs from 0

    # Create a list of customers (excluding depot which is assumed to be customer 0)
    customers = list(range(1, num_customers + 1))  # Only customers, not the depot
    print(f"Shuffling customers: {customers}")
    random.shuffle(customers)

    # Create a new route whenever the vehicle is full
    current_route = []
    current_capacity = vehicle_capacity

    # Iterate over the shuffled customers and assign them to vehicles
    for customer_id in customers:
        if customer_id not in problem.P:
            print(f"Customer {customer_id} not found in problem.P")
            continue  # Skip this customer if they do not exist
        # Get the demand of the customer (assuming demand is stored in 'load')
        demand = problem.P[customer_id].load  # Adjust if demand attribute is different
        print(f"Customer {customer_id} demand: {demand}")

        # Check if the current vehicle can accommodate the customer's demand
        if current_capacity >= demand:
            current_route.append(customer_id)
            current_capacity -= demand

            # Remove the customer from the request bank as it is now assigned
            if customer_id in solution.request_bank:
                solution.request_bank.remove(customer_id)
        else:
            # If the current vehicle is full, finalize the current route and start a new one
            if current_route:  # Only append if current_route is not empty
                route = Route(problem, vehicle_id)
                route.route = current_route  # Assign the customers to the route
                routes.append(route)  # Add the completed route to the routes list

            # Start a new route with a new vehicle
            current_route = [customer_id]
            current_capacity = vehicle_capacity - demand

            # Remove the customer from the request bank as it is now assigned
            if customer_id in solution.request_bank:
                solution.request_bank.remove(customer_id)

            # Increment vehicle ID for the next route
            vehicle_id += 1

    # Add the final route (if there are still customers left)
    if current_route:
        route = Route(problem, vehicle_id)
        route.route = current_route  # Assign the customers to the route
        routes.append(route)  # Add the last route to the routes list

    # Check if all requests have been assigned to a route
    if 0 in solution.request_bank:  # Check if depot is in the request bank (shouldn't be)
        solution.request_bank.remove(0)  # Remove depot if present

    if len(solution.request_bank) > 0:
        print(f"Remaining in request bank: {solution.request_bank}")
        raise IndexError("There are not enough vehicles to assign all requests")

    # Filter the routes to include only those that were used
    solution.routes = routes  # Use the routes list created earlier
    print(
         f"Final solution: {solution.routes}, "
         f"Number of routes: {len(solution.routes)}, "
         f"Number of vehicles used: {solution._number_of_used_vehicles()}"
     )
    # Rebuild insert matrices to reflect the current state of the solution
    solution._rebuild_insert_matrices()

    return solution


def _rebuild_insert_matrices(self):
    """
    (Re)build the insert matrices.

    This method (re)builds _delta_f and _best_insert_position.
    Matrices needed by the insert heuristics.
    """
    # Creating and initializing matrices
    self._delta_f = [[float('inf')]*len(self.routes) for x in range(self.problem.n)]
    self._best_insert_position = [[-1]*len(self.routes) for x in range(self.problem.n)]

    # For each route
    for route_id in self.available_vehicles:
        self._update_best_insert_route(route_id)

Route.__repr__方法

def __repr__(self):
    result = "* Total current cost: %s \n" % self.cost
    result += "* (node: [start, departure_load]):\n"
    for i in range(len(self.route)):
        result += "(%s: [%s, %s]) --> " % (self.route[i],
                                           self.earliest[i],
                                           self.loads[i])
    return result

测试数据 #

B-n31-k5
runtime: 831.782910
 VEHICLE
 NUMBER     CAPACITY
 100000                     100

CUSTOMER
CUST NO.  XCOORD.    YCOORD.    DEMAND

  0             17                76                 0
  1             24            6              25
  2             96            29             3
  3             14            19            13
  4             14            32            17
  5             0            34              16
  6             16           22            9
  7              20           26            22
  8             22            28            10
  9             17            23            16
 10             98            30              8
 11             30            8              3
 12             23             27           16
 13             19             23            16
 14              34            7             10
 15              31             7            24
 16             0            37            16
 17             19            23             15
 18             0             36              14
 19             26             7             5
 20              98              32            12
 21             5               40         2
 22             17             26              18
 23              21             26             20
 24             28              8            15
 25             1             35            8
 26            27             28            22
 27             99             30            15
 28              26             28              10
 29            17            29            13
 30            20            26            19

错误原因分析 #

1. Route属性未同步初始化：在_get_start_solution中，创建Route对象后直接给route.route赋值，但Route类的earliest和loads列表未同步更新。__repr__方法遍历self.route索引时，earliest/loads长度小于self.route长度，导致索引越界。
2. VRP路由逻辑缺失depot：标准VRP路由需从depot（ID 0）出发并返回，但当前代码的current_route仅包含客户ID，未包含depot，可能导致Route内部预期节点数量与实际不符。
3. 直接赋值路由属性的风险：绕过Route类内部逻辑直接修改route属性，导致earliest、loads、cost等依赖属性未正确初始化。

修复步骤 #

1. 修复Route类的路由设置逻辑 #

不要直接给route.route赋值，添加add_customers方法同步初始化所有相关属性：

class Route:
    def __init__(self, problem, vehicle_id):
        self.problem = problem
        self.vehicle_id = vehicle_id
        self.route = []
        self.earliest = []
        self.loads = []
        self.cost = 0.0

    def add_customers(self, customer_ids):
        # 包含depot作为起点和终点
        self.route = [0] + customer_ids + [0]
        # 初始化earliest：默认每个节点最早出发时间为0，可根据问题调整
        self.earliest = [0.0] * len(self.route)
        # 初始化loads：从车辆满容量开始递减
        capacity = self.problem.vehicles[self.vehicle_id].capacity
        current_load = capacity
        self.loads = [current_load]
        for cust_id in customer_ids:
            current_load -= self.problem.P[cust_id].load
            self.loads.append(current_load)
        # 回到depot时负载清零
        self.loads.append(0.0)
        # 计算路由成本（需实现对应成本计算逻辑）
        self.calculate_cost()

在_get_start_solution中替换直接赋值代码：

# 替换 route.route = current_route
route.add_customers(current_route)

2. 增强__repr__方法的鲁棒性 #

添加长度检查避免索引错误：

def __repr__(self):
    result = f"* Total current cost: {self.cost}\n"
    result += "* (node: [start, departure_load]):\n"
    # 取三个列表的最小长度遍历
    min_len = min(len(self.route), len(self.earliest), len(self.loads))
    for i in range(min_len):
        result += f"({self.route[i]}: [{self.earliest[i]}, {self.loads[i]}]) --> "
    # 移除末尾多余的箭头
    return result.rstrip(" --> ")

3. 验证客户分配完整性 #

在_get_start_solution末尾添加验证，确保所有客户都被分配：

# 检查所有客户是否已分配
assigned_customers = set()
for route in solution.routes:
    assigned_customers.update(cust_id for cust_id in route.route if cust_id != 0)
expected_customers = set(range(1, num_customers + 1))
unassigned = expected_customers - assigned_customers
if unassigned:
    raise ValueError(f"未分配的客户：{unassigned}")

路由管理优化建议 #

1. 封装路由操作：所有路由修改（添加/删除节点）都通过Route类的方法完成，避免直接修改属性，保证内部状态一致。
2. 强制包含depot：标准VRP路由必须包含起点和终点的depot，否则后续路径成本、时间窗验证都会出错。
3. 添加路由验证逻辑：将路由添加到solution.routes前，检查earliest、loads、cost等属性是否已正确初始化，避免无效路由进入解决方案。
4. 统一路由添加入口：在Solution类中添加add_route方法，统一处理路由的验证和状态同步。

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