混合遗传算法求解多中心联合配送路径问题

doi:10.16183/j.cnki.jsjtu.2019.08.016

摘要/Abstract

摘要： 针对传统遗传算法在求解多中心车辆路径问题时存在：传统编解码方式引起的染色体长度不固定导致计算效率低下和易产生不可行解；扰动过程中双亲遗传算子计算效率较低；难以平衡不同进化时期种群中精英比例与种群多样性间、搜索深度与搜索广度间的关系等问题，本文设计一种混合遗传算法，在编解码方式上将配送网络信息分开表达，提高计算效率；在选择操作上引入平衡精英比例与种群多样性的控制参数；此外，还提出一种自适应搜索范围策略，以有效平衡搜索深度与搜索广度间的关系.通过实验例证和对比分析，验证了算法的有效性.研究成果为求解多中心联合配送车辆路径问题提供一种新思路，也可为相关的物流配送决策提供指导.

关键词: 联合配送；多中心车辆路径问题；混合遗传算法；自适应搜索范围策略

Abstract: There are problems of traditional genetic algorithm in solving multi-depot vehicle routing problem. First, variable chromosome length produced by conventional coding techniques leads to low computation efficiency and easily produces infeasible solutions. Second, parental genetic operators have less efficient during perturbation. And it is difficult to balance the relationship between elite proportion and population diversity, search depth and search breadth in different evolutionary populations. This paper designs a hybrid genetic algorithm to solve the problem, and the distribution network information is separately expressed in the encoding and decoding method to improve the computational efficiency. The control parameters of balanced elite ratio and population diversity are introduced in the selection operation. In addition, an adaptive search range strategy is proposed to effectively balance the relationship in both search depth and breadth. Through experimental results and comparative analysis, the proposed algorithm is verified. The research results provide a new method to solve the multi-depot vehicle routing problem and can also provide guidance for related logistics distribution decisions.

Key words: joint distribution; multi-depot vehicle routing problem; hybrid genetic algorithm; adaptive search range strategy

中图分类号:

TP 18

范厚明，徐振林，李阳，刘文琪，耿静. 混合遗传算法求解多中心联合配送路径问题[J]. 上海交通大学学报, 2019, 53(8): 1000-1009.

FAN Houming,XU Zhenlin,LI Yang,LIU Wenqi,GENG Jing. Hybrid Genetic Algorithm for Solving Multi-Depot Joint Distribution Routing Problem[J]. Journal of Shanghai Jiaotong University, 2019, 53(8): 1000-1009.

参考文献

［1］ALLAHYARI S, SALARI M, VIGO D. A hybrid metaheuristic algorithm for the multi-depot covering tour vehicle routing problem［J］. European Journal of Operational Research, 2015, 242(3): 756-768. ［2］DE OLIVEIRA F B, ENAYATIFAR R, SADAEI H J, et al. A cooperative coevolutionary algorithm for the multi-depot vehicle routing problem［J］. Expert Systems with Applications, 2016, 43: 117-130. ［3］JABIR E, PANICKER V V, SRIDHARAN R. Design and development of a hybrid ant colony-variable neighbourhood search algorithm for a multi-depot green vehicle routing problem［J］. Transportation Research Part D: Transport and Environment, 2017, 57: 422-457. ［4］ZHOU L, BALDACCI R, VIGO D, et al. A multi-depot two-echelon vehicle routing problem with deli-very options arising in the last mile distribution［J］. European Journal of Operational Research, 2018, 265(2): 765-778. ［5］SALHI S, IMRAN A, WASSAN N A. The multi-depot vehicle routing problem with heterogeneous vehicle fleet: Formulation and a variable neighborhood search implementation［J］. Computers & Operations Research, 2014, 52: 315-325. ［6］葛显龙, 许茂增, 王伟鑫. 多车型车辆路径问题的量子遗传算法研究［J］. 中国管理科学, 2013, 21(1): 125-133. GE Xianlong, XU Maozeng, WANG Weixin. Study on multi-types vehicle routing problem and its quantum genetic algorithm［J］. Chinese Journal of Management Science, 2013, 21(1): 125-133. ［7］MANCINI S. A real-life multi depot multi period vehicle routing problem with a heterogeneous fleet: Formulation and adaptive large neighborhood search based matheuristic［J］. Transportation Research Part C Emerging Technologies, 2016, 70: 100-112. ［8］刘家利, 马祖军. 存在车辆租赁及共享且有时间窗的多配送中心开环VRP［J］. 系统工程理论与实践, 2013, 33(3): 666-675. LIU Jiali, MA Zujun. Multi-depot open vehicle routing problem with time windows based on vehicle leasing and sharing［J］. Systems Engineering: Theory & Practice, 2013, 33(3): 666-675. ［9］LI J, PARDALOS P M, SUN H, et al. Iterated local search embedded adaptive neighborhood selection approach for the multi-depot vehicle routing problem with simultaneous deliveries and pickups［J］. Expert Systems with Applications, 2015, 42(7): 3551-3561. ［10］KACHITVICHYANUKUL V, SOMBUNTHAM P, KUNNAPAPDEELERT S.Two solution representations for solving multi-depot vehicle routing problem with multiple pickup and delivery requests via PSO［J］. Computers & Industrial Engineering, 2015, 89: 125-136. ［11］郎茂祥. 多配送中心车辆调度问题的模型与算法研究［J］. 交通运输系统工程与信息, 2006, 6(5): 65-69. LANG Maoxiang. Study on the model and algorithm for multi-depot vehicle scheduling problem［J］. Journal of Transportation Systems Engineering and Information Technology, 2006, 6(5): 65-69. ［12］殷脂, 叶春明. 多配送中心物流配送车辆调度问题的分层算法模型［J］. 系统管理学报, 2014, 23(4): 602-606. YIN Zhi, YE Chunming. Study on the hierarchical model for multi-depot logistic vehicle scheduling problem［J］. Journal of Systems & Management, 2014, 23(4): 602-606. ［13］葛显龙, 许茂增, 王伟鑫. 基于联合配送的城市物流配送路径优化［J］. 控制与决策, 2016, 31(3): 503-512. GE Xianlong, XU Maozeng, WANG Weixin. Route optimization of urban logistics in joint distribution［J］. Control and Decision, 2016, 31(3): 503-512. ［14］VILLEGAS J G, PRINS C, PRODHON C, et al. GRASP/VND and multi-start evolutionary local search for the single truck and trailer routing problem with satellite depots［J］. Engineering Applications of Artificial Intelligence, 2010, 23(5): 780-794. ［15］THANGIAH S R, SALHI S. Genetic clustering: An adaptive heuristic for the multidepot vehicle routing problem［J］. Applied Artificial Intelligence, 2001, 15(4): 361-383. ［16］KARAKATI S, PODGORELEC V. A survey of genetic algorithms for solving multi depot vehicle routing problem［J］. Applied Soft Computing, 2015, 27: 519-532. ［17］STODOLA P, MAZAL J, PODHOREC M. Improving the ant colony optimization algorithm for the multi-depot vehicle routing problem and its application［C］//1st International Workshop on Modelling and Simulation for Autonomous Systems. Rome, Italy: Springer, 2014: 376-385. ［18］TLILI T, KRICHEN S, DRIRA G, et al. On solving the multi-depot vehicle routing problem［C］//3rd International Conference on Advanced Computing, Networking and Informatics. India: Springer, 2016: 103-108.

