别再只盯着TSP了！用Python+遗传算法搞定多旅行商问题（MTSP）实战，附完整代码

用Python遗传算法攻克多旅行商问题从理论到代码的实战指南想象一下你是一家生鲜配送公司的技术负责人每天需要调度20辆货车为200个社区送货。如果每辆车随意分配路线不仅燃油成本飙升司机们也会抱怨工作量不均。这正是经典旅行商问题(TSP)在现实中的升级版——多旅行商问题(MTSP)的典型场景。本文将带你用Python的DEAP框架实现遗传算法解决单仓库(SD-MTSP)和多仓库(MD-MTSP)两类实际问题包含可直接复用的完整代码和可视化方案。1. 为什么MTSP比TSP更值得关注传统TSP研究单个旅行商的最优路径而现实中更多面临的是资源分配问题10辆物流车如何划分100个配送点负载均衡需求确保每个销售代表拜访客户数量相当多中心调度从不同仓库发车的协同配送以生鲜配送为例SD-MTSP对应单冷链中心发车场景而MD-MTSP则适用于区域前置仓模式。遗传算法特别适合这类组合优化问题因为它能处理离散的解空间并行探索多个潜在解通过适应度函数灵活定义优化目标# 适应度函数示例最小化总路径长度 def evaluate(individual): total_distance 0 for route in decode_routes(individual): total_distance calculate_route_distance(route) return total_distance,2. 环境搭建与DEAP库核心概念安装必要的Python包pip install deap matplotlib numpyDEAP框架的关键组件Creator定义个体和适应度类型Toolbox注册遗传操作函数Base.Fitness封装适应度计算逻辑初始化遗传算法环境的典型代码结构from deap import base, creator, tools creator.create(FitnessMin, base.Fitness, weights(-1.0,)) creator.create(Individual, list, fitnesscreator.FitnessMin) toolbox base.Toolbox() toolbox.register(attr_float, random.random) toolbox.register(individual, tools.initRepeat, creator.Individual, toolbox.attr_float, n100)提示权重参数(-1.0,)表示最小化问题对于多目标优化可扩展为(1.0, -1.0)等形式3. SD-MTSP单仓库模型实现3.1 染色体编码设计采用分段编码方案例如前10个基因表示城市分配阈值后续基因代表城市访问顺序def create_individual(n_cities, n_salesmen): # 分配阈值部分 thresholds [random.random() for _ in range(n_salesmen-1)] # 城市访问顺序部分 cities random.sample(range(n_cities), n_cities) return creator.Individual(thresholds cities)3.2 遗传算子定制关键参数经验值操作类型推荐值调整建议交叉概率0.7-0.9高值促进探索变异概率0.01-0.1低值保持稳定种群大小50-200复杂问题需增大实现有序交叉(OX)的示例toolbox.register(mate, tools.cxOrdered) toolbox.register(mutate, tools.mutShuffleIndexes, indpb0.05)3.3 结果可视化使用Matplotlib绘制路线图def plot_routes(routes, depot): colors plt.cm.rainbow(np.linspace(0, 1, len(routes))) for i, (route, color) in enumerate(zip(routes, colors)): x [depot[0]] [c[0] for c in route] [depot[0]] y [depot[1]] [c[1] for c in route] [depot[1]] plt.plot(x, y, o-, colorcolor, labelfSalesman {i1}) plt.legend()4. MD-MTSP多仓库模型进阶4.1 双阶段编码策略第一阶段基因决定销售员-仓库的归属关系第二阶段基因控制城市分配和访问顺序适应度函数需考虑各销售员路径长度均衡性仓库之间的负载平衡总运输成本最小化4.2 约束处理技巧常用方法对比方法优点缺点惩罚函数实现简单需调参修复算子保证可行解设计复杂特殊编码自然满足约束限制搜索空间示例约束处理代码def feasible(individual): routes decode_routes(individual) # 检查是否所有城市都被访问 visited sum([len(r) for r in routes]) return visited total_cities4.3 多目标优化实现扩展适应度函数creator.create(FitnessMulti, base.Fitness, weights(-1.0, -1.0)) # 第一个目标总距离 # 第二个目标最长路径与最短路径的差值5. 性能优化实战技巧5.1 加速计算的关键使用numpy向量化距离计算实现记忆化(memoization)缓存常见路径并行化评估函数from multiprocessing import Pool pool Pool(processes4) toolbox.register(map, pool.map)5.2 超参数调优策略建议的调参流程固定其他参数调整种群大小(50→200)优化选择压力(tournsize3→10)微调交叉/变异概率引入自适应机制5.3 真实案例参数参考某物流公司实施的配置params { pop_size: 150, cx_prob: 0.85, mut_prob: 0.02, ngen: 500, toursize: 5 }6. 常见问题与解决方案Q1 算法收敛过快怎么办增加变异概率采用多样性保护策略尝试岛模型并行进化Q2 如何处理动态需求变化def dynamic_adjustment(population, new_cities): for ind in population: extend_chromosome(ind, len(new_cities)) toolbox.update_environment(new_cities)Q3 大规模实例性能瓶颈突破分治策略先聚类再分区优化启发式初始化用贪心算法生成初始解混合算法结合局部搜索如2-opt在最近一个社区团购项目中通过引入基于Voronoi图的初始分区我们将2000个点的计算时间从8小时缩短到47分钟。关键是要记住没有银弹参数需要根据具体问题特性进行针对性优化。当处理超大规模实例时可以考虑将Python原型重写为C扩展或者转向专门的优化求解器如OR-Tools作为补充方案。