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