应急救援物资紧缺的两级配送路径选择研究

doi:10.16381/j.cnki.issn1003-207x.2019.0504

中国管理科学 ›› 2022, Vol. 30 ›› Issue (8): 155-163.doi: 10.16381/j.cnki.issn1003-207x.2019.0504cstr: 32146.14.j.cnki.issn1003-207x.2019.0504

应急救援物资紧缺的两级配送路径选择研究

苏兵^1,3, 周佳其¹, LIN Guohui², 姬浩^1,3, 徐阳¹

1.西安工业大学经济管理学院，陕西西安710021；2.阿尔贝塔大学计算机科学系，加拿大埃德蒙顿T6G 2E8；3.陕西省兵工科技创新发展软科学研究基地，陕西西安710021

收稿日期:2019-04-18 修回日期:2020-01-21 出版日期:2022-08-20 发布日期:2022-08-18
通讯作者: 姬浩(1978-)，男(汉族)，陕西榆林人，西安工业大学经济管理学院，教授，研究方向：交通运输管理，Email:wwwjihao_78@126.com. E-mail:wwwjihao_78@126.com
基金资助:
国家社会科学基金资助项目(20XGL023)

Research on Two-Echelon Vehicle Routing for Scarce Emergency Relief Supply Dispatching

SU Bing^1,3, ZHOU Jia-qi¹, LIN Guo-hui², JI Hao^1,3, XU Yang¹

1. School of Economics and Management，Xi’an Technological University，Xi’an 710021， China；2. Computing Science，University of Alberta，Edmonton T6G 2E8， Canada；3. Research Center for Science and Technology Innovation in Military and Civilian Integration of Shaanxi’s Colleges and Universities, Xi’an 710021, China

Received:2019-04-18 Revised:2020-01-21 Online:2022-08-20 Published:2022-08-18
Contact: 姬浩 E-mail:wwwjihao_78@126.com

摘要/Abstract

摘要： 针对应急救援物资紧缺难以满足所有需求的情形，以单个需求点最大缺货量最小、车辆运输费用最小为双目标，建立从配送中心到分发点再到需求点的两级配送路径选择模型，设计复杂性为O(n3)的近似算法GA进行求解，证明算法近似比的上下界并讨论影响因素，用数值验证算法GA的近似比接近于1，表明算法GA具有较好的性能。最后以雅安灾区配送实例验证模型和算法的有效性。

关键词: 两级配送路径；近似算法；应急救援物资配送；优化

Abstract: Emergency relief supply dispatching is an important issue after the sudden disaster. For the practical case that emergency rescue materials are in short supply and cannot meet the needs of all demand points, a multi-objective Two-Echelon emergency relief supply dispatching vehicle routing model which is the nonlinear programming model is built to find an optimal solution with the aim of minimizing both the maximum shortage of each demand point and total distribution cost. Then, an approximation algorithm GA is designed with the time complexity O(n3), the upper and lower bounder of the approximation ratio is analyzed and the approximation ratio is measured by instances. The approximation ratio which closes to 1 means that the approximation performance of the algorithm is better. Further, the influencing factors of the approximate ratio is analyzed, along with the finding that the more of the number of satellites, the supplies in the depot and the capacity of primary vehicles and secondary vehicles, the less of the number of customers, the better of the algorithm effectiveness. Finally, by comparing the results of the algorithm GA with the results of genetic algorithm, the effectiveness of the algorithm GA is proved.

Key words: Two-Echelon Vehicle Routing; approximation algorithms; emergency relief supply dispatching; optimization

中图分类号:

C931

苏兵,周佳其,LIN Guohui, 等. 应急救援物资紧缺的两级配送路径选择研究[J]. 中国管理科学, 2022, 30(8): 155-163.

SU Bing,ZHOU Jia-qi,LIN Guo-hui, et al. Research on Two-Echelon Vehicle Routing for Scarce Emergency Relief Supply Dispatching[J]. Chinese Journal of Management Science, 2022, 30(8): 155-163.

参考文献

