Multi-objective optimization model and solution algorithm for emergency material transportation path

doi:10.11772/j.issn.1001-9081.2019020270

Abstract

Abstract:

For the actual background of the shortage of self-owned vehicles of the transporters in the early stage of emergency, the combinatorial optimization problem of hybrid vehicle paths with transportation mode of joint distribution of self-owned vehicles and vehicles rented by third-party was studied. Firstly, with the different interests between demand points and transporters considered, a multi-objective hybrid vehicle routing optimization model with soft time windows was established with the goal of maximizing system satisfaction and minimizing system delivery time and total cost. Secondly, the shortcomings of NSGA-Ⅱ algorithm in solving this kind of problems such as poor convergence and uneven distribution of Pareto frontiers were considered, the heuristic strategy and pheromone positive feedback mechanism of ant colony algorithm were used to generate offspring population, non-dominated sorting strategy model was used to guide the multi-objective optimization process, and the variable neighborhood descent search was introduced to expand the search space. A multi-objective non-dominated sorting ant colony algorithm was proposed to break through the bottleneck of the original algorithm. The example shows that the proposed model can provide reference for decision makers to choose reasonable paths according to different optimization objectives in different situations, and the proposed algorithm shows better performance in solving different scale problems and different distribution type problems.

Key words: emergency logistics, heterogeneous vehicle routing problem, multi-criteria optimization, non-dominated sorting strategy, ant colony algorithm, variable neighborhood search

摘要：

针对应急前期运输商自有车辆不足的实际背景，采用自有车辆和第三方租用车辆共同配送的运输模式，对混合车辆路径的组合优化问题进行研究。首先，考虑需求点和运输商的不同利益诉求，以系统满意度最大、系统配送时间和总成本最小为优化目标，建立带软时间窗的多目标混合车辆路径优化模型。其次，考虑NSGA-Ⅱ算法在求解该类问题时收敛性差和Pareto前沿分布不均匀的缺点，将蚁群算法的启发式策略和信息素正反馈机制用于生成子代种群，非支配排序策略模型用于指导算法的多目标择优过程，并引入变邻域下降搜索以扩大搜索空间，提出求解多目标的非支配排序蚁群算法以突破原有算法瓶颈。算例表明：构建的模型可对决策者在不同的情境下依据不同的优化目标选择合理的路径提供参考，提出的算法在求解不同规模的问题和不同分布类型的问题中均表现出较好的性能。

关键词: 应急物流, 混合车辆路径问题, 多准则优化, 非支配排序策略, 蚁群算法, 变邻域搜索

CLC Number:

TP301.6

LI Zhuo, LI Yinzhen, LI Wenxia. Multi-objective optimization model and solution algorithm for emergency material transportation path[J]. Journal of Computer Applications, 2019, 39(9): 2765-2771.

李卓, 李引珍, 李文霞. 应急物资运输路径多目标优化模型及求解算法[J]. 计算机应用, 2019, 39(9): 2765-2771.

References