[1]	李少远, 殷翔. 智能体自我博弈学习是否存在性能极限?[J]. 上海交通大学学报, 2021, 55(Sup.1): 3-4.
[2]	刘敏，张英堂，李志宁，范红波. 基于增量稀疏核极限学习机的柴油机故障在线诊断[J]. 上海交通大学学报（自然版）, 2019, 53(2): 217-224.
[3]	毕晓君，胡菘益. 基于混合引导策略的高精度萤火虫优化粒子滤波算法[J]. 上海交通大学学报（自然版）, 2019, 53(2): 232-238.
[4]	杜振鑫1,2，韩德志2，刘广钟2，贾建鑫2. 一种逐步加强开采的人工蜂群算法[J]. 上海交通大学学报（自然版）, 2018, 52(1): 96-102.
[5]	刘凯a，张立民b，周立军a. 随机受限玻尔兹曼机组设计[J]. 上海交通大学学报（自然版）, 2017, 51(10): 1235-1240.
[6]	刘昊，丁进良，杨翠娥，柴天佑. 基于择优学习策略的差分进化算法[J]. 上海交通大学学报（自然版）, 2017, 51(6): 704-708.
[7]	卢诚波，梅颖. 前馈网络的一种高精度鲁棒在线贯序学习算法[J]. 上海交通大学学报（自然版）, 2015, 49(08): 1137-1143.
[8]	王萍，王迪，冯伟. 基于流形正则化的在线半监督极限学习机[J]. 上海交通大学学报（自然版）, 2015, 49(08): 1153-1158.
[9]	鲍治国，万金梁，马西锋. 基于遗传算法具有容错能力的图像滤波器优化设计[J]. 上海交通大学学报（自然版）, 2015, 49(08): 1181-1185.
[10]	纪良波. 基于小波神经网络熔丝堆积三维打印精度预测模型[J]. 上海交通大学学报（自然版）, 2015, 49(03): 375-378.
[11]	王肖霞，杨风暴，吉琳娜，蔺素珍，史冬梅. 基于柔性相似度量和可能性歪度的尾矿坝风险评估方法[J]. 上海交通大学学报（自然版）, 2014, 48(10): 1440-1445.
[12]	杨刚1, 2,乔俊飞1. 跨越-侧抑制神经网络分析及其应用[J]. 上海交通大学学报（自然版）, 2014, 48(07): 965-970.
[13]	杨静1，孔斌1，王斌2. 基于启发式退火拓扑择优机制的稀疏联想记忆实现[J]. 上海交通大学学报（自然版）, 2013, 47(07): 1009-1014.
[14]	王莉1,2，周献中1，李华雄1. 模糊决策粗糙集模型及其属性约简[J]. 上海交通大学学报（自然版）, 2013, 47(07): 1032-1035.
[15]	吴文通1，李元祥1，韦邦合2，郑思龙1. 局部测地距离估计的增量等距特征映射算法[J]. 上海交通大学学报（自然版）, 2013, 47(07): 1082-1087.