大连海事大学 a. 交通运输工程学院； b. 战略管理与系统规划研究所， 辽宁 大连 116026
出版日期:2019-08-28发布日期:2019-09-10作者简介:范厚明(1962-)，男，山东省蓬莱市人，教授，博士生导师，主要从事交通运输规划与管理等研究.电话(Tel.)：0411-84725868；E-mail：fhm468@163.com.基金资助:国家自然科学基金资助项目(61473053)，辽宁省社会科学规划基金重点项目(L16AGL004)，大连市科学技术计划项目(2015D12ZC181)Hybrid Genetic Algorithm for Solving Multi-Depot Joint Distribution Routing Problem
FAN Houming a,b,XU Zhenlin a,b,LI Yang a,LIU Wenqi a,GENG Jing aa. College of Transportation Engineering； b. Institute of Strategy Management and System Planning, Dalian Maritime University, Dalian 116026, Liaoning, China
Online:2019-08-28Published:2019-09-10摘要/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
PDF全文下载地址:
点我下载PDF