［1］苏兵,张萌,姬浩.应急救援物资紧缺的配送车辆路径选择研究［J］.运筹与管理,2013,22(6):57-64.Su Bing, Zhang Meng, Ji Hao. Study on route selection of distribution vehicle for emergency relief materials in short supply［J］. Operations Research and Management Science,2013,22(6):57-64.
［2］王海军,黎卜豪,刘康康.应急救援下需求分配与网络配流研究［J］.系统工程理论与实践,2015,35(6):1457-1464.Wang Haijun, Li Buhao, Liu Kangkang. Research on demand allocation and network allocation under emergency rescue［J］. Systems Engineering-Theory & Practice,2015,35(6):1457-1464.
［3］ Crainic T, Mancini S, Perboli G, et al. Multi-start heuristics for the two-echelon vehicle routing problem［C］//Proc of the 11th European Conf., Berlin, 2011, Springer Berlin Heidelberg, 2011:179-190.
［4］ Li Hongqi, Zhang Lu, Lv Tan, et al. The two-echelon time-constrained vehicle routing problem in linehaul-delivery systems［J］. Transportation Research Part B, 2016(94):169-188.
［5］ Breunig U, Schmid V, Hartl R F, et al. A large neighbourhood based heuristic for two-echelon routing problems［J］. Computer & Operations Research, 2016(76):208-225.
［6］ Guido P, Roberto T, Daniele V. The two-echelon capacitated vehicle routing problem: Models and math based heuristics［J］. Transportation Science, 2011(3):364-380.
［7］ Philippe G, Michel G, Fabien L, et al. An adaptive large neighborhood search for the two-echelon multiple-trip vehicle routing problem with satellite synchronization［J］. European Journal of Operational Research, 2016(254):80-91.
［8］ Jepsen M, Spoorendonk S, Ropke S. A branch-and-cut algorithm for the symmetric two-echelon capacitated vehicle routing problem［J］. Transportation Science,2013(47): 23-37.
［9］ Roberto B, Aristide M, Roberto R, et al. An exact algorithm for the two-echelon capacitated vehicle routing problem［J］. Operations Research,2013(61):298-314.
［10］ Santos F A, Mateus G R, Da Cunha A S. A branch-and-cut-and-price algorithm for the two-echelon capacitated vehicle routing problem［J］. Transportation Science,2015,49(2):355-368.
［11］陈立伟,唐权华. 基于Memetic算法的两级车辆路径优化［J］.重庆大学学报,2017,40(3): 95-104.Chen Liwei, Tang Quanhua. Two-echelon vehicle routing problem based on memetic algorithm［J］. Journal of Chongqing University,2017,40(3): 95-104.
［12］曾正洋,许维胜,徐志宇,等.城市物流中的开闭混合式两级车辆路径问题［J］.信息与控制,2014,43(6):744-749.Zeng Zhengyang, Xu Weisheng, Xu Zhiyu, et al. Open-closed hybrid two-echelon vehicle routing problem in urban logistics［J］. Information and Control,2014,43(6):744-749.
［13］魏占阳,邬炼,张佳伟,等.基于自适应大规模邻域搜索算法的两级车辆路径问题［J］. 物流科技,2015(8):4-7.Wei Zhanyang, Wu Lian, Zhang Jiawei, et al. Two-echelon vehicle routing problem based on adaptive large-scale neighborhood search algorithm［J］. Logistics Sci-Tech,2015(8):4-7.
［14］曾正洋,许维胜,徐志宇,等.两级车辆路径问题的多起始点变邻域下降算法［J］.同济大学学报(自然科学版),2014,42(10):1530-1535.Zeng Zhengyang, Xu Weisheng, Xu Zhiyu, et al. Multi-starting point variable neighborhood descent algorithm for two-echelon vehicle routing problem［J］. Journal of Tongji University(Natural Science),2014,42(10):1530-1535.
［15］张汉鹏,廖毅,邱菀华.两级车辆路径问题下的应急物资配送策略与绩效［J］.控制与决策, 2015,30(2): 266-270.Zhang Hanpeng, Liao Yi, Qiu Wanhua. Emergency material distribution strategy and performance under two-echelon vehicle routing problem［J］. Control and Decision,2015,30(2): 266-270.
［16］张汉鹏,廖毅,邱菀华.基于情景分析的应急两级车辆路径问题研究［J］.系统科学与数学,2016,36(6):759-769.Zhang Hanpeng, Liao Yi, Qiu Wanhua. Research on emergency two-echelon vehicle routing problem based on scenario analysis［J］. Journal of Systems Science and Mathematical Sciences, 2016,36(6):759-769.
［17］何勇,温洁嫦,黄美华.基于遗传算法的三层大规模应急救援物资配置策略［J］.广东工业大学学报,2016,33(2):37-41.He Yong, Wen Jiechang, Huang Meihua. Three-echelon large-scale emergency relief material allocation strategy based on genetic algorithm［J］. Journal of Guangdong University of Technology, 2016,33(2):37-41.
［18］何新华,胡文发,周溪召.震后应急供应问题与交通路网的协同优化模型［J］.中国管理科学,2017,25(4):104-114.He Xinhua, Hu Wenfa, Zhou Xizhao. Coordination optimization model of emergency supply and transportation network after earthquake［J］. Chinese Journal of Management Science, 2017,25(4):104-114.

