简介一份基于遗传算法求解车辆路径问题VRP的MATLAB实现面向物流调度、运筹优化方向的初学者与算法研究者。资源以单个m文件封装核心算法涵盖编码方案、种群初始化、适应度计算、选择、交叉、突变及结果解码等关键环节逻辑紧凑便于直接运行和调试。通过迭代优化逐步改善车辆行驶路径可用于理解遗传算法解决组合优化问题的完整流程并直观观察最优解的收敛过程。压缩包内共1个m文件大小仅2KB轻量易用。已有258人学习下载适合作为入门实践模板。实际应用中可在此基础上扩展容量约束、时间窗口等条件或结合局部搜索、模拟退火等策略进一步提升解的质量适合科研与工程场景下的二次开发。1. VRP 与遗传算法从“VRP.rar”看车辆路径调度问题这个压缩包名字直白但背后是组合优化领域最常被复现的一类项目用遗传算法求解车辆路径问题Vehicle Routing ProblemVRP。场景说开就是物流公司有若干台车、一批客户点怎么安排每台车的访问顺序让总行驶距离最短、用车数最少同时满足载重和时间要求。标题里的“路径”“调度问题”“车辆调度”指的都是同一件事遗传算法则是用来在几十上百个节点构成的巨大搜索空间里找近似最优解的核心手段。这类代码通常被打包成 rar 分享给初学者或面试者所以在本地跑通它之前需要先把编码方式和算法参数吃透。2. 用遗传算法求解VRP的理论和编码设计2.1 车辆路径问题的定义和约束建模先用标准说法把问题固定下来有一个配送中心depot、若干个客户点每辆车有最大载重部分场景还限制最大行驶距离或时间窗要求设计一组从配送中心出发、访问部分客户后返回配送中心的路径集合使得每个客户恰好被访问一次总成本最小。车从哪里走、按什么顺序走、车之间怎么分配客户这三个问题共同构成车辆调度问题的解空间。当客户数只有 8 个时穷举所有排列已经是 40320 种当客户数到 50 个时排列数量超过 10 的 64 次方精确算法只能处理几十个点的规模。所以实际工程里常用智能优化算法而遗传算法是其中最稳定、最容易扩展到物流配送路径场景的一种。它不直接操作“路径”而是操作一种叫染色体的编码因此第一步就是把路径集合翻译成可以交叉、变异的数据结构。在遗传算法里一个染色体就是一组排列比如[1, 3, 2, 5, 4, 6, 7, 8]表示配送顺序。这个排列本身并没有直接说明哪几台车、每台车访问哪几个点需要通过解码规则转换为真正的车辆路径。常见做法是采用容量约束分割按顺序把客户分配给当前车辆如果剩余容量不够放下一个客户就开启新车辆。2.2.1 解码规则解码伪代码如下输入客户排列 perm需求量数组 demand车辆容量 Q 输出路径集合 routes 当前路径 route [] 剩余容量 cap Q for 客户 c in perm: if demand[c] cap: 将 c 加入 route cap cap - demand[c] else: 保存 route 作为一条路径 开始新 route [c] cap Q - demand[c] 保存最后的 route这个解码逻辑解释了为什么染色体中不需要显式插入“车辆分隔符”车辆数完全由容量约束动态决定。它的优点是染色体长度始终等于客户数交叉变异后仍然满足“每个客户只出现一次”缺点是当需求量划分不当时可能产生较多空驶车辆因此适应度函数里需要加入车辆数惩罚。2.2 染色体编码与车辆分割编码方式对遗传算法的搜索效率影响很大。使用自然数排列适用于大部分 VRP 变体包括带容量约束的 CVRP 和带时间窗的 VRPTW。与之相对的是二进制编码但在路径问题上会导致大量非法解修复成本很高。自然数排列的另一个好处是能够直接复用旅行商问题TSP的大量交叉算子。比如部分匹配交叉PMX、顺序交叉OX和循环交叉CX都能保证子代不重复不缺失。后续代码里我会使用顺序交叉因为它在路径类问题中表现最稳定。2.2.1 车辆数量如何计算解码后routes的长度就是使用的车辆数。如果业务上有固定车辆数限制可以在解码时记录当前车辆数一旦超过上限就提前终止并把该个体标记为不可行。需要说明的是固定车辆数的 VRP 在遗传算法里不如动态车辆数好调参因为它会大大压缩可行解空间初始种群中大量个体可能直接非法导致算法一开始就无法收敛。常见做法是允许车辆数浮动但通过惩罚让算法自动偏向车辆数少的解。2.3 适应度函数设计适应度函数的作用是告诉遗传算法“哪些路径好”。最基本的物理量是总行驶距离再加上车辆固定成本因为少一辆车通常意味着更低的燃料、司机和折旧成本。目标函数可以写为总成本 所有车辆路径距离之和 vehicle_weight * 车辆数具体映射到代码时我一般取车辆权重的参考值为“最大客户间距离的 2 倍”。为什么不是固定值如果权重设置得比距离量级小很多算法会只关注缩短路径而忽略车辆数如果设置得过大算法会强行减少车辆数导致某些车绕远路。表 2-1 给出了一个参考。目标项作用权重推荐总行驶距离衡量路线长短1车辆数减少用车数量最大边距离的 12 倍容量超载约束违反惩罚正常适应度值的 1000 倍以上由于遗传算法习惯“适应度越大越好”而路径问题是求最小成本实际代码里可以直接返回总成本并让算法按最小值排序不需要转换成倒数或负值。这样更方便调试也能直接看到车辆数和距离的变化。3. 实现遗传算法求解VRP的Python基础代码3.1 构造距离矩阵和初始种群下面这份 Python 代码是我习惯的最小可运行版本。它解决 8 个客户点、单车容量 5 的 CVRP读者可以直接复制运行。import random import numpy as np # 索引0是配送中心其余是客户点 coords np.array([ [0, 0], [20, 30], [35, 15], [25, 45], [40, 60], [70, 20], [80, 50], [55, 65], [60, 80] ]) demand [0, 1, 1, 1, 1, 1, 1, 1, 1] capacity 5 # 使用字典存储距离便于随机访问 distance {} for i in range(len(coords)): for j in range(len(coords)): distance[(i, j)] np.linalg.norm(coords[i] - coords[j]) def random_individual(): perm list(range(1, len(coords))) random.shuffle(perm) return perm代码逻辑很简单random_individual生成一个从 1 到 8 的随机排列代表一种客户访问顺序。距离字典比二维数组更灵活后面计算路径距离时不需要关注矩阵索引方向。初始种群只需要不断调用random_individual即可不需要依赖距离信息所以初始化速度非常快。对于更大规模问题可以在这里加入最近邻启发式生成的部分初始解以加快收敛。3.2 选择、有序交叉和交换变异遗传算法的核心算子都在下面这段代码里。def decode(perm): routes [] route [] cap capacity for c in perm: if demand[c] cap: route.append(c) cap - demand[c] else: if route: routes.append(route) route [c] cap capacity - demand[c] if route: routes.append(route) return routes def route_distance(route): dist distance[(0, route[0])] for i in range(len(route) - 1): dist distance[(route[i], route[i 1])] dist distance[(route[-1], 0)] return dist def fitness(perm): routes decode(perm) total sum(route_distance(r) for r in routes) return total 100 * len(routes) def tournament_selection(pop, k3): selected random.sample(pop, k) return min(selected, keylambda x: x[1]) def order_crossover(p1, p2): n len(p1) a, b sorted(random.sample(range(n), 2)) child [None] * n child[a:b] p1[a:b] pos b for gene in p2: if gene not in child: while pos in range(a, b): pos 1 child[pos] gene pos 1 return child def swap_mutate(perm, rate0.1): if random.random() rate: i, j random.sample(range(len(perm)), 2) perm[i], perm[j] perm[j], perm[i] return permdecode与前面伪代码一致route_distance负责计算从仓库出发、访问完整条路径再返回仓库的距离。fitness中的100 * len(routes)就是车辆权重这里把车辆权重设为固定值 100适用于当前距离量级在 60 到 160 左右的样例数据。tournament_selection是锦标赛选择随机抽 3 个个体取其中适应度最小的一个作为父代。这种选择方式不依赖适应度尺度实现简单而且能在算法早期防止某个超强个体快速垄断种群。order_crossover是顺序交叉先随机选一段连续基因从父代 P1 复制到子代再从 P2 中按照原有顺序填充剩余空位。这样产生的子代永远是一个合法的客户排列不会出现重复客户。swap_mutate是交换变异随机交换染色体上的两个位置。变异率通常保持在 0.05 到 0.2 之间因为顺序交叉本身已经有相当强的随机性。3.3 迭代收敛与结果输出下面把完整主循环串起来。def genetic_algorithm(n_gen200, pop_size100, cx_rate0.8, mut_rate0.1): pop [] for _ in range(pop_size): ind random_individual() pop.append([ind, fitness(ind)]) best_history [] for gen in range(n_gen): pop.sort(keylambda x: x[1]) best_history.append(pop[0][1]) new_pop [ [pop[0][0].copy(), pop[0][1]], [pop[1][0].copy(), pop[1][1]] ] while len(new_pop) pop_size: p1 tournament_selection(pop, 3)[0] p2 tournament_selection(pop, 3)[0] if random.random() cx_rate: child order_crossover(p1, p2) else: child p1[:] if random.random() 0.5 else p2[:] child swap_mutate(child, mut_rate) new_pop.append([child, fitness(child)]) pop new_pop pop.sort(keylambda x: x[1]) return pop[0], best_history best, hist genetic_algorithm() print(最优排列:, best[0]) print(车辆路径:, decode(best[0])) print(总成本:, best[1])运行后能看到输出类似最优排列: [5, 3, 1, 7, 2, 6, 4, 8] 车辆路径: [[5, 3, 1], [7, 2, 6], [4, 8]] 总成本: 415.9主循环的逻辑是每一代先按成本排序把最优的两个个体保留到下一代这就是精英保留其余个体通过锦标赛选择父代以 0.8 的概率做顺序交叉以 0.1 的概率做交换变异最终组成新的种群。运行 200 代后得到的best[0]就是当前找到的最优客户排列。这段代码已经是一个完整的遗传算法求解 VRP 的骨架。在实际使用时需要注意fitness函数和主循环解耦这样才能方便后面对车辆权重、容量约束和时间窗做扩展。4. 车辆调度中容量约束和时间窗的扩展实现4.1 从VRP到CVRP再到VRPTW基础 VRP 不限制车辆容量而实际车辆调度几乎必然涉及载重、体积或行驶时间限制。带容量约束的 CVRP 上面已经实现但如果要面向真实物流还需要考虑时间窗每个客户点有最早服务时间early[i]和最晚服务时间late[i]车辆到达太早要等待到达太晚则不允许服务。处理时间窗的常见做法是在解码时增加一层时间判断。下面这段代码展示如何单独校验一条路径是否满足时间窗service_time {i: 10 for i in range(1, len(coords))} time_window {i: (0, 300) for i in range(len(coords))} def is_time_feasible(route): current_time 0 for idx, node in enumerate(route): prev 0 if idx 0 else route[idx - 1] current_time distance[(prev, node)] if current_time time_window[node][1]: return False current_time max(current_time, time_window[node][0]) service_time[node] return current_time time_window[0][1]is_time_feasible的逻辑是模拟车辆一路开过去的累计时间在到达客户时判断是否晚于最晚时间窗如果没有晚到再把当前时间更新为最早服务时间和到达时间中的较大值加上服务时间。如果仓库也有时间窗最后还要判断车辆回到仓库是否超时。把时间窗判断放进遗传算法时我会把它和容量判断合并到同一个解码函数里。每次准备把一个客户加入当前路径时先临时假设加入并重新计算到达时间如果不满足时间窗就尝试开启新车辆如果新车辆也无法满足则把该个体标记为不可行。这样能够让遗传算法在解码阶段直接过滤掉大量非法解而不是依靠适应度惩罚慢慢淘汰。4.2 惩罚函数让约束变量成为目标的一部分很多初学者喜欢把所有约束都硬编码进合法解但一个强约束到每个个体都必须合法的算法往往很难生成足够的多样性。工程上更常见的做法是允许算法暂时产生少量不可行解但通过惩罚函数让它们的适应度远远差于可行解。表 4-1 给出了常用惩罚项的配置。约束类型惩罚表达式说明容量超载penalty 1e6 * (超载量 1)超载量是超出容量的货物单位时间窗迟到penalty 1000 * (迟到时长 1)迟到时长是到达时间与最晚时间的差超过车辆数上限penalty 1000 * 超出车辆数车辆数是业务固定限制惩罚系数必须和正常适应度值区分开。比如样例中路径距离总量在 300 到 500 之间容量惩罚设置成1e6就能保证任何一个可行解都优于所有不可行解。这里建议把惩罚设计为“超载量的一次函数”而不是固定常量因为固定常量会让算法无法区分超载 1 个单位还是 5 个单位的个体搜索效率会降低。在迭代后期还可以把惩罚系数逐步调大让种群慢慢收敛到可行域。4.3 多目标距离最短与车辆数最少实际车辆调度中距离最短和车辆数最少往往互相矛盾用 3 辆车可以跑出 400 公里用 4 辆车可能只要 350 公里怎么选取决于业务成本模型。一个快速方法是调整车辆权重参数观察不同权重下的最优结果。def fitness_with_weight(perm, vehicle_weight100): routes decode(perm) total sum(route_distance(r) for r in routes) return total vehicle_weight * len(routes) for weight in [10, 50, 100, 200, 500]: best_cost None for _ in range(10): ind random_individual() cost fitness_with_weight(ind, weight) if best_cost is None or cost best_cost: best_cost cost routes decode(ind) total_dist sum(route_distance(r) for r in routes) print(weight, total_dist, len(routes))实际运行时需要把fitness_with_weight替换到遗传算法主循环中这里只用来展示权重改变对路径结构的影响。车辆权重越高算法越倾向于用更少的车但总行驶距离可能增加。调参时可以画出车辆数-距离曲线找到拐点作为业务决策参考。5. 遗传算法参数调优与常见坑点5.1 种群规模、迭代次数、交叉率和变异率的推荐范围遗传算法能不能求解出一个好路径参数往往比算子更重要。表 5-1 是我的常用参考值适用于 10 到 100 个客户点的车辆路径。问题规模更大时需要同步增大种群规模和迭代次数但交叉率和变异率通常保持在下面范围内。参数可直接参考的范围推荐起始值参数影响种群规模50300100过小容易早熟过大会拖慢每代运行时间迭代次数1001000200根据收敛曲线判断是否继续交叉率0.60.90.8过低会削弱搜索能力过高会破坏高价个体变异率0.050.20.1过高会退化成随机搜索精英保留152防止历史上最优解丢失对于客户点只有 8 个的样例种群规模 50、迭代次数 100 已经足够。但当客户点增加到 50 个以上时我一般把种群规模调到 150迭代次数调到 300并每 50 代打印一次最优成本。如果发现连续 50 代成本没有任何变化就说明算法提前收敛需要提高变异率或引入局部搜索。5.2 三种容易踩的坑5.2.1 车辆权重设置不合理一个常见现象是遗传算法已经跑完 500 代但路径图上车辆数量明明还可以减少绕路却很严重。原因通常是车辆权重设得过大算法会在前几代强行把客户塞进少量车辆导致路径交叉。正确的做法是先计算随机个体平均路径长度把车辆权重设为该长度的 0.5 到 2 倍再逐步调整。5.2.2 容量解码顺序影响结果需求不同的情况下顺序扫描排列有时候会产生不必要的空车。比如一辆车容量只有 4连续遇到两个需求为 3 的客户就会开两辆车。更合理的做法是在解码前先把客户按需求降序排列或者对解码完成的路径做一次 2-opt 局部优化。对于纯容量约束按顺序解码仍然是最常见的基础方式性能瓶颈可以留到后处理阶段解决。5.2.3 时间窗约束导致初期可行解太少引入时间窗后随机生成的排列有相当大概率违反时间窗。如果惩罚函数权重不够大算法会把大量资源花在探索不可行区域如果惩罚权重太大种群会快速收敛到个别可行解错过更优路径。我的做法是初始种群中加入 10% 的贪心解贪心策略是每次选择距离当前点最近且满足容量和时间窗的客户剩余 90% 仍然是随机排列保证多样性。5.3 应对早熟收敛的两个手段当收敛曲线在前 20 代就完全变平说明种群失去了多样性。最基本的应对方法是增大变异率但更有效的是“重启策略”将种群中除了精英个体以外的部分全部重新随机初始化。下面是带重启的简化片段for gen in range(n_gen): # 假设已经完成一次遗传迭代 if gen 20 and gen % 30 0: keep pop[:2] new_individuals [[random_individual(), 0] for _ in range(pop_size - 2)] for item in new_individuals: item[1] fitness(item[0]) pop keep new_individuals这段代码每 30 代清空一次种群只保留最优的前两个个体。重启后适应度值会暂时升高但后续几代会再次下降整体上能跳出局部最优。更精细的做法是对精英个体施加多次变异生成大量邻域个体而不是完全随机初始化这样可以在不破坏优秀基因的前提下增加新信息。6. 用收敛曲线和路径可视化验证遗传算法结果6.1 绘制收敛曲线算法写完后第一件事不是看最终路径而是看收敛曲线。把best_history画出来能够判断当前参数是否需要调整。import matplotlib.pyplot as plt best, history genetic_algorithm(n_gen200, pop_size100) plt.plot(range(len(history)), history) plt.xlabel(generation) plt.ylabel(fitness) plt.title(VRP genetic algorithm convergence) plt.savefig(vrp_convergence.png, dpi200) plt.show()正常情况是前 30 代快速下降后面缓慢变平。如果曲线到最后仍然有明显下降趋势说明迭代次数不够可以继续增加n_gen。如果曲线在 10 代内就平了且总成本远高于随机贪心解说明参数需要调整或算法早熟。6.2 路径可视化与解码验证路径可视化能直观检查车辆路线是否存在严重交叉、是否每辆车都从仓库出发并返回仓库。下面这段代码把车辆路径绘制在同一张图上。def plot_routes(best_perm): routes decode(best_perm) fig, ax plt.subplots(figsize(8, 8)) for route in routes: pts [coords[0]] [coords[i] for i in route] [coords[0]] xs, ys zip(*pts) ax.plot(xs, ys, markero, linewidth1.2) ax.scatter(*coords[0], colorred, s120, labeldepot) for idx, (x, y) in enumerate(coords[1:], start1): ax.text(x 1, y 1, str(idx)) ax.legend() ax.set_title(Vehicle Routes) plt.show() def verify_correctness(best_perm): assert len(set(best_perm)) len(best_perm) 8 routes decode(best_perm) visited [c for route in routes for c in route] assert sorted(visited) list(range(1, 9)) verify_correctness(best[0]) plot_routes(best[0])一眼看过去就能发现车辆数是否正确路径是否过长路线之间是否交叉严重。路径可视化还可以和收敛曲线配合使用在同一个坐标下绘制不同收敛阶段的路线图观察算法是把前期精力花在消除交叉还是减少路径。特别是在有容量约束时解码后的路径经常会出现两条很短的路线相邻这时可以通过调整车辆权重观察是否能把它们合并成一条可行路线。6.3 用数值指标代替肉眼判断路径图和收敛曲线只是验证手段最终判断是否值得继续优化我会用三个数字比较总距离所有车辆路径距离之和车辆数解码后routes的长度最优解稳定性连续 50 代最优成本的标准差小于 1e-6说明已经收敛。对于 8 个客户点的样例可以用它验证算法是否真的找到了最优路径。验证通过后再逐步增加客户点并将数据结构从距离字典替换为欧氏距离矩阵就可以接入真实车辆调度数据。本文还有配套的精品资源点击获取 遗传算法求解车辆路径问题（VRP）的Python实现与调优指南
简介一份基于遗传算法求解车辆路径问题VRP的MATLAB实现面向物流调度、运筹优化方向的初学者与算法研究者。资源以单个m文件封装核心算法涵盖编码方案、种群初始化、适应度计算、选择、交叉、突变及结果解码等关键环节逻辑紧凑便于直接运行和调试。通过迭代优化逐步改善车辆行驶路径可用于理解遗传算法解决组合优化问题的完整流程并直观观察最优解的收敛过程。压缩包内共1个m文件大小仅2KB轻量易用。已有258人学习下载适合作为入门实践模板。实际应用中可在此基础上扩展容量约束、时间窗口等条件或结合局部搜索、模拟退火等策略进一步提升解的质量适合科研与工程场景下的二次开发。1. VRP 与遗传算法从“VRP.rar”看车辆路径调度问题这个压缩包名字直白但背后是组合优化领域最常被复现的一类项目用遗传算法求解车辆路径问题Vehicle Routing ProblemVRP。场景说开就是物流公司有若干台车、一批客户点怎么安排每台车的访问顺序让总行驶距离最短、用车数最少同时满足载重和时间要求。标题里的“路径”“调度问题”“车辆调度”指的都是同一件事遗传算法则是用来在几十上百个节点构成的巨大搜索空间里找近似最优解的核心手段。这类代码通常被打包成 rar 分享给初学者或面试者所以在本地跑通它之前需要先把编码方式和算法参数吃透。2. 用遗传算法求解VRP的理论和编码设计2.1 车辆路径问题的定义和约束建模先用标准说法把问题固定下来有一个配送中心depot、若干个客户点每辆车有最大载重部分场景还限制最大行驶距离或时间窗要求设计一组从配送中心出发、访问部分客户后返回配送中心的路径集合使得每个客户恰好被访问一次总成本最小。车从哪里走、按什么顺序走、车之间怎么分配客户这三个问题共同构成车辆调度问题的解空间。当客户数只有 8 个时穷举所有排列已经是 40320 种当客户数到 50 个时排列数量超过 10 的 64 次方精确算法只能处理几十个点的规模。所以实际工程里常用智能优化算法而遗传算法是其中最稳定、最容易扩展到物流配送路径场景的一种。它不直接操作“路径”而是操作一种叫染色体的编码因此第一步就是把路径集合翻译成可以交叉、变异的数据结构。在遗传算法里一个染色体就是一组排列比如[1, 3, 2, 5, 4, 6, 7, 8]表示配送顺序。这个排列本身并没有直接说明哪几台车、每台车访问哪几个点需要通过解码规则转换为真正的车辆路径。常见做法是采用容量约束分割按顺序把客户分配给当前车辆如果剩余容量不够放下一个客户就开启新车辆。2.2.1 解码规则解码伪代码如下输入客户排列 perm需求量数组 demand车辆容量 Q 输出路径集合 routes 当前路径 route [] 剩余容量 cap Q for 客户 c in perm: if demand[c] cap: 将 c 加入 route cap cap - demand[c] else: 保存 route 作为一条路径 开始新 route [c] cap Q - demand[c] 保存最后的 route这个解码逻辑解释了为什么染色体中不需要显式插入“车辆分隔符”车辆数完全由容量约束动态决定。它的优点是染色体长度始终等于客户数交叉变异后仍然满足“每个客户只出现一次”缺点是当需求量划分不当时可能产生较多空驶车辆因此适应度函数里需要加入车辆数惩罚。2.2 染色体编码与车辆分割编码方式对遗传算法的搜索效率影响很大。使用自然数排列适用于大部分 VRP 变体包括带容量约束的 CVRP 和带时间窗的 VRPTW。与之相对的是二进制编码但在路径问题上会导致大量非法解修复成本很高。自然数排列的另一个好处是能够直接复用旅行商问题TSP的大量交叉算子。比如部分匹配交叉PMX、顺序交叉OX和循环交叉CX都能保证子代不重复不缺失。后续代码里我会使用顺序交叉因为它在路径类问题中表现最稳定。2.2.1 车辆数量如何计算解码后routes的长度就是使用的车辆数。如果业务上有固定车辆数限制可以在解码时记录当前车辆数一旦超过上限就提前终止并把该个体标记为不可行。需要说明的是固定车辆数的 VRP 在遗传算法里不如动态车辆数好调参因为它会大大压缩可行解空间初始种群中大量个体可能直接非法导致算法一开始就无法收敛。常见做法是允许车辆数浮动但通过惩罚让算法自动偏向车辆数少的解。2.3 适应度函数设计适应度函数的作用是告诉遗传算法“哪些路径好”。最基本的物理量是总行驶距离再加上车辆固定成本因为少一辆车通常意味着更低的燃料、司机和折旧成本。目标函数可以写为总成本 所有车辆路径距离之和 vehicle_weight * 车辆数具体映射到代码时我一般取车辆权重的参考值为“最大客户间距离的 2 倍”。为什么不是固定值如果权重设置得比距离量级小很多算法会只关注缩短路径而忽略车辆数如果设置得过大算法会强行减少车辆数导致某些车绕远路。表 2-1 给出了一个参考。目标项作用权重推荐总行驶距离衡量路线长短1车辆数减少用车数量最大边距离的 12 倍容量超载约束违反惩罚正常适应度值的 1000 倍以上由于遗传算法习惯“适应度越大越好”而路径问题是求最小成本实际代码里可以直接返回总成本并让算法按最小值排序不需要转换成倒数或负值。这样更方便调试也能直接看到车辆数和距离的变化。3. 实现遗传算法求解VRP的Python基础代码3.1 构造距离矩阵和初始种群下面这份 Python 代码是我习惯的最小可运行版本。它解决 8 个客户点、单车容量 5 的 CVRP读者可以直接复制运行。import random import numpy as np # 索引0是配送中心其余是客户点 coords np.array([ [0, 0], [20, 30], [35, 15], [25, 45], [40, 60], [70, 20], [80, 50], [55, 65], [60, 80] ]) demand [0, 1, 1, 1, 1, 1, 1, 1, 1] capacity 5 # 使用字典存储距离便于随机访问 distance {} for i in range(len(coords)): for j in range(len(coords)): distance[(i, j)] np.linalg.norm(coords[i] - coords[j]) def random_individual(): perm list(range(1, len(coords))) random.shuffle(perm) return perm代码逻辑很简单random_individual生成一个从 1 到 8 的随机排列代表一种客户访问顺序。距离字典比二维数组更灵活后面计算路径距离时不需要关注矩阵索引方向。初始种群只需要不断调用random_individual即可不需要依赖距离信息所以初始化速度非常快。对于更大规模问题可以在这里加入最近邻启发式生成的部分初始解以加快收敛。3.2 选择、有序交叉和交换变异遗传算法的核心算子都在下面这段代码里。def decode(perm): routes [] route [] cap capacity for c in perm: if demand[c] cap: route.append(c) cap - demand[c] else: if route: routes.append(route) route [c] cap capacity - demand[c] if route: routes.append(route) return routes def route_distance(route): dist distance[(0, route[0])] for i in range(len(route) - 1): dist distance[(route[i], route[i 1])] dist distance[(route[-1], 0)] return dist def fitness(perm): routes decode(perm) total sum(route_distance(r) for r in routes) return total 100 * len(routes) def tournament_selection(pop, k3): selected random.sample(pop, k) return min(selected, keylambda x: x[1]) def order_crossover(p1, p2): n len(p1) a, b sorted(random.sample(range(n), 2)) child [None] * n child[a:b] p1[a:b] pos b for gene in p2: if gene not in child: while pos in range(a, b): pos 1 child[pos] gene pos 1 return child def swap_mutate(perm, rate0.1): if random.random() rate: i, j random.sample(range(len(perm)), 2) perm[i], perm[j] perm[j], perm[i] return permdecode与前面伪代码一致route_distance负责计算从仓库出发、访问完整条路径再返回仓库的距离。fitness中的100 * len(routes)就是车辆权重这里把车辆权重设为固定值 100适用于当前距离量级在 60 到 160 左右的样例数据。tournament_selection是锦标赛选择随机抽 3 个个体取其中适应度最小的一个作为父代。这种选择方式不依赖适应度尺度实现简单而且能在算法早期防止某个超强个体快速垄断种群。order_crossover是顺序交叉先随机选一段连续基因从父代 P1 复制到子代再从 P2 中按照原有顺序填充剩余空位。这样产生的子代永远是一个合法的客户排列不会出现重复客户。swap_mutate是交换变异随机交换染色体上的两个位置。变异率通常保持在 0.05 到 0.2 之间因为顺序交叉本身已经有相当强的随机性。3.3 迭代收敛与结果输出下面把完整主循环串起来。def genetic_algorithm(n_gen200, pop_size100, cx_rate0.8, mut_rate0.1): pop [] for _ in range(pop_size): ind random_individual() pop.append([ind, fitness(ind)]) best_history [] for gen in range(n_gen): pop.sort(keylambda x: x[1]) best_history.append(pop[0][1]) new_pop [ [pop[0][0].copy(), pop[0][1]], [pop[1][0].copy(), pop[1][1]] ] while len(new_pop) pop_size: p1 tournament_selection(pop, 3)[0] p2 tournament_selection(pop, 3)[0] if random.random() cx_rate: child order_crossover(p1, p2) else: child p1[:] if random.random() 0.5 else p2[:] child swap_mutate(child, mut_rate) new_pop.append([child, fitness(child)]) pop new_pop pop.sort(keylambda x: x[1]) return pop[0], best_history best, hist genetic_algorithm() print(最优排列:, best[0]) print(车辆路径:, decode(best[0])) print(总成本:, best[1])运行后能看到输出类似最优排列: [5, 3, 1, 7, 2, 6, 4, 8] 车辆路径: [[5, 3, 1], [7, 2, 6], [4, 8]] 总成本: 415.9主循环的逻辑是每一代先按成本排序把最优的两个个体保留到下一代这就是精英保留其余个体通过锦标赛选择父代以 0.8 的概率做顺序交叉以 0.1 的概率做交换变异最终组成新的种群。运行 200 代后得到的best[0]就是当前找到的最优客户排列。这段代码已经是一个完整的遗传算法求解 VRP 的骨架。在实际使用时需要注意fitness函数和主循环解耦这样才能方便后面对车辆权重、容量约束和时间窗做扩展。4. 车辆调度中容量约束和时间窗的扩展实现4.1 从VRP到CVRP再到VRPTW基础 VRP 不限制车辆容量而实际车辆调度几乎必然涉及载重、体积或行驶时间限制。带容量约束的 CVRP 上面已经实现但如果要面向真实物流还需要考虑时间窗每个客户点有最早服务时间early[i]和最晚服务时间late[i]车辆到达太早要等待到达太晚则不允许服务。处理时间窗的常见做法是在解码时增加一层时间判断。下面这段代码展示如何单独校验一条路径是否满足时间窗service_time {i: 10 for i in range(1, len(coords))} time_window {i: (0, 300) for i in range(len(coords))} def is_time_feasible(route): current_time 0 for idx, node in enumerate(route): prev 0 if idx 0 else route[idx - 1] current_time distance[(prev, node)] if current_time time_window[node][1]: return False current_time max(current_time, time_window[node][0]) service_time[node] return current_time time_window[0][1]is_time_feasible的逻辑是模拟车辆一路开过去的累计时间在到达客户时判断是否晚于最晚时间窗如果没有晚到再把当前时间更新为最早服务时间和到达时间中的较大值加上服务时间。如果仓库也有时间窗最后还要判断车辆回到仓库是否超时。把时间窗判断放进遗传算法时我会把它和容量判断合并到同一个解码函数里。每次准备把一个客户加入当前路径时先临时假设加入并重新计算到达时间如果不满足时间窗就尝试开启新车辆如果新车辆也无法满足则把该个体标记为不可行。这样能够让遗传算法在解码阶段直接过滤掉大量非法解而不是依靠适应度惩罚慢慢淘汰。4.2 惩罚函数让约束变量成为目标的一部分很多初学者喜欢把所有约束都硬编码进合法解但一个强约束到每个个体都必须合法的算法往往很难生成足够的多样性。工程上更常见的做法是允许算法暂时产生少量不可行解但通过惩罚函数让它们的适应度远远差于可行解。表 4-1 给出了常用惩罚项的配置。约束类型惩罚表达式说明容量超载penalty 1e6 * (超载量 1)超载量是超出容量的货物单位时间窗迟到penalty 1000 * (迟到时长 1)迟到时长是到达时间与最晚时间的差超过车辆数上限penalty 1000 * 超出车辆数车辆数是业务固定限制惩罚系数必须和正常适应度值区分开。比如样例中路径距离总量在 300 到 500 之间容量惩罚设置成1e6就能保证任何一个可行解都优于所有不可行解。这里建议把惩罚设计为“超载量的一次函数”而不是固定常量因为固定常量会让算法无法区分超载 1 个单位还是 5 个单位的个体搜索效率会降低。在迭代后期还可以把惩罚系数逐步调大让种群慢慢收敛到可行域。4.3 多目标距离最短与车辆数最少实际车辆调度中距离最短和车辆数最少往往互相矛盾用 3 辆车可以跑出 400 公里用 4 辆车可能只要 350 公里怎么选取决于业务成本模型。一个快速方法是调整车辆权重参数观察不同权重下的最优结果。def fitness_with_weight(perm, vehicle_weight100): routes decode(perm) total sum(route_distance(r) for r in routes) return total vehicle_weight * len(routes) for weight in [10, 50, 100, 200, 500]: best_cost None for _ in range(10): ind random_individual() cost fitness_with_weight(ind, weight) if best_cost is None or cost best_cost: best_cost cost routes decode(ind) total_dist sum(route_distance(r) for r in routes) print(weight, total_dist, len(routes))实际运行时需要把fitness_with_weight替换到遗传算法主循环中这里只用来展示权重改变对路径结构的影响。车辆权重越高算法越倾向于用更少的车但总行驶距离可能增加。调参时可以画出车辆数-距离曲线找到拐点作为业务决策参考。5. 遗传算法参数调优与常见坑点5.1 种群规模、迭代次数、交叉率和变异率的推荐范围遗传算法能不能求解出一个好路径参数往往比算子更重要。表 5-1 是我的常用参考值适用于 10 到 100 个客户点的车辆路径。问题规模更大时需要同步增大种群规模和迭代次数但交叉率和变异率通常保持在下面范围内。参数可直接参考的范围推荐起始值参数影响种群规模50300100过小容易早熟过大会拖慢每代运行时间迭代次数1001000200根据收敛曲线判断是否继续交叉率0.60.90.8过低会削弱搜索能力过高会破坏高价个体变异率0.050.20.1过高会退化成随机搜索精英保留152防止历史上最优解丢失对于客户点只有 8 个的样例种群规模 50、迭代次数 100 已经足够。但当客户点增加到 50 个以上时我一般把种群规模调到 150迭代次数调到 300并每 50 代打印一次最优成本。如果发现连续 50 代成本没有任何变化就说明算法提前收敛需要提高变异率或引入局部搜索。5.2 三种容易踩的坑5.2.1 车辆权重设置不合理一个常见现象是遗传算法已经跑完 500 代但路径图上车辆数量明明还可以减少绕路却很严重。原因通常是车辆权重设得过大算法会在前几代强行把客户塞进少量车辆导致路径交叉。正确的做法是先计算随机个体平均路径长度把车辆权重设为该长度的 0.5 到 2 倍再逐步调整。5.2.2 容量解码顺序影响结果需求不同的情况下顺序扫描排列有时候会产生不必要的空车。比如一辆车容量只有 4连续遇到两个需求为 3 的客户就会开两辆车。更合理的做法是在解码前先把客户按需求降序排列或者对解码完成的路径做一次 2-opt 局部优化。对于纯容量约束按顺序解码仍然是最常见的基础方式性能瓶颈可以留到后处理阶段解决。5.2.3 时间窗约束导致初期可行解太少引入时间窗后随机生成的排列有相当大概率违反时间窗。如果惩罚函数权重不够大算法会把大量资源花在探索不可行区域如果惩罚权重太大种群会快速收敛到个别可行解错过更优路径。我的做法是初始种群中加入 10% 的贪心解贪心策略是每次选择距离当前点最近且满足容量和时间窗的客户剩余 90% 仍然是随机排列保证多样性。5.3 应对早熟收敛的两个手段当收敛曲线在前 20 代就完全变平说明种群失去了多样性。最基本的应对方法是增大变异率但更有效的是“重启策略”将种群中除了精英个体以外的部分全部重新随机初始化。下面是带重启的简化片段for gen in range(n_gen): # 假设已经完成一次遗传迭代 if gen 20 and gen % 30 0: keep pop[:2] new_individuals [[random_individual(), 0] for _ in range(pop_size - 2)] for item in new_individuals: item[1] fitness(item[0]) pop keep new_individuals这段代码每 30 代清空一次种群只保留最优的前两个个体。重启后适应度值会暂时升高但后续几代会再次下降整体上能跳出局部最优。更精细的做法是对精英个体施加多次变异生成大量邻域个体而不是完全随机初始化这样可以在不破坏优秀基因的前提下增加新信息。6. 用收敛曲线和路径可视化验证遗传算法结果6.1 绘制收敛曲线算法写完后第一件事不是看最终路径而是看收敛曲线。把best_history画出来能够判断当前参数是否需要调整。import matplotlib.pyplot as plt best, history genetic_algorithm(n_gen200, pop_size100) plt.plot(range(len(history)), history) plt.xlabel(generation) plt.ylabel(fitness) plt.title(VRP genetic algorithm convergence) plt.savefig(vrp_convergence.png, dpi200) plt.show()正常情况是前 30 代快速下降后面缓慢变平。如果曲线到最后仍然有明显下降趋势说明迭代次数不够可以继续增加n_gen。如果曲线在 10 代内就平了且总成本远高于随机贪心解说明参数需要调整或算法早熟。6.2 路径可视化与解码验证路径可视化能直观检查车辆路线是否存在严重交叉、是否每辆车都从仓库出发并返回仓库。下面这段代码把车辆路径绘制在同一张图上。def plot_routes(best_perm): routes decode(best_perm) fig, ax plt.subplots(figsize(8, 8)) for route in routes: pts [coords[0]] [coords[i] for i in route] [coords[0]] xs, ys zip(*pts) ax.plot(xs, ys, markero, linewidth1.2) ax.scatter(*coords[0], colorred, s120, labeldepot) for idx, (x, y) in enumerate(coords[1:], start1): ax.text(x 1, y 1, str(idx)) ax.legend() ax.set_title(Vehicle Routes) plt.show() def verify_correctness(best_perm): assert len(set(best_perm)) len(best_perm) 8 routes decode(best_perm) visited [c for route in routes for c in route] assert sorted(visited) list(range(1, 9)) verify_correctness(best[0]) plot_routes(best[0])一眼看过去就能发现车辆数是否正确路径是否过长路线之间是否交叉严重。路径可视化还可以和收敛曲线配合使用在同一个坐标下绘制不同收敛阶段的路线图观察算法是把前期精力花在消除交叉还是减少路径。特别是在有容量约束时解码后的路径经常会出现两条很短的路线相邻这时可以通过调整车辆权重观察是否能把它们合并成一条可行路线。6.3 用数值指标代替肉眼判断路径图和收敛曲线只是验证手段最终判断是否值得继续优化我会用三个数字比较总距离所有车辆路径距离之和车辆数解码后routes的长度最优解稳定性连续 50 代最优成本的标准差小于 1e-6说明已经收敛。对于 8 个客户点的样例可以用它验证算法是否真的找到了最优路径。验证通过后再逐步增加客户点并将数据结构从距离字典替换为欧氏距离矩阵就可以接入真实车辆调度数据。本文还有配套的精品资源点击获取