简介这是一份基于遗传算法求解车辆路径问题VRP的MATLAB实现面向物流、交通运输、供应链管理领域的学生与研究者可用于课程设计、算法入门或实际调度场景的快速验证。压缩包内只有一个m脚本文件体积约2KB代码虽小但覆盖了遗传算法求解VRP的主要环节客户点编码、初始种群构建、适应度评估、选择、交叉、变异与结果解码便于读者逐段理解、运行与修改。目前已有258人浏览学习。通过运行该脚本可以直观观察不同代数下配送路线的优化过程理解如何利用遗传算法降低总行驶距离还可在现有代码上扩展车辆容量、时间窗等约束或结合局部搜索、模拟退火等策略进一步提升解质量从而为实际物流调度决策提供参考也为深入研究组合优化问题打下基础。1. 车辆路径调度为什么要用遗传算法配送中心每天早上要派 8 辆车给 64 个客户点送货车有载重限制点是分散的路有来回时间调度员排了三个小时只能给出“看起来顺路”的方案但你算一下总里程比理论最优多了两成。车辆路径问题VRP就是这类场景的数学模型给定一个车库、一组带需求量的客户点、若干容量相同的车在每辆车从车库出发、服务完分配到的客户后返回车库的限制下找到总行驶距离最短的路径集合。这个问题属于 NP-hard客户点超过几十个之后分支定界那类精确算法直接算到天亮而物流排线、外卖调度、维修工单派发这类实时场景根本等不起。遗传算法Genetic Algorithm在 VRP 上的价值不是保证最优而是在秒级到分钟级给出“可以拿去开车”的近似解。它模仿自然选择把一组路径方案当成种群用交叉和变异产生新方案再用适应度函数淘汰差的迭代几十代后收敛到工程上可用的结果。相比禁忌搜索和模拟退火遗传算法实现门槛低解码逻辑写清楚之后加时间窗、加多车型、加车辆数可变都只是在适应度函数里加约束的事。这篇文章就围绕“遗传算法怎么做 VRP 车辆调度”这条主线展开从数学建模、Python 编码实现、参数调优到带容量和时间窗的约束处理给出不需要商用求解器也能跑通的完整做法。2. 车辆路径问题的数学模型与遗传算法编码2.1 VRP 的约束与目标函数标准 CVRPCapacitated Vehicle Routing Problem的输入是一个车场节点 0N 个客户节点 1~N每个客户 i 有需求量 q_i每辆车最大载重 Q。目标是安排若干条从节点 0 出发、服务若干客户后返回节点 0 的回路使所有客户被且仅被服务一次同时每条回路上的总需求量不超过 Q总行驶距离最小。数学上写为 min ∑_{k∈K} ∑_{i,j∈V} d_{ij} × x_{ijk} s.t. ∑_{k∈K} ∑_{j∈V} x_{ijk} 1每个客户 i 只被访问一次i≠0 ∑_{i∈V} x_{ijk} ∑_{j∈V} x_{jik}每个中间节点进出平衡 ∑_{i∈V} q_i × ∑_{j∈V} x_{ijk} ≤ Q容量约束这里 K 是车辆编号集合V 是全部节点集合d_{ij} 是节点 i 到 j 的距离。x_{ijk} 是 0-1 决策变量表示车辆 k 是否从 i 直接开到 j。VRP 和旅行商问题 TSP 的差别就在这里TSP 是派人走完所有点的一条环线VRP 是派多辆车并行走后合并成多段环线。遗传算法处理 TSP 时一个个体就是一条全排列处理 VRP 时一个个体要切成多段每段对应一辆车的路径。这也是后面编码和解码设计的核心分界点。2.2 染色体编码方式客户排列与分段解码常见编码方式有两种。第一种是“多段直接编码”每个基因位存车辆编号同时维护每个车辆对应的客户序列交叉时车辆编号和客户序列都要处理操作复杂度较高。第二种是“客户排列 分隔符解码”这是最常用也更简单的方式染色体是 1~N 的一个全排列比如 [3, 7, 2, 5, 1, 4, 6]解码时从左到右累加客户需求量当加入下一个客户会超过容量 Q 时就在当前位置插入一个分隔符记为 0表示换下一辆车。用上面这个排列和 Q10如果 q34, q75, q23那前两个客户加起来 9 还可以继续再加 q23 就超了所以分隔符插在 3 和 7 之后形成路径 0-3-7-0 和 0-2-5-1-4-6-0假设后段不超载。这种编码的好处是任何 1~N 的排列经过容量约束切分后都天然满足“每个客户只被服务一次”的硬约束越界问题只出现在容量这一层。交叉和变异算子可以直接使用 TSP 领域成熟的 PMX、OX、反转变异不需要设计复杂的多段染色体专用算子。解码时需要注意的是车辆数上限如果切出来的段数超过车队规模 M说明该个体在当前容量下不可行应该给予惩罚而不是直接丢弃。2.2.1 解码算法伪码输入: 排列 route [r1, r2, ..., rN], 需求量 demand[], 容量 Q 输出: 分段后的路径列表 segments cur_load 0 segments [[]] for customer in route: if cur_load demand[customer] Q: segments.append([customer]) # 当前段封口开新段 cur_load demand[customer] else: segments[-1].append(customer) cur_load demand[customer]这个解码规则是贪婪式的它不允许交换相邻两个客户来避免额外车辆段所以同样一段排列可能因为提前触发容量而多分出一辆车。工程上不必在解码阶段做全局优化因为遗传算法会通过迭代筛选掉车辆段数多的个体但如果你希望解码阶段就更激进地压低车辆数可以改成“先检查整个排列能否塞进 M 段再先生成 M 段空路径依次把客户放进装载剩余最多的那一段”。2.3 适应度函数设计让不可行解被淘汰但有生机遗传算法的适应度必须是一个“越大越好”的函数而 VRP 是最小化问题所以一般取总距离的倒数或取一个固定大数减去总距离。最直接的写法是 fitness 1 / total_distance但直接这样写有个问题超载、超时等不可行解的距离可能比可行解更短反而被保留下来。我一般会在距离之外显式叠加惩罚项把约束违反量线性放大例如fitness 1 / (total_distance α * overload β * time_violation)α 和 β 的取值要超出“省一跳路”能带来的收益。例如一次超载如果只是让路程短了 30 公里而 α5超载 10 单位惩罚 50 公里那超载就没有吸引力了。α 和 β 不必一开始就调好可以在种群进化的过程中动态提升前 20 代放宽惩罚以维持种群多样性后 20 代收紧惩罚让它闭着眼睛往可行域方向收敛。3. 用 Python 实现遗传算法求解 VRP 的最低可运行代码3.1 输入数据与距离矩阵先不讲任何开源库手写一个完整可运行的 GA。为了便于演示用 15 个客户点的坐标数据容量 Q35每辆车的按需装载。这种规模下遗传算法跑到 200 代就能稳定给出接近最优的解适合调试算子逻辑。import numpy as np import random # 节点 0 是车场1~15 是客户点 coords np.array([ [50, 50], # depot [10, 60], [20, 30], [30, 10], [40, 20], [50, 40], [60, 30], [70, 50], [80, 60], [90, 70], [15, 80], [35, 70], [45, 85], [55, 90], [65, 95], [75, 80] ]) demands np.array([0, 12, 8, 10, 15, 18, 9, 5, 7, 11, 6, 13, 14, 4, 10, 8]) capacity 35 num_vehicles 5 # 欧氏距离矩阵 n len(coords) dist_matrix np.zeros((n, n)) for i in range(n): for j in range(n): dist_matrix[i][j] np.hypot(coords[i][0] - coords[j][0], coords[i][1] - coords[j][1])距离矩阵是求解的基础后面所有计算都围绕它展开。大多数真实业务里的距离是地图 API 返回的实际道路距离不是直线但遗传算法本身不关心距离怎么来只要 dist_matrix 是(N1)×(N1)的对称矩阵算法逻辑完全一样。3.2 初始化种群与解码函数def generate_individual(): # 随机生成一个客户点排列代表一条完整染色体 return random.sample(range(1, n), n - 1) def decode(individual): # 返回分段路径列表和车辆数 segments [] current [] load 0 for customer in individual: if load demands[customer] capacity: segments.append(current) current [customer] load demands[customer] else: current.append(customer) load demands[customer] if current: segments.append(current) return segments def total_distance(individual): segments decode(individual) dist 0.0 for seg in segments: route [0] seg [0] for i in range(len(route) - 1): dist dist_matrix[route[i]][route[i 1]] # 超车数惩罚 extra_vehicles max(0, len(segments) - num_vehicles) return dist extra_vehicles * 500.0 def fitness(individual): return 1.0 / (total_distance(individual) 1e-6)解码函数里直接返回分段路径不需要单独维护车辆编号。注意总距离函数里加了一个超车数惩罚如果解码出来的段数超过 num_vehicles每多一辆车加 500。500 这个值要远大于正常距离差否则会出现用 6 辆车跑出更短距离但实际车队只有 5 辆的情况。3.3 锦标赛选择、顺序交叉与反转变异遗传算法的三个核心算子中选择容易交叉和变异需要针对排列编码设计。def tournament_selection(population, fitness_values, k3): # 随机挑 k 个个体返回适应度最高的一个 idx random.sample(range(len(population)), k) best max(idx, keylambda i: fitness_values[i]) return population[best] def ordered_crossover(p1, p2): # 顺序交叉 OX1从 p1 中取一段剩余基因按 p2 的相对顺序填充 length len(p1) start random.randint(0, length - 2) end random.randint(start 1, length - 1) child [None] * length child[start:end 1] p1[start:end 1] p2_seq [g for g in p2 if g not in p1[start:end 1]] idx 0 for i in range(length): if child[i] is None: child[i] p2_seq[idx] idx 1 return child def inversion_mutation(individual, prob0.2): if random.random() prob: return individual i random.randint(0, len(individual) - 2) j random.randint(i, len(individual) - 1) individual[i:j 1] reversed(individual[i:j 1]) return individual锦标赛选择 k3 是最常见的经典参数。OX 交叉保留了 p1 中连续的一整段路径片段剩余位置用 p2 中未出现的点按顺序填入这样能最大程度保留父本中局部的路径顺序。反转变异则是把一段客户的访问顺序倒过来相当于在局部改变路径走向适合在收敛后期微调绕路。3.4 进化主循环与结果输出population_size 80 mutation_rate 0.15 generations 300 population [generate_individual() for _ in range(population_size)] for gen in range(generations): fit_vals [fitness(ind) for ind in population] new_pop [] while len(new_pop) population_size: p1 tournament_selection(population, fit_vals) p2 tournament_selection(population, fit_vals) if random.random() 0.8: child1 ordered_crossover(p1, p2) child2 ordered_crossover(p2, p1) else: child1, child2 p1[:], p2[:] child1 inversion_mutation(child1, mutation_rate) child2 inversion_mutation(child2, mutation_rate) new_pop.extend([child1, child2]) population new_pop[:population_size] if gen % 30 0: best_dist min(total_distance(ind) for ind in population) print(fgeneration {gen}, best distance {best_dist:.2f}) best_individual min(population, keytotal_distance) best_segments decode(best_individual) print(best routes:) for i, seg in enumerate(best_segments): print(fvehicle {i 1}: 0 - { - .join(map(str, seg))} - 0)进化循环中每一代先计算适应度再反复选两个父本做交叉和变异生成和种群规模等量的新个体然后整体替换。这里没有使用精英保留机制只是用一个简单问题验证逻辑如果直接用于实际项目至少要把上一代最优个体无条件复制进下一代否则最优解可能在交叉中丢失一次就再也找不回来。4. 遗传算法参数怎么设种群规模、交叉率、变异率与收敛判断4.1 参数对照表与推荐范围遗传算法的表现极度依赖参数。工程上可以记住一组通用区间再根据问题规模微调参数推荐范围设置依据种群规模50~200客户点数越多种群越大。15 个客户用 80100 个客户至少 200交叉率0.7~0.9交叉率过低种群容易提前同质化过高优良片段被打散变异率0.05~0.25按个体计算变异概率要随迭代代数逐渐降低锦标赛规模2~5越大选择压越强但会牺牲种群多样性精英数量1~5至少保留 1 个最优解推荐保留种群规模的 2%参数之间不是独立的。种群规模翻倍时交叉率可以相应降低一点因为靠交叉产生多样性的需求变弱了变异率则要提升因为大种群需要更多随机扰动来避免局部收敛。以第 3 节的代码为例15 个客户点跑 300 代种群 80、交叉 0.8、变异 0.15 通常能在第 50 代左右接近收敛如果客户点变成 100 个我会把种群调到 300代数调到 1000变异率降到 0.08。4.2 自适应变异率让前期探索、后期收敛固定的变异率在后期会造成问题当种群都集中在一个局部最优附近反复反转一小段路径并不能跳出局部极值反而会破坏已经接近最优的排列。常见的做法是线性递减变异率也可以用更简单的自适应公式current_gen 0 total_gen 300 base_mutation 0.25 min_mutation 0.05 def adaptive_mutation_rate(): ratio current_gen / total_gen return base_mutation - (base_mutation - min_mutation) * ratio代际越往后变异率越小意味着遗传算法从“广撒网找解”切换成“局部精细打磨”。这里的关键是判断种群是否还在进化如果连续 20 代最优解都没有改善就说明种群已经收敛此时可以手动把变异率拉回 0.2 再跑 20 代制造一次“重启”。这种重启机制在 VRP 里很有效因为路径排列的组合空间极其崎岖一次收敛到局部最优后单纯小变异很难翻身。4.3 提前终止条件固定迭代代数简单但浪费算力。我一般会同时设置两个终止条件no_improve_count 0 best_ever float(inf) for gen in range(max_generations): # ... 进化代码 ... current_best min(total_distance(ind) for ind in population) if current_best best_ever - 1e-6: best_ever current_best no_improve_count 0 else: no_improve_count 1 if no_improve_count 50: break连续 50 代最优解没有下降 1e-6基本可以断定收敛。这里 1e-6 的阈值很关键它允许计算浮点误差但不会把真的改进漏掉。另外要记录 best_ever 而不是当前代的最优因为最小化问题里一代可能因为交叉算子把所有好解都打散了最优值暂时恶化但下一代会重新爬上来所以只看“全局最优”决定是否终止更稳妥。5. 带约束的实际调度容量限制与时间窗不能只靠罚函数第 3 节的解码里已经处理了容量约束那是硬约束直接在解码阶段就保证不会超载。但真实车辆调度往往还有时间窗约束客户要求“上午 9 点到 11 点之间到达”或者最长行驶时间限制。时间窗不像容量那样能在解码时简单切段因为超时是路径顺序导致的两个客户的排列顺序会影响前一个的服务时间进而影响后一个客户的到达时间。5.1 在适应度函数中显式计算时间窗违反量定义每个客户 i 的服务时间 si最早到达时间 ei最晚到达时间 li。车辆从节点 i 到 j 的行驶时间是 tij通常等于距离除以速度。从车场出发时刻设为 0到达节点 j 的时刻是 arrival_j arrival_i si tij如果车辆到达早于 ei一般允许等待到达晚于 li就算超时。实现时不再只累加距离而是在计算完整条路径后统计所有客户的超时时间总和service_time np.array([0, 5, 8, 4, 6, 7, 3, 5, 9, 2, 4, 6, 5, 8, 3, 7]) time_windows np.array([ [0, 100], # 车场 [10, 40], [20, 60], [15, 50], [30, 70], [25, 65], [40, 80], [35, 75], [45, 85], [50, 90], [55, 95], [60, 100], [65, 105], [70, 110], [75, 115], [80, 120] ]) speed 1.0 # 距离单位/时间单位便于演示 def total_time_violation(segments): total_wait 0.0 # 等待时间不算惩罚 total_violation 0.0 for seg in segments: t 0.0 current_node 0 for node in seg: t dist_matrix[current_node][node] / speed if t time_windows[node][0]: t time_windows[node][0] elif t time_windows[node][1]: total_violation t - time_windows[node][1] t service_time[node] current_node node t dist_matrix[current_node][0] / speed return total_violation这个函数里早到只是把时间拨到最早允许时间相当于允许司机等待不产生惩罚晚到则累计超出量。注意它必须在解码后的 segments 上计算所以适应度函数现在变成def fitness_with_constraints(individual): segments decode(individual) d total_distance(individual) tw_violation total_time_violation(segments) return 1.0 / (d 300.0 * tw_violation 1e-6)时间窗违反量乘以 300这个惩罚系数要远大于距离量级。如果总距离正常是 300~500超时 1 分钟罚 300 等于让车辆多绕一整圈路这样 GA 才会优先尝试满足时间窗的路径排列。5.2 容量约束在解码阶段处理时间窗交给适应度阶段这里有一个容易踩的坑有人在解码阶段就把超过时间窗的客户节点单独切出来试图保证每条路径时间窗都可行。这样做的问题在于时间窗约束是可变的一个节点在路径 A 中排在前面可能不超时在路径 B 中排在后面就超时单纯靠解码切段无法判断反而破坏了染色体原本要表达的路径顺序。所以容量用硬约束处理时间窗用软惩罚处理是更稳健的工程分离。如果业务要求“必须全部严格满足时间窗”那么进化结束后要多加一层修复函数对每一辆车的客户序列按最早时间窗重新排序例如按照 time_windows[i][0] 升序排列但这可能会破坏路径连续性。更快的方法是继续迭代同时持续提高时间窗惩罚系数比如每 20 代把系数翻倍让不可行解的适应度被压到极低最后一个可行解必然胜出。5.3 如何判断“这个解到底可不可行”跑完 GA 后不能只看距离要把约束违反量单独打印出来。写一个 report 函数def verify_solution(segments): loads [] tw_violations [] for seg in segments: total_load sum(demands[node] for node in seg) loads.append(total_load) tw_violations.append(total_time_violation([seg])) return { vehicle_count: len(segments), loads: loads, capacity_exceeded: any(l capacity for l in loads), time_violations: tw_violations }这种做法可以快速发现两个常见陷阱。第一容量约束虽然解码时不会超载但修改算法后有人把解码顺序改错了导致切段时漏掉了容量检查第二时间窗惩罚项在适应度里的权重大低最终解虽然距离漂亮但没有一辆车的时间窗是满足的。把验证结果打印出来你就不会把不可行解当作方案交付给调度系统。6. 三种验证技巧标准算例对比、路径可视化和多次运行统计6.1 用标准 CVRP 算例验证解的误差上界自造的随机数据只能说明代码能跑不能说明解的质量。行业内常用 Augerat 系列算例如 A-n32-k5和 Christofides 系列做基准测试它们提供已知最优解。下载后把客户坐标、需求量和容量喂给解码函数注意先处理文件里DIMENSION和CAPACITY字段再把坐标数组读入距离矩阵。对比 GA 结果和已知最优解看误差率是否在可接受范围内。例如 A-n32-k5 已知最优距离为 784如果你的 GA 跑出的结果是 795~810说明算子实现没问题如果跑出 900 以上优先检查解码是否正确地生成了 M 条以内的路径。6.2 用 matplotlib 直接散点连线一眼看出绕路和串线问题import matplotlib.pyplot as plt def plot_routes(segments, coords): plt.figure(figsize(8, 8)) for seg in segments: route [0] seg [0] x [coords[node][0] for node in route] y [coords[node][1] for node in route] plt.plot(x, y, markero, linewidth1.5) for i, node in enumerate(range(len(coords))): plt.text(coords[node][0] 1, coords[node][1] 1, str(node)) plt.title(VRP Genetic Algorithm Routes) plt.show()把每辆车的路径用不同颜色的折线画出来经常能看到遗传算法解里两条路径交叉打结。注意路径交叉不一定代表不是最优因为距离矩阵可能是基于道路网的折线交叉不代表实际道路交叉但如果距离是欧氏距离且两条线路又交叉又重叠说明局部搜索能力不够。此时可以针对最优解运行一种简单的 2-opt 局部优化对每辆车路径中任意两对边做交换如果总距离下降就保留交换迭代直到无法改进。6.3 多次运行并记录最优、平均、最差遗传算法是随机算法一次运行的结果没有参考价值。至少跑 10 次记录每次的最优距离和首次找到最优解的代数results [] for run in range(10): # 重新初始化种群跑完整进化 best_seq None best_val float(inf) # ... 进化循环 ... results.append((best_val, run)) values [v for v, _ in results] print(fmin{min(values):.2f} avg{np.mean(values):.2f} max{max(values):.2f}) print(fstd{np.std(values):.2f}) # 保存最优个体到 CSV后续可直接解码 best_individual min(results, keylambda x: x[0])标准差比平均值更能反映算法稳定性。如果 10 次运行的标准差大于平均值的 3%说明变异率过高或种群太小应该把变异率下调到 0.1 再测如果标准差很小但平均值明显偏离已知最优说明选择压太强种群过早收敛需要提升变异率或增大种群。用这个流程去调参两周内你能把任意 VRP 实例的遗传算法方案调到“敢拿去给业务用”的程度。本文还有配套的精品资源点击获取
遗传算法求解车辆路径问题（VRP）的Python实现与工程实践
简介这是一份基于遗传算法求解车辆路径问题VRP的MATLAB实现面向物流、交通运输、供应链管理领域的学生与研究者可用于课程设计、算法入门或实际调度场景的快速验证。压缩包内只有一个m脚本文件体积约2KB代码虽小但覆盖了遗传算法求解VRP的主要环节客户点编码、初始种群构建、适应度评估、选择、交叉、变异与结果解码便于读者逐段理解、运行与修改。目前已有258人浏览学习。通过运行该脚本可以直观观察不同代数下配送路线的优化过程理解如何利用遗传算法降低总行驶距离还可在现有代码上扩展车辆容量、时间窗等约束或结合局部搜索、模拟退火等策略进一步提升解质量从而为实际物流调度决策提供参考也为深入研究组合优化问题打下基础。1. 车辆路径调度为什么要用遗传算法配送中心每天早上要派 8 辆车给 64 个客户点送货车有载重限制点是分散的路有来回时间调度员排了三个小时只能给出“看起来顺路”的方案但你算一下总里程比理论最优多了两成。车辆路径问题VRP就是这类场景的数学模型给定一个车库、一组带需求量的客户点、若干容量相同的车在每辆车从车库出发、服务完分配到的客户后返回车库的限制下找到总行驶距离最短的路径集合。这个问题属于 NP-hard客户点超过几十个之后分支定界那类精确算法直接算到天亮而物流排线、外卖调度、维修工单派发这类实时场景根本等不起。遗传算法Genetic Algorithm在 VRP 上的价值不是保证最优而是在秒级到分钟级给出“可以拿去开车”的近似解。它模仿自然选择把一组路径方案当成种群用交叉和变异产生新方案再用适应度函数淘汰差的迭代几十代后收敛到工程上可用的结果。相比禁忌搜索和模拟退火遗传算法实现门槛低解码逻辑写清楚之后加时间窗、加多车型、加车辆数可变都只是在适应度函数里加约束的事。这篇文章就围绕“遗传算法怎么做 VRP 车辆调度”这条主线展开从数学建模、Python 编码实现、参数调优到带容量和时间窗的约束处理给出不需要商用求解器也能跑通的完整做法。2. 车辆路径问题的数学模型与遗传算法编码2.1 VRP 的约束与目标函数标准 CVRPCapacitated Vehicle Routing Problem的输入是一个车场节点 0N 个客户节点 1~N每个客户 i 有需求量 q_i每辆车最大载重 Q。目标是安排若干条从节点 0 出发、服务若干客户后返回节点 0 的回路使所有客户被且仅被服务一次同时每条回路上的总需求量不超过 Q总行驶距离最小。数学上写为 min ∑_{k∈K} ∑_{i,j∈V} d_{ij} × x_{ijk} s.t. ∑_{k∈K} ∑_{j∈V} x_{ijk} 1每个客户 i 只被访问一次i≠0 ∑_{i∈V} x_{ijk} ∑_{j∈V} x_{jik}每个中间节点进出平衡 ∑_{i∈V} q_i × ∑_{j∈V} x_{ijk} ≤ Q容量约束这里 K 是车辆编号集合V 是全部节点集合d_{ij} 是节点 i 到 j 的距离。x_{ijk} 是 0-1 决策变量表示车辆 k 是否从 i 直接开到 j。VRP 和旅行商问题 TSP 的差别就在这里TSP 是派人走完所有点的一条环线VRP 是派多辆车并行走后合并成多段环线。遗传算法处理 TSP 时一个个体就是一条全排列处理 VRP 时一个个体要切成多段每段对应一辆车的路径。这也是后面编码和解码设计的核心分界点。2.2 染色体编码方式客户排列与分段解码常见编码方式有两种。第一种是“多段直接编码”每个基因位存车辆编号同时维护每个车辆对应的客户序列交叉时车辆编号和客户序列都要处理操作复杂度较高。第二种是“客户排列 分隔符解码”这是最常用也更简单的方式染色体是 1~N 的一个全排列比如 [3, 7, 2, 5, 1, 4, 6]解码时从左到右累加客户需求量当加入下一个客户会超过容量 Q 时就在当前位置插入一个分隔符记为 0表示换下一辆车。用上面这个排列和 Q10如果 q34, q75, q23那前两个客户加起来 9 还可以继续再加 q23 就超了所以分隔符插在 3 和 7 之后形成路径 0-3-7-0 和 0-2-5-1-4-6-0假设后段不超载。这种编码的好处是任何 1~N 的排列经过容量约束切分后都天然满足“每个客户只被服务一次”的硬约束越界问题只出现在容量这一层。交叉和变异算子可以直接使用 TSP 领域成熟的 PMX、OX、反转变异不需要设计复杂的多段染色体专用算子。解码时需要注意的是车辆数上限如果切出来的段数超过车队规模 M说明该个体在当前容量下不可行应该给予惩罚而不是直接丢弃。2.2.1 解码算法伪码输入: 排列 route [r1, r2, ..., rN], 需求量 demand[], 容量 Q 输出: 分段后的路径列表 segments cur_load 0 segments [[]] for customer in route: if cur_load demand[customer] Q: segments.append([customer]) # 当前段封口开新段 cur_load demand[customer] else: segments[-1].append(customer) cur_load demand[customer]这个解码规则是贪婪式的它不允许交换相邻两个客户来避免额外车辆段所以同样一段排列可能因为提前触发容量而多分出一辆车。工程上不必在解码阶段做全局优化因为遗传算法会通过迭代筛选掉车辆段数多的个体但如果你希望解码阶段就更激进地压低车辆数可以改成“先检查整个排列能否塞进 M 段再先生成 M 段空路径依次把客户放进装载剩余最多的那一段”。2.3 适应度函数设计让不可行解被淘汰但有生机遗传算法的适应度必须是一个“越大越好”的函数而 VRP 是最小化问题所以一般取总距离的倒数或取一个固定大数减去总距离。最直接的写法是 fitness 1 / total_distance但直接这样写有个问题超载、超时等不可行解的距离可能比可行解更短反而被保留下来。我一般会在距离之外显式叠加惩罚项把约束违反量线性放大例如fitness 1 / (total_distance α * overload β * time_violation)α 和 β 的取值要超出“省一跳路”能带来的收益。例如一次超载如果只是让路程短了 30 公里而 α5超载 10 单位惩罚 50 公里那超载就没有吸引力了。α 和 β 不必一开始就调好可以在种群进化的过程中动态提升前 20 代放宽惩罚以维持种群多样性后 20 代收紧惩罚让它闭着眼睛往可行域方向收敛。3. 用 Python 实现遗传算法求解 VRP 的最低可运行代码3.1 输入数据与距离矩阵先不讲任何开源库手写一个完整可运行的 GA。为了便于演示用 15 个客户点的坐标数据容量 Q35每辆车的按需装载。这种规模下遗传算法跑到 200 代就能稳定给出接近最优的解适合调试算子逻辑。import numpy as np import random # 节点 0 是车场1~15 是客户点 coords np.array([ [50, 50], # depot [10, 60], [20, 30], [30, 10], [40, 20], [50, 40], [60, 30], [70, 50], [80, 60], [90, 70], [15, 80], [35, 70], [45, 85], [55, 90], [65, 95], [75, 80] ]) demands np.array([0, 12, 8, 10, 15, 18, 9, 5, 7, 11, 6, 13, 14, 4, 10, 8]) capacity 35 num_vehicles 5 # 欧氏距离矩阵 n len(coords) dist_matrix np.zeros((n, n)) for i in range(n): for j in range(n): dist_matrix[i][j] np.hypot(coords[i][0] - coords[j][0], coords[i][1] - coords[j][1])距离矩阵是求解的基础后面所有计算都围绕它展开。大多数真实业务里的距离是地图 API 返回的实际道路距离不是直线但遗传算法本身不关心距离怎么来只要 dist_matrix 是(N1)×(N1)的对称矩阵算法逻辑完全一样。3.2 初始化种群与解码函数def generate_individual(): # 随机生成一个客户点排列代表一条完整染色体 return random.sample(range(1, n), n - 1) def decode(individual): # 返回分段路径列表和车辆数 segments [] current [] load 0 for customer in individual: if load demands[customer] capacity: segments.append(current) current [customer] load demands[customer] else: current.append(customer) load demands[customer] if current: segments.append(current) return segments def total_distance(individual): segments decode(individual) dist 0.0 for seg in segments: route [0] seg [0] for i in range(len(route) - 1): dist dist_matrix[route[i]][route[i 1]] # 超车数惩罚 extra_vehicles max(0, len(segments) - num_vehicles) return dist extra_vehicles * 500.0 def fitness(individual): return 1.0 / (total_distance(individual) 1e-6)解码函数里直接返回分段路径不需要单独维护车辆编号。注意总距离函数里加了一个超车数惩罚如果解码出来的段数超过 num_vehicles每多一辆车加 500。500 这个值要远大于正常距离差否则会出现用 6 辆车跑出更短距离但实际车队只有 5 辆的情况。3.3 锦标赛选择、顺序交叉与反转变异遗传算法的三个核心算子中选择容易交叉和变异需要针对排列编码设计。def tournament_selection(population, fitness_values, k3): # 随机挑 k 个个体返回适应度最高的一个 idx random.sample(range(len(population)), k) best max(idx, keylambda i: fitness_values[i]) return population[best] def ordered_crossover(p1, p2): # 顺序交叉 OX1从 p1 中取一段剩余基因按 p2 的相对顺序填充 length len(p1) start random.randint(0, length - 2) end random.randint(start 1, length - 1) child [None] * length child[start:end 1] p1[start:end 1] p2_seq [g for g in p2 if g not in p1[start:end 1]] idx 0 for i in range(length): if child[i] is None: child[i] p2_seq[idx] idx 1 return child def inversion_mutation(individual, prob0.2): if random.random() prob: return individual i random.randint(0, len(individual) - 2) j random.randint(i, len(individual) - 1) individual[i:j 1] reversed(individual[i:j 1]) return individual锦标赛选择 k3 是最常见的经典参数。OX 交叉保留了 p1 中连续的一整段路径片段剩余位置用 p2 中未出现的点按顺序填入这样能最大程度保留父本中局部的路径顺序。反转变异则是把一段客户的访问顺序倒过来相当于在局部改变路径走向适合在收敛后期微调绕路。3.4 进化主循环与结果输出population_size 80 mutation_rate 0.15 generations 300 population [generate_individual() for _ in range(population_size)] for gen in range(generations): fit_vals [fitness(ind) for ind in population] new_pop [] while len(new_pop) population_size: p1 tournament_selection(population, fit_vals) p2 tournament_selection(population, fit_vals) if random.random() 0.8: child1 ordered_crossover(p1, p2) child2 ordered_crossover(p2, p1) else: child1, child2 p1[:], p2[:] child1 inversion_mutation(child1, mutation_rate) child2 inversion_mutation(child2, mutation_rate) new_pop.extend([child1, child2]) population new_pop[:population_size] if gen % 30 0: best_dist min(total_distance(ind) for ind in population) print(fgeneration {gen}, best distance {best_dist:.2f}) best_individual min(population, keytotal_distance) best_segments decode(best_individual) print(best routes:) for i, seg in enumerate(best_segments): print(fvehicle {i 1}: 0 - { - .join(map(str, seg))} - 0)进化循环中每一代先计算适应度再反复选两个父本做交叉和变异生成和种群规模等量的新个体然后整体替换。这里没有使用精英保留机制只是用一个简单问题验证逻辑如果直接用于实际项目至少要把上一代最优个体无条件复制进下一代否则最优解可能在交叉中丢失一次就再也找不回来。4. 遗传算法参数怎么设种群规模、交叉率、变异率与收敛判断4.1 参数对照表与推荐范围遗传算法的表现极度依赖参数。工程上可以记住一组通用区间再根据问题规模微调参数推荐范围设置依据种群规模50~200客户点数越多种群越大。15 个客户用 80100 个客户至少 200交叉率0.7~0.9交叉率过低种群容易提前同质化过高优良片段被打散变异率0.05~0.25按个体计算变异概率要随迭代代数逐渐降低锦标赛规模2~5越大选择压越强但会牺牲种群多样性精英数量1~5至少保留 1 个最优解推荐保留种群规模的 2%参数之间不是独立的。种群规模翻倍时交叉率可以相应降低一点因为靠交叉产生多样性的需求变弱了变异率则要提升因为大种群需要更多随机扰动来避免局部收敛。以第 3 节的代码为例15 个客户点跑 300 代种群 80、交叉 0.8、变异 0.15 通常能在第 50 代左右接近收敛如果客户点变成 100 个我会把种群调到 300代数调到 1000变异率降到 0.08。4.2 自适应变异率让前期探索、后期收敛固定的变异率在后期会造成问题当种群都集中在一个局部最优附近反复反转一小段路径并不能跳出局部极值反而会破坏已经接近最优的排列。常见的做法是线性递减变异率也可以用更简单的自适应公式current_gen 0 total_gen 300 base_mutation 0.25 min_mutation 0.05 def adaptive_mutation_rate(): ratio current_gen / total_gen return base_mutation - (base_mutation - min_mutation) * ratio代际越往后变异率越小意味着遗传算法从“广撒网找解”切换成“局部精细打磨”。这里的关键是判断种群是否还在进化如果连续 20 代最优解都没有改善就说明种群已经收敛此时可以手动把变异率拉回 0.2 再跑 20 代制造一次“重启”。这种重启机制在 VRP 里很有效因为路径排列的组合空间极其崎岖一次收敛到局部最优后单纯小变异很难翻身。4.3 提前终止条件固定迭代代数简单但浪费算力。我一般会同时设置两个终止条件no_improve_count 0 best_ever float(inf) for gen in range(max_generations): # ... 进化代码 ... current_best min(total_distance(ind) for ind in population) if current_best best_ever - 1e-6: best_ever current_best no_improve_count 0 else: no_improve_count 1 if no_improve_count 50: break连续 50 代最优解没有下降 1e-6基本可以断定收敛。这里 1e-6 的阈值很关键它允许计算浮点误差但不会把真的改进漏掉。另外要记录 best_ever 而不是当前代的最优因为最小化问题里一代可能因为交叉算子把所有好解都打散了最优值暂时恶化但下一代会重新爬上来所以只看“全局最优”决定是否终止更稳妥。5. 带约束的实际调度容量限制与时间窗不能只靠罚函数第 3 节的解码里已经处理了容量约束那是硬约束直接在解码阶段就保证不会超载。但真实车辆调度往往还有时间窗约束客户要求“上午 9 点到 11 点之间到达”或者最长行驶时间限制。时间窗不像容量那样能在解码时简单切段因为超时是路径顺序导致的两个客户的排列顺序会影响前一个的服务时间进而影响后一个客户的到达时间。5.1 在适应度函数中显式计算时间窗违反量定义每个客户 i 的服务时间 si最早到达时间 ei最晚到达时间 li。车辆从节点 i 到 j 的行驶时间是 tij通常等于距离除以速度。从车场出发时刻设为 0到达节点 j 的时刻是 arrival_j arrival_i si tij如果车辆到达早于 ei一般允许等待到达晚于 li就算超时。实现时不再只累加距离而是在计算完整条路径后统计所有客户的超时时间总和service_time np.array([0, 5, 8, 4, 6, 7, 3, 5, 9, 2, 4, 6, 5, 8, 3, 7]) time_windows np.array([ [0, 100], # 车场 [10, 40], [20, 60], [15, 50], [30, 70], [25, 65], [40, 80], [35, 75], [45, 85], [50, 90], [55, 95], [60, 100], [65, 105], [70, 110], [75, 115], [80, 120] ]) speed 1.0 # 距离单位/时间单位便于演示 def total_time_violation(segments): total_wait 0.0 # 等待时间不算惩罚 total_violation 0.0 for seg in segments: t 0.0 current_node 0 for node in seg: t dist_matrix[current_node][node] / speed if t time_windows[node][0]: t time_windows[node][0] elif t time_windows[node][1]: total_violation t - time_windows[node][1] t service_time[node] current_node node t dist_matrix[current_node][0] / speed return total_violation这个函数里早到只是把时间拨到最早允许时间相当于允许司机等待不产生惩罚晚到则累计超出量。注意它必须在解码后的 segments 上计算所以适应度函数现在变成def fitness_with_constraints(individual): segments decode(individual) d total_distance(individual) tw_violation total_time_violation(segments) return 1.0 / (d 300.0 * tw_violation 1e-6)时间窗违反量乘以 300这个惩罚系数要远大于距离量级。如果总距离正常是 300~500超时 1 分钟罚 300 等于让车辆多绕一整圈路这样 GA 才会优先尝试满足时间窗的路径排列。5.2 容量约束在解码阶段处理时间窗交给适应度阶段这里有一个容易踩的坑有人在解码阶段就把超过时间窗的客户节点单独切出来试图保证每条路径时间窗都可行。这样做的问题在于时间窗约束是可变的一个节点在路径 A 中排在前面可能不超时在路径 B 中排在后面就超时单纯靠解码切段无法判断反而破坏了染色体原本要表达的路径顺序。所以容量用硬约束处理时间窗用软惩罚处理是更稳健的工程分离。如果业务要求“必须全部严格满足时间窗”那么进化结束后要多加一层修复函数对每一辆车的客户序列按最早时间窗重新排序例如按照 time_windows[i][0] 升序排列但这可能会破坏路径连续性。更快的方法是继续迭代同时持续提高时间窗惩罚系数比如每 20 代把系数翻倍让不可行解的适应度被压到极低最后一个可行解必然胜出。5.3 如何判断“这个解到底可不可行”跑完 GA 后不能只看距离要把约束违反量单独打印出来。写一个 report 函数def verify_solution(segments): loads [] tw_violations [] for seg in segments: total_load sum(demands[node] for node in seg) loads.append(total_load) tw_violations.append(total_time_violation([seg])) return { vehicle_count: len(segments), loads: loads, capacity_exceeded: any(l capacity for l in loads), time_violations: tw_violations }这种做法可以快速发现两个常见陷阱。第一容量约束虽然解码时不会超载但修改算法后有人把解码顺序改错了导致切段时漏掉了容量检查第二时间窗惩罚项在适应度里的权重大低最终解虽然距离漂亮但没有一辆车的时间窗是满足的。把验证结果打印出来你就不会把不可行解当作方案交付给调度系统。6. 三种验证技巧标准算例对比、路径可视化和多次运行统计6.1 用标准 CVRP 算例验证解的误差上界自造的随机数据只能说明代码能跑不能说明解的质量。行业内常用 Augerat 系列算例如 A-n32-k5和 Christofides 系列做基准测试它们提供已知最优解。下载后把客户坐标、需求量和容量喂给解码函数注意先处理文件里DIMENSION和CAPACITY字段再把坐标数组读入距离矩阵。对比 GA 结果和已知最优解看误差率是否在可接受范围内。例如 A-n32-k5 已知最优距离为 784如果你的 GA 跑出的结果是 795~810说明算子实现没问题如果跑出 900 以上优先检查解码是否正确地生成了 M 条以内的路径。6.2 用 matplotlib 直接散点连线一眼看出绕路和串线问题import matplotlib.pyplot as plt def plot_routes(segments, coords): plt.figure(figsize(8, 8)) for seg in segments: route [0] seg [0] x [coords[node][0] for node in route] y [coords[node][1] for node in route] plt.plot(x, y, markero, linewidth1.5) for i, node in enumerate(range(len(coords))): plt.text(coords[node][0] 1, coords[node][1] 1, str(node)) plt.title(VRP Genetic Algorithm Routes) plt.show()把每辆车的路径用不同颜色的折线画出来经常能看到遗传算法解里两条路径交叉打结。注意路径交叉不一定代表不是最优因为距离矩阵可能是基于道路网的折线交叉不代表实际道路交叉但如果距离是欧氏距离且两条线路又交叉又重叠说明局部搜索能力不够。此时可以针对最优解运行一种简单的 2-opt 局部优化对每辆车路径中任意两对边做交换如果总距离下降就保留交换迭代直到无法改进。6.3 多次运行并记录最优、平均、最差遗传算法是随机算法一次运行的结果没有参考价值。至少跑 10 次记录每次的最优距离和首次找到最优解的代数results [] for run in range(10): # 重新初始化种群跑完整进化 best_seq None best_val float(inf) # ... 进化循环 ... results.append((best_val, run)) values [v for v, _ in results] print(fmin{min(values):.2f} avg{np.mean(values):.2f} max{max(values):.2f}) print(fstd{np.std(values):.2f}) # 保存最优个体到 CSV后续可直接解码 best_individual min(results, keylambda x: x[0])标准差比平均值更能反映算法稳定性。如果 10 次运行的标准差大于平均值的 3%说明变异率过高或种群太小应该把变异率下调到 0.1 再测如果标准差很小但平均值明显偏离已知最优说明选择压太强种群过早收敛需要提升变异率或增大种群。用这个流程去调参两周内你能把任意 VRP 实例的遗传算法方案调到“敢拿去给业务用”的程度。本文还有配套的精品资源点击获取