简介一套面向多目标多配送站车辆路径规划问题的C工程基于人工蜂群算法实现兼顾全局搜索与帕累托优化适合算法研究人员和物流调度开发者参考学习。压缩包内共101个文件以18个C源文件和5个头文件为主体辅以完整的Visual Studio解决方案文件及编译生成的exe、pdb、obj等包体约211.76MB。该资源已有346人学习工程涵盖主程序入口、适应度计算、非支配排序、拥挤距离、雇佣蜂与观察蜂更新等核心模块并包含MDVRP等关键类定义代码结构清晰。通过阅读源码读者可深入理解多目标路径规划问题的编码表示、目标冲突处理机制以及C面向对象的算法实现方式也可在此基础上扩展其他智能优化算法进行对比实验。工程同时提供可执行程序便于直接运行验证。1. 人工蜂群算法与多目标多配送站车辆路径规划问题的真实交汇场景如果只优化一个配送站的路线调度系统用最省总里程的局部搜索就能交出结果但把配送站从1个变到多之后车辆必须归属到某个仓订单也要在“去哪个仓”和“顺序怎么排”两层上同时做决定单目标解的偏差立刻暴露出来。比较常见的结果是某一座配送站跑满运力另一座配送站闲半程系统给出的解释却是“总里程确实最小”。人工蜂群算法的作用空间正好在连续优化之外它用三种角色的蜂群逐个更新整张“配送站-车辆-客户”分配结构用多目标评价机制保留一组互相不可替代的解而不是挤出单个答案。下面的内容会把目标建模、离散编码和 Python 实现串成可落地的流程。2. 多目标多配送站车辆路径规划问题建模与人工蜂群算法搜索空间设计2.1 多目标MDVRP的目标函数与约束条件先明确输入有 m 个配送站组成集合 Dn 个客户组成集合 CK 辆车组成集合 V。每个客户带坐标和需求量每辆车有载重上限且归属于某个配送站。车辆路径规划问题在这里要产出的变量包含三层哪些客户被放到同一辆车、每辆车从哪个配送站出发、同一辆车的客户按什么顺序访问。这三层变量互相制约所以目标函数不能直接在连续空间上求梯度只能靠组合搜索。常用目标取三个。f1 是总行驶距离等于所有路线闭环距离的累加f2 是投入车辆数量和出车成本线性相关f3 是配送站负载均衡程度通常用各配送站承担总里程的标准差表示。f1 和 f2 都直接可算f3 要小心如果把方差原始值塞进目标向量量级通常会比 f1 小很多非支配排序时几乎不起作用。常见做法是把 f3 除以总里程或仓库数量做归一化让三个目标大致落在同一个尺度上。约束条件建议按下表在代码里真实落地约束名判断方式处理方式车辆载重每条路线需求之和 ≤ 车辆容量超载直接设罚值服务唯一性每个客户只能出现在一条路线中编码本身保证配送站归属车辆路线起终点等于其所属配送站解码时补起终点时间窗可选客户允许提前或延后到达作为额外惩罚项另外要补充一个边界超载直接返回罚值会让初始种群的可行解偏少尤其在容量紧的实例上。更稳妥的方案是允许一定比例超载只对超过容量 1.5 倍的部分额外加大惩罚给搜索留出过渡区域。多目标优化在这里的意义就是把超载、距离、均衡这些指标放在同一维度上比较而不是只盯着一个可行域边界去求单点最优。2.2 人工蜂群算法三阶段与多目标邻域动作的映射关系人工蜂群算法原本为连续优化设计公式里包含位置加减法和适应度值直接搬到组合问题上完全跑不通。常见做法是把三种蜂阶段对应成三类邻域操作雇佣蜂对当前解做一步局部搜索例如交换同一条路线里的客户访问顺序观察蜂在前沿排序靠前的解附近做更多轮搜索侦察蜂在有解连续多代未改进时将其丢弃并重启。对应回多目标多配送站场景这三类操作就变成具体的车辆路径规划问题算子了。交换是微调同车内的路线顺序只改变访问次序不改变车辆归属转移是把某个客户从一辆车移动到另一辆车影响的是车辆载重和路径长度换仓是改变某辆车所归属的配送站影响的是路线起终点和仓库负载均衡。三种操作分别对应编码的三个层面缺失任何一层都会让搜索空间变窄。多配送站场景下还有一个非常隐蔽的问题对称解。两辆车编号互换但实际路线完全一样在目标向量的计算中会得到相同结果但会被当成两个独立种群个体参与选择白白浪费评估次数。因此邻域生成和父代比较时要约定车辆编号从小到大排列过滤掉等价交换带来的重复评估。2.3 双层编码和解码从客户分配到路线序列的完整还原把连续蜜蜂位置映射到离散编码比较稳妥的是双层编码方案。第一层是car_assign长度等于客户数存储每个客户被派给的车辆编号第二层是visit_order长度也等于客户数表示某个客户在同一辆车内的访问次序。这种写法从编码定义上保证“一个客户只属于一辆车”不需要在每次变异后额外做配对修复。解码阶段要做的只是把同车的客户按访问序号排序并在路径首尾补上该车所属配送站。car_assign [0, 1, 2, 0, 3, 1, 2, 3] # 8个客户分配到4辆车 visit_order [1, 2, 1, 3, 1, 3, 2, 2] # 同车内按该值排序 def decode_routes(car_assign, visit_order, depot_of_vehicle): routes {vid: [] for vid in set(car_assign)} for i, (vid, order) in enumerate(zip(car_assign, visit_order)): routes[vid].append((i, order)) result {} for vid, items in routes.items(): items_sorted [c for c, _ in sorted(items, keylambda x: x[1])] result[vid] (depot_of_vehicle[vid], items_sorted) return result逻辑说明routes先按车辆编号聚合客户sorted对同一辆车内的visit_order升序重排得到真正访问顺序depot_of_vehicle字典把车辆映射到所属配送站返回结果直接可用于后续距离计算。参数说明car_assign和visit_order必须等长车辆编号需要从 0 开始连续排列否则set(car_assign)的复用顺序会不稳定影响邻域操作中的索引映射。这个解码方案不检查载重属于纯空间-顺序定义正式评估时要单独叠加容量校验。注意visit_order只在同车内排序不表示跨车绝对顺序。不同车辆之间的访问先后没有可比性解码时不要混用。3. Python实现人工蜂群算法求解多目标多配送站车辆路径规划问题的核心流程3.1 Solution类与目标评估函数的实现先写一个ABCSolution类处理完整评估读入双层编码解码为路线再计算载重、总里程、车辆数和配送站负载标准差。这段代码是整条链路的计算基础后续所有蜂群操作都复用它的evaluate方法。import numpy as np class ABCSolution: def __init__(self, car_assign, visit_order, dist, demands, vehicle_capacity, depot_of_vehicle): self.car_assign np.array(car_assign) self.visit_order np.array(visit_order) self.dist dist self.demands demands self.vehicle_capacity vehicle_capacity self.depot_of_vehicle depot_of_vehicle self.objectives None def evaluate(self): routes {vid: [] for vid in np.unique(self.car_assign)} for client, (vid, order) in enumerate(zip(self.car_assign, self.visit_order)): routes[vid].append((client, order)) total_distance 0.0 depot_km {} n_used len(routes) for vid, items in routes.items(): items.sort(keylambda x: x[1]) path [self.depot_of_vehicle[vid]] [c for c, _ in items] load sum(self.demands[c] for c, _ in items) if load self.vehicle_capacity: self.objectives [np.inf, np.inf, np.inf] return seq_dist 0.0 for prev, curr in zip(path[:-1], path[1:]): seq_dist self.dist[prev][curr] # 车辆访问完最后一个客户后必须返回所属配送站 seq_dist self.dist[path[-1]][self.depot_of_vehicle[vid]] total_distance seq_dist depot_km[self.depot_of_vehicle[vid]] \ depot_km.get(self.depot_of_vehicle[vid], 0.0) seq_dist if not depot_km: self.objectives [np.inf, np.inf, np.inf] return mean_km np.mean(list(depot_km.values())) variance np.sqrt(np.mean([(v - mean_km) ** 2 for v in depot_km.values()])) self.objectives [total_distance, n_used, variance]逻辑说明routes按车辆聚合客户后items.sort(keylambda x: x[1])取出同车访问顺序path把所属配送站放在列表首尾两端然后用相邻点距离累加得到路线里程。载重检查用的是罚函数超载返回三个正无穷让非支配排序自然淘汰这批解。参数说明vehicle_capacity是每辆车统一容量如果实际场景中车辆载重不同需要把容量数组传进来在不同车辆上分别比较depot_of_vehicle的长度必须等于车辆总数车辆编号在这里与car_assign保持一致。3.2 非支配排序与拥挤度距离观察蜂选择的排序基础多目标优化首先要区分解的优劣这里直接复用 NSGA-II 多目标优化的排序思路先按支配关系分层再在同一层内用拥挤度距离保持分布。人工蜂群算法里的观察蜂就是根据这个排序结果去挑选父代附近继续搜索。def dominates(a, b): return all(a[i] b[i] for i in range(len(a))) and any(a[i] b[i] for i in range(len(a))) def fast_non_dominated_sort(values): n len(values) domination_count [0] * n dominated_solutions [[] for _ in range(n)] fronts [[]] for p in range(n): for q in range(n): if p q: continue if dominates(values[p], values[q]): dominated_solutions[p].append(q) elif dominates(values[q], values[p]): domination_count[p] 1 if domination_count[p] 0: fronts[0].append(p) idx 0 while fronts[idx]: next_front [] for p in fronts[idx]: for q in dominated_solutions[p]: domination_count[q] - 1 if domination_count[q] 0: next_front.append(q) idx 1 fronts.append(next_front) return fronts[:-1]fast_non_dominated_sort返回的是分层列表每层是解的下标数组。第一次循环找出所有不被任何解支配的个体放入第 0 层然后逐层剥离domination_count归零表示该解对应的支配者已经全部被移走自然进入下一层。这里时间复杂度为 O(N²)MDVRP 求解器种群规模在 100 以内时不是瓶颈不需要替换成复杂度更高的实现。3.3 雇佣蜂和观察蜂的邻域操作交换、插入和换仓这轮代码给出generate_neighbor函数覆盖车辆路径规划问题里最常用的三种变异操作evaluate在变异完成后自动执行。def generate_neighbor(sol): import copy new copy.deepcopy(sol) action np.random.choice([swap, move, switch_depot]) if action swap: vid np.random.choice(np.unique(new.car_assign)) indices [i for i, v in enumerate(new.car_assign) if v vid] if len(indices) 2: i, j np.random.choice(indices, 2, replaceFalse) new.visit_order[i], new.visit_order[j] new.visit_order[j], new.visit_order[i] elif action move: i, j np.random.choice(len(new.car_assign), 2, replaceFalse) new.car_assign[i] new.car_assign[j] else: client np.random.choice(len(new.car_assign)) current_depot new.depot_of_vehicle[new.car_assign[client]] candidates [v for v in range(len(new.depot_of_vehicle)) if new.depot_of_vehicle[v] ! current_depot] if candidates: new.car_assign[client] np.random.choice(candidates) new.evaluate() return new逻辑说明swap 操作保持车辆归属不变只调换车内次序适合微调move 操作把某个客户点直接移动到另一辆车载重约束由evaluate里的罚值承担switch_depot 操作换的是客户所属车辆对应的配送站目的是让跨仓远距离订单重新配对。三种动作分别对应路线次序、车辆归属、配送站归属三个搜索维度缺一个都会缩小可搜索空间。参数说明switch_depot的候选集只要求所属配送站不同没有排除当前车辆本身某些情况下会生成等价交换如果需要更强变异可以在候选集里加入随机空车扩大换仓影响。3.4 ABC主循环与参数入口三个阶段整合到一个迭代里所有参数集中在函数入口方便做对比实验。def abc_mdvrp(pop_size80, limit25, max_iter200): population [random_solution() for _ in range(pop_size)] stall_counter [0] * pop_size archive [] for _ in range(max_iter): # 雇佣蜂阶段每个个体尝试一次邻域替换 for k in range(pop_size): cand generate_neighbor(population[k]) if dominates(cand.objectives, population[k].objectives): population[k] cand stall_counter[k] 0 else: stall_counter[k] 1 # 观察蜂阶段从第一、第二前沿抽样做二次开发 fronts fast_non_dominated_sort([p.objectives for p in population]) pool [idx for f in fronts[:2] for idx in f] for k in range(pop_size // 2): parent np.random.choice(pool) cand generate_neighbor(population[parent]) if dominates(cand.objectives, population[parent].objectives): population[parent] cand # 侦察蜂阶段只重启停滞最久的个体 worst np.argmax(stall_counter) if stall_counter[worst] limit: population[worst] random_solution() stall_counter[worst] 0 archive.extend(population) archive [s for s in archive if not any(dominates(other.objectives, s.objectives) for other in archive if other is not s)] return archive逻辑说明雇佣蜂逐个做单步变异只有能支配父代才接收观察蜂从非支配前沿集合里抽样做第二轮搜索目标是让高潜力个体继续被开发。侦察蜂每次只重启一个停滞最久的个体避免一次性破坏大量解。参数说明pop_size80适合几十个客户的中小型实例limit25表示一个解最多允许 25 代无改进太小会让局部搜索永远不够充分太大则停滞解占用种群位置时间过长max_iter200对中等规模问题已经够用如果前沿长期不变化先调观察蜂选择压力而不是盲目加迭代数。4. 人工蜂群算法参数调优与多配送站场景的复现实验排错4.1 在随机小规模实例上跑通人工蜂群算法的最小复现流程在本地验证前面代码是否正确小规模随机实例是最快的路径。下面这段主流程生成 3 个配送站、6 辆车、24 个客户的实例并跑一次 ABC 循环。if __name__ __main__: np.random.seed(0) n_depots, n_vehicles, n_customers 3, 6, 24 coords np.random.rand(n_depots n_customers, 2) * 100 demands np.random.randint(1, 8, n_customers) capacity 20 dist [[np.linalg.norm(coords[i] - coords[j]) for j in range(n_depots n_customers)] for i in range(n_depots n_customers)] depot_of_vehicle np.random.randint(0, n_depots, n_vehicles) archive abc_mdvrp(pop_size60, limit20, max_iter100) print(非支配解数量:, len(archive)) print(各目标最小值:, [min(s.objectives[g] for s in archive) for g in range(3)])逻辑说明数据集随机生成客户需求在 1 到 7 之间容量 20每辆车大约能容纳 4 到 5 个客户。这个密度能保证 ABC 在运行初期有一批可行解也不会因为超载比例过高导致整个初始种群全被罚掉。参数说明输出两行分别表示档案中的非支配解数量和三个目标的各自最小值。如果非支配解数量持续快速增长说明变异动作过于分散要提高观察蜂选择压力如果数量一直很小甚至收敛到单点说明局部开发不足需要调大limit。4.2 三个关键参数limit、种群规模、观察蜂选择压力人工蜂群算法在车辆路径规划问题上的表现多数情况下不是被迭代次数限制而是参数配比不合适。下表列出影响最直接的几个参数数值范围适合配送站数量在 3 到 8 之间的常见 MDVRP 实例。参数推荐范围表现与倾向limit10-40过小导致侦察蜂频繁重启解结构被打断过大则停滞解占用时间过长pop_size40-100客户在 100 以内时 60 够用超过 200 个客户建议提到 100观察蜂比例0.2-0.5比例高则对优质解深挖容易早熟低则搜索分散收敛慢二元锦标赛大小2-5越大选择压力越强需要配合更大的种群防止陷入局部前沿改这些参数只涉及abc_mdvrp函数入口的传参不需要动内部循环。多目标优化场景里观察蜂比例比单目标更敏感因为前沿上的分布性依赖多样性选择如果观察蜂总是抽到同一小簇解种群会快速塌缩再增加迭代次数也救不回来。4.3 多配送站场景独有的排错点与修复方式第一个坑是漏算回程距离。车辆从配送站出发访问完客户后必须回到出发的配送站路线才闭合。许多实现会为了计算方便省略最后一段总里程偏小配送站负载均衡目标也会失真。修复方式在ABCSolution.evaluate里已经体现关键是别在其他临时副本里把这段逻辑删掉。第二个坑是车辆编号与配送站归属的隐式关联。多配送站环境下车辆数组必须用depot_of_vehicle显式记录归属而不是通过“前两个车辆属于 1 号仓后面属于 2 号仓”这类位置规则推断。隐式规则在种群重启和 switch_depot 操作后容易悄悄引入错误归属而且很难被测试用例发现。第三个坑是目标量纲差异导致排序失效。配送站负载方差数值通常比总里程小一个数量级不归一化会让它在前沿排序里被压制算法会变成实际上的双目标优化。在evaluate末尾用variance / (total_distance / len(depot_km))重新表示这个目标能让三个目标在量级上更接近。下面这段可以直接替换ABCSolution中的目标赋值# 将负载均衡目标折算到总里程量级避免量纲压制 normalized_variance variance / (total_distance / max(1, len(depot_km))) self.objectives [total_distance, n_used, normalized_variance]5. 多目标优化与决策阶段的帕累托筛选技巧和验证边界5.1 从帕累托前沿选择最终上线方案ABC 输出的档案里通常有几十个非支配解决策模块要从里面挑一个实际下发。常见做法是计算每个解到理想点的欧氏距离把三个目标各自最小值组成理想点对解做 0-1 标准化再取距离最近者。如果业务对总里程有明确倾向可以在计算距离前给对应目标乘一个权重权重只影响决策不需要重新运行 ABC。def pick_by_ideal_point(archive, weightsNone): vec np.array([s.objectives for s in archive]) ideal vec.min(axis0) vmax, vmin vec.max(axis0), vec.min(axis0) normed (vec - ideal) / (vmax - vmin 1e-9) if weights is not None: normed * weights dist np.linalg.norm(normed, axis1) return archive[int(np.argmin(dist))]5.2 验证人工蜂群算法在小型MDVRP实例上的正确性验证框架正确性的可靠方法是在小实例上和穷举对照。用 2 个配送站、4 辆车、6 个客户生成所有合法双层编码组合并计算目标遍历得到真正的非支配前沿再跑 30 轮 ABC统计算法得到的解能覆盖或支配穷举前沿的比例。比例达到 80% 以上可以认为编码和解码没有结构性错误。写对比脚本时注意穷举必须包含配送站归属变化否则搜索空间和 ABC 不一致固定随机种子并取多次均值比单次运行更有参考意义。5.3 面向大规模配送站的收敛技巧客户超过 200 个时雇佣蜂阶段会非常耗时因为每个解都要重新遍历距离矩阵。一个有效做法是在初始化种群前先按配送站坐标对客户做聚类预分组把同仓客户初始分配给同一批车辆邻域变异再从局部调整开始。ABC 的全局档案已经积累了历史非支配解不需要额外增大种群来保存记忆。如果发现第一前沿的目标值在后期不再更新但档案数量还在增加说明正在产出大量等价重复解优先检查是否缺少对称解过滤而不是怀疑算法陷入局部最优。本文还有配套的精品资源点击获取