★ FEATURED ARTICLE 简介面向物流优化、运筹学课程设计与Python算法实践者的VRPTW-ga项目聚焦带时间窗车辆路径问题用遗传算法在客户时间窗、车辆容量与路径成本约束下搜索近似最优配送方案。压缩包约671KB文件总数显示为0、类型明细暂无数据具体文件构成需以实际下载内容为准。已有1585人学习或下载说明该主题在课程实验与算法入门中具有一定关注度。项目围绕问题建模、整数编码、适应度评估、选择、交叉、变异和终止条件展开并提供主流程组织与最优解输出思路适合用来理解VRPTW约束如何进入适应度函数以及种群规模、交叉变异概率等参数对收敛效果的影响也可作为遗传算法解决组合优化问题的Python参考实现帮助读者对照复现实验并积累调参经验。1. 车队排不出来的时候我翻出了这套 Python 遗传算法解法去年帮一个做同城配送的朋友看过排班问题一个仓、二十多台车、一百来个客户点每单收货方都有“最早不早于、最晚不晚于”的时间窗车有容量上限。调度员每天早上拿 Excel 手排排到第三十单就开始出错最后只能把不好塞的单子丢到第二天。这类问题在运筹里有个标准名字——带时间窗的车辆路径问题缩写 VRPTW属于 NP 难规模一上来精确算法就跑不动工程上基本靠元启发式遗传算法是其中最常被拿来落地的方案之一。VRPTW-ga 这个项目做的就是这件事用 Python 把遗传算法套到 VRPTW 上读标准算例文件输出一串车辆路线和总里程。它的价值不在于算法有多前沿而在于结构干净——数据解析、解码、算子、评测四块分得很开你换个距离矩阵、加一条新约束不用把整个仓库翻一遍。适合两类人一类是想把课堂上的 GA 真跑起来看结果的学生一类是要把调度算法接进自己业务系统的后端开发。2. 工程结构与数据入口一个 txt 文件怎么变成能求解的实例2.1 目录分层数据、算法、评测三件事分开这个仓库的组织方式基本是按职责切的不按“技术名词”切。常见做法是这样vrptw-ga/ ├── data/ # 算例文件纯文本一个文件一个实例 │ ├── c101.txt │ ├── r101.txt │ └── rc101.txt ├── ga/ │ ├── instance.py # 实例数据结构 算例文件解析 │ ├── decode.py # 染色体 - 路线的解码与适应度 │ ├── operators.py # 交叉、变异、选择 │ └── solver.py # 主循环、参数、日志 ├── run.py # 命令行入口 └── tests/ # 解码正确性的单元测试这么切的理由很实际instance.py决定“问题长什么样”decode.py决定“一个解有多好”operators.py决定“怎么产生新解”。三块里最容易变的是第一块——业务上你的客户点不是从 txt 来的是从数据库或接口来的改这一层不影响另外两层。我见过把解析、解码、交叉全塞进一个 800 行main.py的写法加个新约束要改五个地方那种代码没法二次开发。数据文件用的是业界公开的标准算例格式文件名像c101.txt、r101.txt、rc101.txt这种c是聚类分布、r是随机分布、rc是混合分布数字越大客户越多。项目自带这几份是为了让你开箱就能跑出可对比的数字不是让你拿它当业务数据。2.2 解析算例文件按关键字定位别硬编码行号算例文件的结构是固定段落先车辆信息再客户表C101 VEHICLE NUMBER CAPACITY 25 200 CUSTOMER CUST NO. XCOORD. YCOORD. DEMAND READY TIME DUE DATE SERVICE TIME 0 40 50 0 0 1236 0 1 45 68 10 912 967 90第 0 号点是仓库depot后面的才是客户。解析这段的关键是别数行号——我第一次写的时候按lines[4]、lines[9]这么取换一份格式稍有差异的算例直接崩血泪经验。稳妥的写法是找关键字import math from dataclasses import dataclass, field dataclass class Instance: name: str capacity: int num_vehicles: int coords: list # [(x, y), ...]下标 0 是仓库 demand: list # 每个点的需求量仓库为 0 ready: list # 时间窗下界最早可服务时刻 due: list # 时间窗上界最晚可服务时刻 service: list # 服务时长 dist: list field(default_factorylist) def load_instance(path: str) - Instance: with open(path, encodingutf-8) as f: lines [ln.rstrip(\n) for ln in f if ln.strip() ! ] name lines[0].strip() # 用关键字定位段落避免硬编码行号换算例文件不会翻车 i_veh next(i for i, ln in enumerate(lines) if ln.strip().upper() VEHICLE) i_cus next(i for i, ln in enumerate(lines) if ln.strip().upper() CUSTOMER) # VEHICLE 段下面第二行才是数字NUMBER CAPACITY num_vehicles, capacity map(int, lines[i_veh 2].split()) rows [] for ln in lines[i_cus 2:]: parts ln.split() if len(parts) 7: # 恰好 7 列才算数据行表头自动跳过 rows.append([int(float(p)) for p in parts]) rows.sort(keylambda r: r[0]) # 按编号排序保证下标 客户编号 inst Instance( namename, capacitycapacity, num_vehiclesnum_vehicles, coords[(r[1], r[2]) for r in rows], demand[r[3] for r in rows], ready[r[4] for r in rows], due[r[5] for r in rows], service[r[6] for r in rows], ) inst.dist build_distance(inst.coords) return inst def build_distance(coords): n len(coords) d [[0] * n for _ in range(n)] for i in range(n): for j in range(i 1, n): dx coords[i][0] - coords[j][0] dy coords[i][1] - coords[j][1] d[i][j] d[j][i] int(round(math.hypot(dx, dy))) return d几个参数和逻辑要说明白。rows.sort(keylambda r: r[0])这行是为了让列表下标和客户编号严格对齐后面所有demand[c]、dist[prev][c]都靠这个前提省掉一层字典查找也避免“编号不连续”时越界。距离用hypot算欧氏距离后round取整是因为标准算例的已知最优解都是按整数距离算的你保留浮点会导致最后跟公开结果对不上看起来像算法不行实际上是尺子不一样。int(round(...))里的round是银行家舍入还是四舍五入Python 默认是前者对.5这种边界值会有半整数偏差规模大的算例累积起来能有几十的差距介意的话用math.floor(x 0.5)。i_veh 2和i_cus 2这两个偏移量的含义是关键字占一行表头字段名占一行数字从第三行开始。如果你的算例文件多一行空行或少一行注释这里就会错位——所以len(parts) 7的过滤是第二道保险宁可丢行也不要塞进脏数据。2.3 解编码用客户排列不用“客户-车辆”二维表编码方式决定了后面所有算子的写法。这个项目用的是最经典也最好用的一种染色体是一个客户编号的排列长度等于客户数车辆归属不写在染色体里而是在解码阶段推断。# 染色体示例18 个客户分几辆车由解码决定 chrom [7, 3, 12, 1, 9, 15, 4, 11, 2, 8, 16, 5, 14, 6, 13, 10, 17, 18]为什么不用“每个客户跟一辆车”的二维编码因为二维编码做交叉特别容易产生非法解——父代 A 的第 3 号客户在车 1父代 B 的同一位在车 2交换完可能出现某辆车超载、某辆车空跑你得写一大堆修复逻辑。排列编码天然满足“每个客户被服务且仅被服务一次”交叉变异的结果永远是合法排列约束违反只在解码时体现代码量能少一半。代价是染色体本身不包含车辆数和容量信息一个排列可能“太挤”也可能“太散”。这正好交给解码层处理第三章会讲。3. 解码与适应度一条染色体怎么变成能跑的路线3.1 按容量切段从排列到初始路线解码第一件事是把排列切成若干段每段是一辆车跑的客户序列。切法有讲究常见两种贪心切段和最优分割。贪心切段实现简单按排列顺序往当前车里塞塞不下就开新车def split_by_capacity(chrom, inst): routes, cur, load [], [], 0 for c in chrom: if cur and load inst.demand[c] inst.capacity: routes.append(cur) # 当前车装满收车 cur, load [], 0 cur.append(c) load inst.demand[c] if cur: routes.append(cur) # 别忘了最后一辆 return routesif cur and ...里的cur不能省。少了它第一个客户的需求量如果就超过容量会先 append 一个空路线进去后面统计车辆数多出一台适应度里的车辆惩罚项一直降不下来你会以为是参数没调好实际上是解码有 bug。最优分割则是把“在哪里切”也当成优化问题用动态规划求总代价最小的切法同样一条排列能解出更少车辆或者更短总距离。代价是每次评估多一个 O(n²) 的 DP如果你的客户数上千、种群上千这块会成为瓶颈。我一般先用贪心切段跑通流程确认结果量级对了再换成 DP 看能提升几个百分点。3.2 时间窗推演等待不算违约迟到才算切完段之后要按顺序推每条路线上每个点的到达时刻。这里有个新手最容易搞错的点早到不是违约晚到才是。车 8 点就到了客户门口客户 9 点才收货那就等到 9 点中间的等待时间是成本但不是不可行反过来 10 点才到妥投时限是 9 点半这就是硬违约。def evaluate_routes(routes, inst, w_vehicle1000.0, w_late50.0): total_dist, total_late 0.0, 0.0 for r in routes: t inst.ready[0] # 从仓库时间窗下界出发 prev 0 for c in r: total_dist inst.dist[prev][c] t inst.dist[prev][c] if t inst.ready[c]: t inst.ready[c] # 早到等一等等待不计惩罚 if t inst.due[c]: total_late t - inst.due[c] t inst.service[c] # 服务完才能去下一个点 prev c total_dist inst.dist[prev][0] # 回仓库的那一段别漏 # 回仓时间也要落在仓库时间窗内 back t inst.dist[prev][0] if back inst.due[0]: total_late back - inst.due[0] n_vehicles len(routes) fitness total_dist w_vehicle * n_vehicles w_late * total_late return fitness, total_dist, n_vehicles, total_latew_vehicle和w_late是两个权重量级。w_vehicle 1000的意思是“多开一辆车等价于多跑 1000 单位距离”这个值要和你算例的距离量级匹配——标准算例单条路线的往返距离通常在几百到一千多所以 1000 大约是“显著但不压倒性”如果设成 100000算法会疯狂压缩车辆数宁可让一堆订单迟到时间窗全崩。w_late 50表示每迟到 1 个时间单位折合 50 单位距离它比距离权重大是因为迟到在业务上是不可接受的用大权重把搜索方向往可行解推。初始阶段允许出现不可行解total_late 0是刻意的。遗传算法如果在第一代就只接受可行解初始种群可能根本凑不齐或者要花大量时间做修复。放软约束、用惩罚项引导是这类问题的标准做法。等迭代到中后期total_late自然会被压到 0那时候你再去检查最终解是否 100% 可行。3.3 适应度缓存解码是热点别重复算主循环里同一份染色体可能被评估很多次——精英保留会跨代拿同一批个体锦标赛选择也可能重复抽到同一个。解码一次是 O(n)种群一千、迭代一千就是一百万次评估纯 Python 跑起来会让你去泡第二杯咖啡。常见做法是加一层字典缓存class Evaluator: def __init__(self, inst, w_vehicle1000.0, w_late50.0): self.inst inst self.w_vehicle w_vehicle self.w_late w_late self.cache {} def __call__(self, chrom): key tuple(chrom) # 列表不可哈希转元组 if key in self.cache: return self.cache[key] routes split_by_capacity(chrom, self.inst) res evaluate_routes(routes, self.inst, self.w_vehicle, self.w_late) self.cache[key] res return restuple(chrom)这步是必须的列表不能当字典键。缓存不加也行加上之后通常能省掉三到五成的解码时间而且代码只有十行投入产出比很高。要注意的是缓存会随迭代单调增长客户数上千的时候内存占用不能忽略真跑到那个规模得加个 LRU 淘汰。4. 遗传算子交叉、变异与精英保留4.1 顺序交叉 OX保住相对次序排列编码最常用的交叉是顺序交叉Order Crossover简称 OX。思路是从父代 A 里随机截一段连续片段直接塞进子代剩下的位置按父代 B 里的出现顺序依次填。import random def ox_crossover(p1, p2, rng): n len(p1) a, b sorted(rng.sample(range(n), 2)) # 随机取两个切点 child [None] * n child[a:b 1] p1[a:b 1] # 父代 A 的片段原样保留 seg set(p1[a:b 1]) fill [g for g in p2 if g not in seg] # 父代 B 里去掉已有基因保持相对顺序 idx 0 # 从切片之后的位置开始填绕回到切片之前保证环形连续性 for i in list(range(b 1, n)) list(range(0, a)): child[i] fill[idx] idx 1 return childrng.sample(range(n), 2)取两个不同的下标再排序是为了保证a b切片方向唯一。for i in list(range(b1, n)) list(range(0, a))这个环形的填充顺序是 OX 的精髓它让子代在染色体首尾衔接处也保持父代 B 的相邻关系比简单地从左到右填更容易产生好的路线切分。这个细节如果写错比如直接从 0 填到 a算法照样能跑看不出报错只是收敛变慢、结果差几个百分点属于典型的“黑匣子”问题——不打印中间解根本发现不了。4.2 变异算子交换、逆序、插入各管一件事变异提供种群多样性单一变异算子不够用。这个项目里常见的是三种混着来每次按概率选一个执行def mutate(chrom, rng, p_swap0.3, p_inv0.3): c chrom[:] if rng.random() p_swap: i, j rng.sample(range(len(c)), 2) c[i], c[j] c[j], c[i] # 交换微调局部顺序 if rng.random() p_inv: i, j sorted(rng.sample(range(len(c)), 2)) c[i:j 1] c[i:j 1][::-1] # 逆序等价于 2-opt 的一次翻转 return c交换变异改动小适合在收敛后期做精细搜索逆序变异一次改动一整段等价于对路线做一次 2-opt 翻转能跳出局部最优插入变异把一个客户挪到另一个位置则适合调整车辆的装载分布。三个概率加起来不一定要等于 1因为代码里是各自独立判断的可能一个都不触发也可能两个同时触发——后者其实是有益的一次变异改动更大探索范围更广。p_inv别设太大我一般给 0.2 到 0.3。设到 0.8 以上种群会一直在剧烈抖动精英解刚攒起来就被打散表现是适应度曲线剧烈震荡不下降很多人第一反应是“算法不收敛”其实是变异率调猛了。4.3 选择与精英保留别让最好的解被随机淘汰选择用锦标赛随机抽 k 个个体取适应度最好的那个进下一代。k 越大选择压力越大收敛快但容易早熟k2 到 3 是比较稳的区间。def tournament(population, fitness, k, rng): picked rng.sample(range(len(population)), k) best min(picked, keylambda i: fitness[i]) # 适应度越小越好 return population[best][:]精英保留是另一层保险每代把适应度最好的若干个体原样复制到下一代不参与交叉变异。def next_generation(pop, fit, params, rng, evaluator): order sorted(range(len(pop)), keylambda i: fit[i]) new_pop [pop[i][:] for i in order[:params[elite]]] # 精英直通 while len(new_pop) params[pop_size]: p1 tournament(pop, fit, params[tournament_k], rng) p2 tournament(pop, fit, params[tournament_k], rng) if rng.random() params[cx_rate]: child ox_crossover(p1, p2, rng) else: child p1[:] child mutate(child, rng, params[p_swap], params[p_inv]) new_pop.append(child) return new_popelite一般给 1 到 3。给 0 的话某一代出现的好解可能因为运气不好没被选中直接消失适应度曲线会看到“明明降下去了又弹回去”这是最典型的后悔药场景——你眼睁睁看着最优解被自己的选择算子扔掉。给太多比如 20又会挤占新个体的名额种群多样性下降二十代之后基本靠精英自己在原地打转。4.4 参数与终止条件一张能照着改的表主循环的参数集中放一个字典方便命令行覆盖参数常用值作用调大的后果pop_size100种群规模每次迭代更慢但单代搜索更充分generations500迭代代数收益递减超过一定代数基本不涨cx_rate0.9交叉概率探索增强但可能破坏已收敛的结构p_swap0.3交换变异概率局部扰动变多p_inv0.3逆序变异概率抖动加剧过大时不收敛tournament_k3锦标赛规模选择压力上升早熟风险增加elite2精英保留个数多样性下降w_vehicle1000车辆数惩罚权重车辆数压得更狠可能牺牲时间窗w_late50迟到惩罚权重可行性优先可能里程变长终止条件建议用“最大代数 适应度停滞”的组合光靠代数容易白跑def solve(inst, params, seed42): rng random.Random(seed) # 固定种子结果可复现 evaluator Evaluator(inst, params[w_vehicle], params[w_late]) n len(inst.demand) - 1 # 客户数不含仓库 pop [rng.sample(range(1, n 1), n) for _ in range(params[pop_size])] best, best_fit, stale None, float(inf), 0 for gen in range(params[generations]): fit [evaluator(ind)[0] for ind in pop] i min(range(len(pop)), keylambda k: fit[k]) if fit[i] best_fit - 1e-6: best_fit, best, stale fit[i], pop[i][:], 0 else: stale 1 if gen % 50 0 or stale 0: print(fgen{gen:4d} best{best_fit:.1f} stale{stale}) if stale params[patience]: # 连续 N 代没提升就收工 print(fearly stop at gen {gen}) break pop next_generation(pop, fit, params, rng, evaluator) return best, evaluator(best)rng random.Random(seed)单独建一个随机源不要用全局random。全局状态在并发或者多次调用之间会串味你会发现“同一个种子跑两次结果不一样”排查半天。5. 避坑与排查跑不出可行解时先看这五件事5.1 每次运行结果差异很大同样的参数跑两次差 200 公里现象命令行连续跑两遍日志里最优适应度一个是 828一个是 1043。原因随机种子没固定或者代码里某处用了全局random而主流程用的是Random(seed)实例两条随机流各走各的。另一个隐蔽原因是种群初始化用到了 Python 的set遍历顺序字符串哈希在进程间不一致。解决全流程统一一个random.Random(seed)实例并往下传禁止模块里裸调random.xxx。日志里把种子打出来出问题能原地复现。想要稳定性评估就固定种子跑 10 次看方差而不是拿单次结果说事。5.2 迭代到两百代适应度不再下降但解明显还没优化好现象曲线前 100 代降得挺快之后基本平了最终距离比公开参考值高 15% 以上。原因大概率是种群早熟。锦标赛选择压力大 精英保留 变异率低三代之后全种群都是同一个解的后代交叉等于自己跟自己换。解决先把p_inv从 0.2 提到 0.35 试试再看tournament_k降到 2。如果还不行加“重启”机制——每隔 100 代把最差的 20% 个体用随机排列替换掉强制注入多样性。这类问题没有万能参数得看你的算例规模。5.3 最终解里出现空路线车辆数统计总是比实际多现象打印出来的路线列表里夹着[]车辆数惩罚项怎么调都降不完。原因解码时切段函数在“当前车已经装了东西但下一个客户装不下”的分支里 append 了当前路线但如果初始就进不去比如第一个客户需求大于容量会先 append 一个空列表。另外主循环里对routes做过滤的地方漏了。解决切段函数里if cur:的保护不能省解码出口统一加一句routes [r for r in routes if r]。再顺手加个单元测试构造一个需求量等于容量的客户断言解码结果里没有空路线。5.4 明明时间窗刚好赶上却被判成迟到现象某个客户到达时刻 967时限 967日志显示迟到 0.0001 或者直接算成迟到。原因距离矩阵如果保留浮点累加过程会有精度误差t due[c]就成立了。反过来如果距离取整了但服务时间用了浮点同样会出现边界误判。解决全程用整数运算距离round成 int服务时间和时间窗本来就是整数。判定改成if t inst.due[c] 1e-9给一个极小容差。别小看这个边界解在算例里很多误判一个点就能让整条路线的可行性标记翻车。5.5 换一份算例文件直接抛 IndexError现象c101.txt跑得好好的换成rc201.txt就报列表越界。原因解析时硬编码了行号偏移不同算例文件里空行数量、列头排版不一致偏移量就错了。也有可能某些算例的客户编号不连续你的rows直接按读入顺序存放下标和编号对不上。解决按关键字定位段落第 2 章那段代码数据行用列数过滤读完之后按编号排序并断言rows[0][0] 0且编号连续。这三道检查加上换文件基本不会再崩。6. 二次开发把它接到你自己的业务数据上真正要落地第一步不是改算法是改数据入口。业务数据通常来自数据库或者接口字段名跟算例文件完全对不上还可能缺时间窗。我的做法是写一层适配把业务数据先规整成Instance那个 dataclass后面的解码、算子一行都不用动。def from_business_rows(rows, depot, capacity, num_vehicles): 把业务接口返回的行转成 Instance缺时间窗时给一个宽区间兜底 inst Instance( namebiz, capacitycapacity, num_vehiclesnum_vehicles, coords[(depot[x], depot[y])], demand[0], ready[0], due[10 ** 9], service[0], ) for r in rows: inst.coords.append((r[lon], r[lat])) inst.demand.append(int(r[qty])) inst.ready.append(int(r.get(ready, 0))) inst.due.append(int(r.get(due, 10 ** 9))) # 没时间窗就当没有约束 inst.service.append(int(r.get(service, 0))) inst.dist build_distance(inst.coords) return instdue缺省给10**9是个实用技巧业务上很多客户其实没有严格时限你给个极大值等于“不约束”比给 0 或者干脆报错友好得多。但要注意w_late得跟着调如果大量客户是这种无约束的时间窗惩罚项几乎不起作用算法会退化成纯 CVRP车辆数惩罚的权重要相应提高。想加新约束多车型、优先级、司机工时推荐走“解码层加、算子层不动”的路线。比如限工时就在evaluate_routes里累加行驶加服务时间超了就计入total_late其他代码原样保留。算子层只管排列它不知道也不关心你加了什么业务规则这个边界守住改造成本能压到最低。验证方法别只看总距离。我会固定种子跑 10 次记录最优、中位、最差三个值然后拿算例的公开参考解做 gap 对比——如果中位数 gap 在 5% 以内、最差不超过 10%说明参数组合是稳的如果最好的一次很好、中位数很差那是运气不是能力。再加一个可行性检查断言最终解里每条路线的载重不超容量、每个点的到达时刻不晚于due这两条过不了距离再短也是废解。我现在的习惯是每改一次解码逻辑先跑三个不同规模的算例把车辆数、总距离、迟到量、运行时间打成一行日志跟改之前的基线并排看。有一次我优化了切段逻辑总距离降了 8%结果迟到量从 0 涨到了 1200——那是把不可行解当成了好解。从那以后我每次调完参数、改完算子都强制把可行性断言跑一遍不管曲线多好看。希望帮到你。本文还有配套的精品资源点击获取
阅读完成 · 觉得有帮助？
