应急物资运输路径多目标优化模型及求解算法

doi:10.11772/j.issn.1001-9081.2019020270

计算机应用 ›› 2019, Vol. 39 ›› Issue (9): 2765-2771.DOI: 10.11772/j.issn.1001-9081.2019020270

• 应用前沿、交叉与综合 • 上一篇下一篇

应急物资运输路径多目标优化模型及求解算法

李卓, 李引珍, 李文霞

兰州交通大学交通运输学院, 兰州 730070

收稿日期:2019-02-18 修回日期:2019-04-07 出版日期:2019-09-10 发布日期:2019-05-14
通讯作者: 李引珍
作者简介:李卓(1993-),男,甘肃天水人,硕士研究生,主要研究方向:交通运输规划与管理、网络优化;李引珍(1963-),男,甘肃天水人,教授,博士,主要研究方向:运输系统分析与决策;李文霞(1993-),女,甘肃兰州人,硕士研究生,主要研究方向:交通运输规划与管理、网络优化。

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

LI Zhuo, LI Yinzhen, LI Wenxia

School of Traffic and Transportation, Lanzhou Jiaotong University, Lanzhou Gansu 730070, China

Received:2019-02-18 Revised:2019-04-07 Online:2019-09-10 Published:2019-05-14

摘要/Abstract

摘要：

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

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

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

中图分类号:

TP301.6

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

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.

参考文献

[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.

应急物资运输路径多目标优化模型及求解算法

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

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	龚英, 何彦婷, 曹策俊. 面向重大公共卫生风险治理的应急物流协同演化仿真[J]. 计算机应用, 2021, 41(9): 2754-2760.
[2]	杨玮, 李然, 张堃. 基于变邻域模拟退火算法的多自动导引车任务分配优化[J]. 计算机应用, 2021, 41(10): 3056-3062.
[3]	段宇君, 王耀力, 常青, 刘鑫. 改进型蚁群算法融合混沌优化的pSPIEL算法的无线传感器布局优化[J]. 计算机应用, 2020, 40(3): 793-798.
[4]	屈立成, 吕娇, 赵明, 王海飞, 屈艺华. 基于三维时空地图和运动分解的多机器人路径规划算法[J]. 计算机应用, 2020, 40(12): 3499-3507.
[5]	刘育良, 陈淮莉. 负载影响下纯电动汽车配送路径规划及充电策略[J]. 计算机应用, 2020, 40(10): 2831-2837.
[6]	王东先, 孟学雷, 乔俊, 汤霖, 焦志臻. 基于改进蚁群算法的铁路乘务交路计划的编制[J]. 计算机应用, 2019, 39(9): 2749-2756.
[7]	郑延斌, 王林林, 席鹏雪, 樊文鑫, 韩梦云. 基于蚁群算法及博弈论的多Agent路径规划算法[J]. 计算机应用, 2019, 39(3): 681-687.
[8]	郭良敏, 朱莹, 孙丽萍. 障碍空间中基于并行蚁群算法的k近邻查询[J]. 计算机应用, 2019, 39(3): 790-795.
[9]	杨继东, 孙兆琦, 王飞龙. 基于视觉抓取的并联桁架机器人最优路径控制[J]. 计算机应用, 2019, 39(3): 913-917.
[10]	王东先, 孟学雷, 何国强, 孙慧萍, 王喜栋. 基于改进蚁群算法的铁路乘务排班计划编制[J]. 计算机应用, 2019, 39(12): 3678-3684.
[11]	陈林烽, 齐学梅, 陈俊文, 黄琤, 陈付龙. 批量流水调度问题的量子候鸟协同优化算法[J]. 计算机应用, 2019, 39(11): 3250-3256.
[12]	魏亚茹, 朱瑾. 自动化码头双场桥调度与集装箱存储选位建模[J]. 计算机应用, 2018, 38(4): 1189-1194.
[13]	郭羽含, 伊鹏. 长期车辆合乘问题的复合变邻域搜索算法[J]. 计算机应用, 2018, 38(10): 3036-3041.
[14]	王超, 朱明, 王敏. 基于管制员认知负荷和改进蚁群算法的扇区动态通行能力评估[J]. 计算机应用, 2018, 38(1): 277-283.
[15]	许凯波, 鲁海燕, 程毕芸, 黄洋. 求解TSP的改进信息素二次更新与局部优化蚁群算法[J]. 计算机应用, 2017, 37(6): 1686-1691.