企业官网建设流程全解析

简介：面向物流优化、运筹学课程设计与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_factory=list) def load_instance(path: str) -> Instance: with open(path, encoding="utf-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(key=lambda r: r[0]) # 按编号排序，保证下标 == 客户编号 inst = Instance( name=name, capacity=capacity, num_vehicles=num_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(key=lambda 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 routes

if cur and ...里的cur不能省。少了它，第一个客户的需求量如果就超过容量，会先 append 一个空路线进去，后面统计车辆数多出一台，适应度里的车辆惩罚项一直降不下来，你会以为是参数没调好，实际上是解码有 bug。

最优分割则是把“在哪里切”也当成优化问题，用动态规划求总代价最小的切法，同样一条排列能解出更少车辆或者更短总距离。代价是每次评估多一个 O(n²) 的 DP，如果你的客户数上千、种群上千，这块会成为瓶颈。我一般先用贪心切段跑通流程，确认结果量级对了，再换成 DP 看能提升几个百分点。

3.2 时间窗推演：等待不算违约，迟到才算

切完段之后要按顺序推每条路线上每个点的到达时刻。这里有个新手最容易搞错的点：早到不是违约，晚到才是。车 8 点就到了客户门口，客户 9 点才收货，那就等到 9 点，中间的等待时间是成本但不是不可行；反过来 10 点才到，妥投时限是 9 点半，这就是硬违约。

def evaluate_routes(routes, inst, w_vehicle=1000.0, w_late=50.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_late

w_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_vehicle=1000.0, w_late=50.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 res

tuple(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 child

rng.sample(range(n), 2)取两个不同的下标再排序，是为了保证a < b，切片方向唯一。for i in list(range(b+1, n)) + list(range(0, a))这个环形的填充顺序是 OX 的精髓：它让子代在染色体首尾衔接处也保持父代 B 的相邻关系，比简单地从左到右填更容易产生好的路线切分。这个细节如果写错（比如直接从 0 填到 a），算法照样能跑，看不出报错，只是收敛变慢、结果差几个百分点，属于典型的“黑匣子”问题——不打印中间解根本发现不了。

4.2 变异算子：交换、逆序、插入各管一件事

变异提供种群多样性，单一变异算子不够用。这个项目里常见的是三种混着来，每次按概率选一个执行：

def mutate(chrom, rng, p_swap=0.3, p_inv=0.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 越大选择压力越大，收敛快但容易早熟；k=2 到 3 是比较稳的区间。

def tournament(population, fitness, k, rng): picked = rng.sample(range(len(population)), k) best = min(picked, key=lambda i: fitness[i]) # 适应度越小越好 return population[best][:]

精英保留是另一层保险：每代把适应度最好的若干个体原样复制到下一代，不参与交叉变异。

def next_generation(pop, fit, params, rng, evaluator): order = sorted(range(len(pop)), key=lambda 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_pop

elite一般给 1 到 3。给 0 的话，某一代出现的好解可能因为运气不好没被选中，直接消失，适应度曲线会看到“明明降下去了又弹回去”，这是最典型的后悔药场景——你眼睁睁看着最优解被自己的选择算子扔掉。给太多（比如 20）又会挤占新个体的名额，种群多样性下降，二十代之后基本靠精英自己在原地打转。

4.4 参数与终止条件：一张能照着改的表

主循环的参数集中放一个字典，方便命令行覆盖：

终止条件建议用“最大代数 + 适应度停滞”的组合，光靠代数容易白跑：

def solve(inst, params, seed=42): 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)), key=lambda 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(f"gen={gen:4d} best={best_fit:.1f} stale={stale}") if stale >= params["patience"]: # 连续 N 代没提升就收工 print(f"early 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( name="biz", capacity=capacity, num_vehicles=num_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 inst

due缺省给10**9是个实用技巧：业务上很多客户其实没有严格时限，你给个极大值等于“不约束”，比给 0 或者干脆报错友好得多。但要注意w_late得跟着调，如果大量客户是这种无约束的，时间窗惩罚项几乎不起作用，算法会退化成纯 CVRP，车辆数惩罚的权重要相应提高。

想加新约束（多车型、优先级、司机工时），推荐走“解码层加、算子层不动”的路线。比如限工时，就在evaluate_routes里累加行驶加服务时间，超了就计入total_late，其他代码原样保留。算子层只管排列，它不知道也不关心你加了什么业务规则，这个边界守住，改造成本能压到最低。

验证方法别只看总距离。我会固定种子跑 10 次，记录最优、中位、最差三个值，然后拿算例的公开参考解做 gap 对比——如果中位数 gap 在 5% 以内、最差不超过 10%，说明参数组合是稳的；如果最好的一次很好、中位数很差，那是运气不是能力。再加一个可行性检查：断言最终解里每条路线的载重不超容量、每个点的到达时刻不晚于due，这两条过不了，距离再短也是废解。

我现在的习惯是：每改一次解码逻辑，先跑三个不同规模的算例，把车辆数、总距离、迟到量、运行时间打成一行日志，跟改之前的基线并排看。有一次我优化了切段逻辑，总距离降了 8%，结果迟到量从 0 涨到了 1200——那是把不可行解当成了好解。从那以后我每次调完参数、改完算子，都强制把可行性断言跑一遍，不管曲线多好看。

希望帮到你。

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