[1]	曹端阳, 张旭梅, 但斌. 考虑订单可拆分的第三方共享制造平台产能匹配策略[J]. 中国管理科学, 2025, 33(10): 225-235.
[2]	冯宇, 党耀国, 王俊杰, 杨章程. 基于2-可加Choquet积分的混合信息灰关联决策方法及其应用[J]. 中国管理科学, 2025, 33(9): 189-200.
[3]	戢守峰, 刘红玉, 王丽洁, 戢媛媛. PI环境下考虑保鲜努力的冷链产品生产-库存-运输联合优化模型与求解[J]. 中国管理科学, 2025, 33(8): 166-176.
[4]	毛照昉, 袁锐莹, 张清然. 考虑捆绑销售的在线课程免费试听策略研究[J]. 中国管理科学, 2025, 33(8): 238-249.
[5]	陈晓红, 杨志慧, 胡东滨. 数字化全渠道客户行为：研究热点与知识框架[J]. 中国管理科学, 2025, 33(7): 1-10.
[6]	丁黎黎, 赵忠超, 张凯旋. 感知价值对个人碳账户绿色信贷发展的作用机制研究[J]. 中国管理科学, 2025, 33(5): 344-355.
[7]	谷炜, 刘亚金, Lu Feng Susan, 闫相斌. 人工智能驱动管理决策：应用、感知与偏见[J]. 中国管理科学, 2025, 33(5): 99-112.
[8]	刘嘉, 袁欣, 阮伟乔, 白晋宇. 呼吸道传染病疫情下地铁站行人感染风险控制[J]. 中国管理科学, 2025, 33(5): 236-246.
[9]	卞亦文, 程文超. 平台供应链线下渠道策略与运营模式选择研究[J]. 中国管理科学, 2025, 33(4): 165-174.
[10]	苏兵, 耿雪韵, 姬浩, 徐阳, 郭清娥, 陈光会, 张娟. 需求点服务请求无法预知的应急物资配送路径选择研究[J]. 中国管理科学, 2025, 33(4): 197-203.
[11]	巩在武, 阳佳琦. 考虑灾民心理的多周期应急物资调度不确定规划建模研究[J]. 中国管理科学, 2025, 33(3): 209-222.
[12]	柴一栋, 刘昊鑫, 姜元春, 刘业政. 基于重要性最大化与社区划分的图神经网络推荐系统对抗攻击方法[J]. 中国管理科学, 2025, 33(2): 95-104.
[13]	杨善林, 李霄剑, 莫杭杰, 张强, 唐孝安. 科技战略供应链的基本特征与关键科学问题[J]. 中国管理科学, 2025, 33(1): 1-13.
[14]	陈晓红, 许冠英, 徐雪松, 易国栋, 唐加乐, 刘天朔. 新质生产力视域下管理科学变革：内涵特征、现实挑战与发展路径[J]. 中国管理科学, 2025, 33(1): 14-21.
[15]	胡勋锋, 单而芳, 李登峰. 联盟结构和交流网络限制下合作博弈的Shapley值研究进展[J]. 中国管理科学, 2025, 33(1): 140-152.

应急救援物资紧缺的两级配送路径选择研究

Research on Two-Echelon Vehicle Routing for Scarce Emergency Relief Supply Dispatching

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

Metrics

本文评价

推荐阅读 0