基于改进多层编码遗传算法的多配送中心车辆路径优化方法研究
Research on Multi-Distribution Center Vehicle Routing Optimization Method Based on Improved Multi-Layer Coding Genetic Algorithm

DOI: 10.12677/OJTT.2019.83027, PP. 222-232

Keywords: VRP问题，遗传算法，多层编码，交通运输，物流，调度，路径优化
VRP Problem, Genetic Algorithm, Multi-Layer Coding, Transportation, Logistics, Dispatching, Path Optimization

Full-Text   Cite this paper   Add to My Lib

Abstract:

为了提高物流运输效率，减少不必要的资源消耗，综合规划一条最有效率的车辆配送货物的路径成为当下物流交通研究的一个热点问题。而其中多配送中心的情况研究尚少。车辆路径优化问题(VRP)是基于旅行商问题(TSP)衍生的，这类问题我们都将其归为非确定性多项式(NP)完全组合优化问题。本文在交通物流车辆路径规划的背景下，首先从VRP问题的概念分析出发，构建了一个数学模型，然后对本文解决该问题的核心算法——遗传算法的理论基础及策略思路进行了一个描述。最后通过加入多因素分析，改进了评价的综合成本，将改进多层编码的遗传算法应用于解决多配送中心VRP问题，并在过程中探索改进。
In order to improve logistics transportation efficiency and reduce unnecessary resource con-sumption, comprehensive planning of a most efficient vehicle distribution route has become a hot issue in the next logistics transportation research. There are still few studies on the situation of multiple distribution centers. The Vehicle Routing Optimization Problem (VRP) is derived from the Traveling Salesman Problem (TSP), which we classify as a non-deterministic polynomial (NP) complete combinatorial optimization problem. In the context of traffic logistics vehicle routing, this paper firstly constructs a mathematical model from the conceptual analysis of VRP problem, and then describes the theoretical basis and strategic thinking of the core algorithm—genetic algorithm to solve this problem. Finally, by adding multi-factor analysis, the comprehensive cost of evaluation is improved, and the improved multi-encoding genetic algorithm is applied to solve the multi-distribution center VRP problem, and the improvement is explored in the process.

References

[1]	薛戈丽, 王建平. 一种基于蚁群算法的物流配送VRP解决方案[J]. 计算机系统应用, 2012, 21(2): 200-203.
[2]	崔雪丽, 马良, 范炳全. 车辆路径问题(VRP)的蚂蚁搜索算法[J]. 系统工程学报, 2004, 19(4): 418-422.
[3]	李向阳. 遗传算法求解VRP问题[J]. 计算机工程与设计, 2004, 25(2): 271-273+276.
[4]	方金城, 张岐山. 物流配送车辆路径问题(VRP)算法综述[J]. 沈阳工程学院学报(自然科学版), 2006, 2(4): 357-360.
[5]	钟石泉. 物流配送车辆路径优化方法研究[D]: [博士学位论文]. 天津: 天津大学, 2007.
[6]	Wazirali, R.A., Alzughaibi, A.D. and Chaczko, Z. (2014) Adaptation of Evolutionary Algorithms for Decision Making on Building Construction Engineering (TSP Problem). International Journal of Electronics and Telecommunications, 60, 113-116. https://doi.org/10.2478/eletel-2014-0015
[7]	Ma, H., Yang, Z., You, P. and Fei, M. (2017) Multi-Objective Biogeography-Based Optimization for Dynamic Economic Emission Load Dispatch Considering Plug-in Electric Vehicles Charging. Energy, 135, 101-111. https://doi.org/10.1016/j.energy.2017.06.102
[8]	贾楠, 吕永波, 付蓬勃, 等. 物流配送问题中VRP的数学模型及其求解算法[J]. 物流技术, 2007, 26(4): 54-56.
[9]	彭其华. 一种车辆路径优化调度算法的研究与仿真[J]. 计算机仿真, 2014, 31(5): 143-146.
[10]	周生伟, 蒋同海, 张荣辉. 改进遗传算法求解VRP问题[J]. 计算机仿真,2013, 30(12): 140-143+157.
[11]	宗辰光, 于培培, 费利鹏, 等. 基于多层编码粒子群——遗传算法融合的AGV调度问题研究[J]. 机电工程技术, 2016, 45(4): 11-14.
[12]	胡飞虎, 马贝龙, 杨丽, 等. 基于改进遗传算法的应急物资配送车辆调度优化问题研究[J]. 计算机应用研究, 2014, 31(10): 2928-2932+2936.
[13]	石彪, 池宏, 祁明亮, 等. 应急物资运输的两阶段车辆调度模型[J]. 系统工程, 2012, 30(7): 105-111.
[14]	饶卫振. 大规模动态车辆路径问题优化方法研究[M]. 北京: 经济科学出版社, 2018.
[15]	孔祥丽. 多影响因素下的导航路网数据路径规划研究[D]: [硕士学位论文]. 武汉: 武汉大学, 2018.
[16]	郎茂祥. 多配送中心车辆调度问题的模型与算法研究[J]. 交通运输系统工程与信息, 2006, 6(5): 65-69.
[17]	王保中, 康立山, 何巍. 基于实数编码遗传算法的多层神经网络BP算法[J]. 武汉大学学报(自然科学版), 1998, 44(3): 26-28.
[18]	谢思聪, 陈小波. 基于多层编码遗传算法的两阶段装配式建筑预制构件生产调度优化[J]. 工程管理学报, 2018, 32(1): 18-22.
[19]	王琛, 游伟, 袁泉, 等. 一种基于多层编码遗传算法的虚拟网络功能调度方法[J]. 信息工程大学学报, 2018, 19(3): 275-281.

Full-Text