如何基于NetworkX网络，使用OptaPy构建垃圾收集VRP解决方案？

首先明确：NetworkX可用于构建和处理VRP的网络拓扑（如节点、边、最短路径计算），但它不是优化求解器；OptaPy作为Python约束优化框架，适合解决这类带容量限制、倾倒区规则的车辆路径问题。

以下是具体实现步骤：

一、数据准备：对接NetworkX网络 #

• 从已构建的NetworkX网络中导出核心数据：
  • 提取所有节点，标记出车场（AJ、A、G、R）、倾倒区（F、AQ、AA）和普通节点
  • 导出每条边的垃圾量权重，并用NetworkX的shortest_path_length预计算任意节点到各倾倒区的最短路径，用于后续触发倾倒时选择最近点
• 定义Python数据类封装核心要素：
  • Location：包含节点ID、是否为车场、是否为倾倒区属性
  • Vehicle：关联归属车场、固定承载容量属性
  • RouteSegment：记录路段的起点、终点、垃圾量

二、OptaPy模型定义 #

1. 规划实体类 #

用@planning_entity定义车辆路径实体，通过规划变量描述路径的节点序列：

from optapy import planning_entity, planning_id, planning_list_variable

@planning_entity
class VehicleRoute:
    @planning_id
    def __init__(self, vehicle, start_depot):
        self.vehicle = vehicle
        self.start_depot = start_depot
        self.visited_locations = []  # 存储途经的普通节点、倾倒区
        self.current_load = 0

    @planning_list_variable(Location, value_range_provider_refs=["all_locations"])
    def get_visited_locations(self):
        return self.visited_locations

    def set_visited_locations(self, visited_locations):
        self.visited_locations = visited_locations

2. 约束规则定义 #

用@constraint_provider实现所有业务约束，区分硬约束（必须满足）和软约束（优化目标）：

from optapy import constraint_provider, Joiners, HardSoftScore

@constraint_provider
def define_constraints(constraint_factory):
    return [
        # 硬约束：车辆装载量不能超过额定容量
        constraint_factory.for_each(VehicleRoute)
            .filter(lambda route: route.current_load > route.vehicle.capacity)
            .penalize("超载违规", HardSoftScore.ONE_HARD),
        
        # 硬约束：装载量达上限后必须前往倾倒区，禁止继续收集
        constraint_factory.for_each(VehicleRoute)
            .join(Location, Joiners.equal(lambda r: r.visited_locations[-1], lambda loc: loc))
            .filter(lambda r, loc: not loc.is_dump and r.current_load >= r.vehicle.capacity)
            .penalize("未及时倾倒", HardSoftScore.ONE_HARD),
        
        # 硬约束：车辆必须从归属车场出发，最终返回原车场且无垃圾
        constraint_factory.for_each(VehicleRoute)
            .filter(lambda r: r.visited_locations[-1] != r.start_depot or r.current_load != 0)
            .penalize("未返回车场或残留垃圾", HardSoftScore.ONE_HARD),
        
        # 软约束：优先选择最近的倾倒区，减少行驶距离
        constraint_factory.for_each(VehicleRoute)
            .join(Location, Joiners.equal(lambda r: next(loc for loc in r.visited_locations if loc.is_dump), lambda loc: loc))
            .reward("选择最近倾倒区", HardSoftScore.ONE_SOFT,
                    lambda r, loc: -networkx.shortest_path_length(network, r.last_non_dump_loc, loc))
    ]

三、路径逻辑处理 #

在求解过程中，需自定义路径的装载量计算逻辑：

• 遍历路径中的节点序列，累加途经路段的垃圾量到current_load
• 当current_load达到车辆容量时，自动插入最近的倾倒区节点，并将current_load重置为0
• 确保最终节点为归属车场，且current_load为0

四、求解与验证 #

• 初始化OptaPy求解器，设置求解时长、启发式算法（如禁忌搜索）
• 运行求解后，提取每条车辆的路径序列
• 用NetworkX可视化求解结果，验证路径是否符合示例场景（如R出发→收集节点→F倾倒→再收集→AA倾倒→返回R），同时检查容量约束、倾倒规则是否满足

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