遗传算法求解带时间窗的车辆路径问题

作     者：周景欣 

作者机构：重庆交通大学经济与管理学院 

出 版 物：《中国储运》 (China Storage & Transport)

年 卷 期：2023年第1期

页      面：100-101页

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 081104[工学-模式识别与智能系统] 08[工学] 082303[工学-交通运输规划与管理] 0835[工学-软件工程] 082302[工学-交通信息工程及控制] 0811[工学-控制科学与工程] 0812[工学-计算机科学与技术（可授工学、理学学位）] 0823[工学-交通运输工程] 

主　　题：带时间窗的车辆路径问题 局部搜索策略 简单遗传算法 多目标问题 精确算法 大型超市 交付时间 客户服务 

摘      要：引言随着互联网的进步,电子商务业的飞速发展,人们的生活愈发信息化,车辆路径问题的客户已经从以前的大型超市、生产基地等更多的落地到如家庭、个人等小而精的客户身上。带时间窗的车辆路径问题(VRPTW)更加贴切现在和未来对于车辆路径问题的描述。VRPTW是VRP问题的一种常见的变体,配送车辆容量有限,每一个客户都拥有一个特定的交付时间窗口所限定,车队运输需要在客户的时间窗内抵达客户所在位置为客户服务,否则将受到一定的惩罚。VRPTW也被认为是NP-hard[1],精确算法求解车辆路径问题仅仅适用于规模较小的问题,而面对现实世界中大型的VRPTW时,启发式和元启发式通常更加适合[2]。模拟退火(SA)、禁忌搜索(TS)[6]、蚁群优化(ACO)[4]、遗传算法(GA)[3]、粒子群优化(PSO)[5]等算法已被证明可有效解决复杂的多目标问题,在求解车辆路径问题上取得了显著的成果。本文以最小化物流配送成本为目标,研究带时间窗的车辆路径问题,建立数学模型;为克服遗传算法收敛速度慢的缺陷,设计并采用了自适应大邻域算法中的破坏算子,通过局部搜索策略,保留较优解。通过实际算例测试表明,改进的遗传算法较简单遗传算法有较好的局部寻优能力,验证了本文算法的有效性。