[1] 何明珂.应急物流的成本损失无处不在[J].中国物流与采购,2003(23):18-19.(HE M K. The cost loss of emergency logistics is ubiquitous[J]. China Logistics and Purchasing, 2003(23):18-19.)
[2] 王付宇,王涛,叶春明.突发灾害事件情景下应急救援车辆调度问题综述[J].计算机应用研究,2017,34(10):2887-2891.(WANG F Y, WANG T, YE C M. Review of emergency rescue vehicle scheduling problem under sudden disaster[J]. Application Research of Computers, 2017, 34(10):2887-2891.)
[3] 曹琦,曹阳.应急物资配送车辆调度模型与优化综述[J]. 计算机应用, 2018,38(8):2416-2422.(CAO Q, CAO Y. Review of model and optimization of vehicle scheduling for emergency material distribution[J]. Journal of Computer Applications, 2018, 38(8):2416-2422.)
[4] ARDEKANI S A,HOBEIKA A G. Logistics problems in the aftermath of the 1985 Mexico city earth-quake[J]. Transportation Quarterly, 1988, 42(1):107-124.
[5] 郭咏梅,胡大伟,陈翔.改进蚁群算法求解带时间窗的应急物流开环车辆路径问题[J].长安大学学报(自然科学版),2017,37(6):105-112.(GUO Y M, HU D W, CHEN X. Solution of emergency logistics open-loop vehicle routing problem with time window based on improved ant colony algorithm[J]. Journal of Chang'an University (Natural Science Edition), 2017, 37(6):105-112.)
[6] 程碧荣,赵晓波,秦进.考虑供应不足的应急物流车辆路径优化模型及算法[J].计算机应用研究,2016,33(6):1682-1685.(CHENG B R, ZHAO X B, QIN J. Optimization model and algorithm for emergency vehicle route with insufficiency supply[J]. Application Research of Computers, 2016, 33(6):1682-1685.)
[7] WOHLGEMUTH S, OLORUNTOBA R, CLAUSEN U. Dynamic vehicle routing with anticipation in disaster relief[J]. Socio-Economic Planning Sciences, 2012, 46(4):261-271.
[8] NOROUZI N, SADEGH-AMALNICK M, TAVAKKOLI-MOGHADDAM R. Modified particle swarm optimization in a time-dependent vehicle routing problem:minimizing fuel consumption[J]. Optimization Letters, 2016, 11(1):121-134.
[9] 杜苗苗.基于应急物资分类-分批配送的应急车辆路径研究[D]. 北京:北京交通大学,2014:27-36.(DU M M. Emergency vehicle routing problem research based on emergency relief classification-batches distribution[D]. Beijing:Beijing Jiaotong University, 2014:27-36.)
[10] CHANG F, WU J, LEE C, et al. Greedy-search-based multi-objective genetic algorithm for emergency logistics scheduling[J]. Expert Systems with Applications, 2014, 41(6):2947-2956.
[11] ZHANG J, PENG J, XU Z, et al. SDVRP model for emergency logistics and evolutionary heuristic approach[C]//Proceedings of the 2013 International Conference on Automatic Control and Artificial Intelligence. Stevenage, UK:IET, 2013:1809-1812.
[12] 方金城,张岐山. 物流配送车辆路径问题(VRP)算法综述[J]. 沈阳工程学院学报(自然科学版), 2006, 2(4):357-360.(FANG J C, ZHANG Q S. Algorithm review on vehicle routing problem in logistics distribution[J]. Journal of Shenyang Institute of Engineering (Natural Science), 2006, 2(4):357-360.)
[13] da COSTA P R O, MAUCERI S, CARROLL P, et al. A genetic algorithm for a green vehicle routing problem[J]. Electronic Notes in Discrete Mathematics, 2018, 64:65-74.
[14] STODOLA P, MAZAL J, PODHOREC M, et al. Using the ant colony optimization algorithm for the capacitated vehicle routing problem[C]//Proceedings of the 16th International Conference on Mechatronics-Mechatronika. Piscataway, NJ:IEEE, 2014:503-510.
[15] BRANDÃO J. A tabu search algorithm for the heterogeneous fixed fleet vehicle routing problem[J]. Computers and Operations Research, 2011, 38(1):140-151.
[16] GOEL R, MAINI R. A Hybrid of Ant colony and Firefly Algorithms (HAFA) for solving vehicle routing problems[J]. Journal of Computational Science, 2018, 25:28-37.
[17] KAABACHI I, JRIJI D, KRICHEN S. An improved ant colony optimization for green multi-depot vehicle routing problem with time windows[C]//Proceedings of the 18th IEEE/ACIS International Conference on Software Engineering, Artificial Intelligence, Networking and Parallel/Distributed Computing. Piscataway, NJ:IEEE, 2017:339-344.
[18] 万旭,林健良,杨晓伟.改进的最大-最小蚂蚁算法在有时间窗车辆路径问题中的应用[J].计算机集成制造系统,2005,11(4):572-576.(WAN X, LIN J L, YANG X W. Improved MMAS for vehicle routing problem with time window[J]. Computer Integrated Manufacturing Systems, 2005, 11(4):572-576.)
[19] DEB K, PRATAP A, AGARWAL S, et al. A fast and elitist multiobjective genetic algorithm:NSGA-Ⅱ[J]. IEEE Transactions on Evolutionary Computation, 2002, 6(2):182-197.
[20] HASSANZADEH A, RASTI-BARZOKI M. Minimizing total resource consumption and total tardiness penalty in a resource allocation supply chain scheduling and vehicle routing problem[J]. Applied Soft Computing, 2017, 58:307-323.