遗传算法求解车辆路径问题（VRP）的Python实现与调优指南

简介：一份基于遗传算法求解车辆路径问题（VRP）的MATLAB实现，面向物流调度、运筹优化方向的初学者与算法研究者。资源以单个m文件封装核心算法，涵盖编码方案、种群初始化、适应度计算、选择、交叉、突变及结果解码等关键环节，逻辑紧凑，便于直接运行和调试。通过迭代优化逐步改善车辆行驶路径，可用于理解遗传算法解决组合优化问题的完整流程，并直观观察最优解的收敛过程。压缩包内共1个m文件，大小仅2KB，轻量易用。已有258人学习下载，适合作为入门实践模板。实际应用中可在此基础上扩展容量约束、时间窗口等条件，或结合局部搜索、模拟退火等策略进一步提升解的质量，适合科研与工程场景下的二次开发。

1. VRP 与遗传算法：从“VRP.rar”看车辆路径调度问题

这个压缩包名字直白，但背后是组合优化领域最常被复现的一类项目：用遗传算法求解车辆路径问题（Vehicle Routing Problem，VRP）。场景说开就是物流公司有若干台车、一批客户点，怎么安排每台车的访问顺序，让总行驶距离最短、用车数最少，同时满足载重和时间要求。标题里的“路径”“调度问题”“车辆调度”指的都是同一件事，遗传算法则是用来在几十上百个节点构成的巨大搜索空间里找近似最优解的核心手段。这类代码通常被打包成 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 给出了一个参考。

由于遗传算法习惯“适应度越大越好”，而路径问题是求最小成本，实际代码里可以直接返回总成本并让算法按最小值排序，不需要转换成倒数或负值。这样更方便调试，也能直接看到车辆数和距离的变化。

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, k=3): selected = random.sample(pop, k) return min(selected, key=lambda 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, rate=0.1): if random.random() < rate: i, j = random.sample(range(len(perm)), 2) perm[i], perm[j] = perm[j], perm[i] return perm

decode与前面伪代码一致，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_gen=200, pop_size=100, cx_rate=0.8, mut_rate=0.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(key=lambda 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(key=lambda 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 给出了常用惩罚项的配置。

惩罚系数必须和正常适应度值区分开。比如样例中路径距离总量在 300 到 500 之间，容量惩罚设置成1e6就能保证任何一个可行解都优于所有不可行解。这里建议把惩罚设计为“超载量的一次函数”，而不是固定常量，因为固定常量会让算法无法区分超载 1 个单位还是 5 个单位的个体，搜索效率会降低。在迭代后期，还可以把惩罚系数逐步调大，让种群慢慢收敛到可行域。

4.3 多目标：距离最短与车辆数最少

实际车辆调度中，距离最短和车辆数最少往往互相矛盾：用 3 辆车可以跑出 400 公里，用 4 辆车可能只要 350 公里，怎么选取决于业务成本模型。一个快速方法是调整车辆权重参数，观察不同权重下的最优结果。

def fitness_with_weight(perm, vehicle_weight=100): 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 个客户点的车辆路径。问题规模更大时，需要同步增大种群规模和迭代次数，但交叉率和变异率通常保持在下面范围内。

对于客户点只有 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_gen=200, pop_size=100) plt.plot(range(len(history)), history) plt.xlabel("generation") plt.ylabel("fitness") plt.title("VRP genetic algorithm convergence") plt.savefig("vrp_convergence.png", dpi=200) 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, marker="o", linewidth=1.2) ax.scatter(*coords[0], color="red", s=120, label="depot") for idx, (x, y) in enumerate(coords[1:], start=1): 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 个客户点的样例，可以用它验证算法是否真的找到了最优路径。验证通过后，再逐步增加客户点，并将数据结构从距离字典替换为欧氏距离矩阵，就可以接入真实车辆调度数据。

本文还有配套的精品资源，点击获取