卡车与无人机协同的无接触式配送问题的双层启发式算法

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

摘要/Abstract

摘要：

本文提出了一个卡车与无人机协同的无接触式配送问题，该问题适用于新冠疫情期间的城市最后一公里配送。卡车从配送中心出发，访问配送网络中的设施点，无人机从设施点出发，为用户提供无接触式交付服务。问题的目标是两级配送成本的最小化。本文为该问题构建了一个混合整数规划模型，并提出了一个双层规划模型，将该问题分解为一个用户分配主问题和一个容量车辆路径子问题。基于双层规划模型，设计了一种双层启发式算法，以快速求解该问题。最后，生成了两类测试集，共包含144个实例，以测试模型和算法的有效性。结果表明，随着实例中节点数的增加，CPLEX的性能显著下降，而双层启发式算法具有良好的性能。

关键词: 城市物流, 无接触式配送, 双层规划, 双层启发式

Abstract:

In this paper， a contactless delivery problem coordinated with trucks and drones （CDP-TD） is introduced， in which trucks depart from the depot， facilities in the delivery network are visited， and then drones start from the facilities to provide customers with contactless delivery services. The goal of the problem is to minimize the two-level delivery cost. The problem has application in the urban contactless delivery during the pandemic， such as COVID-19. A mixed integer programming model is proposed for the problem， and the problem is reformulated to a bilevel programming model by Benders Decomposition. Inspired by the ideas of the bilevel programming model， a bilevel heuristic is developed to solve the problem. Finally， two classes of problems are generated， including 144 instances， to test the formulation and BH algorithm. The results show that as the number of nodes increases， the performance of the CPLEX deteriorates significantly， whereas the BH has good performance for solving the CDP-TD.

Key words: urban logistics, contactless delivery, bilevel programming, bilevel heuristic

中图分类号:

TP391

蒋丽, 梁昌勇, 臧晓宁. 卡车与无人机协同的无接触式配送问题的双层启发式算法[J]. 中国管理科学, 2024, 32(12): 153-163.

Li Jiang, Changyong Liang, Xiaoning Zang. A Bilevel Heuristic for the Contactless Delivery Problem Coordinated with Trucks and Drones[J]. Chinese Journal of Management Science, 2024, 32(12): 153-163.

图/表 8

图1

图2

图3

图4

表1

表2

图5

图6

参考文献 38

1	搜狐新闻.百度Apollo新石器无人车上岗当送餐员啦［EB/OL］.（2020-02-22）［2022-07-12］..
	News Sohu. Baidu Apollo's Neolix unmanned vehicle is employed as a food delivery man［EB/OL］.（2020-02-22）［2022-07-12］.
2	中国日报.顺丰无人机携手罗湖人民医院开展常态化医疗配送［EB/OL］.（2021-10-28）［2022-07-12］..
	Daily China. SF UAV cooperates with Luohu People's Hospital to carry out normalized medical distribution［EB/OL］.（2021-10-28）［2022-07-12］..
3	IT时报. 无人配送车，行驶在疫情下的上海［EB/OL］.（2022-04-25）［2022-07-12］..
	Times IT. Unmanned delivery vehicles， driving in Shanghai under the epidemic［EB/OL］.（2022-04-25）［2022-07-12］..
4	Reed S， Campbell A M， Thomas B W. The value of autonomous vehicles for last-mile deliveries in urban environments［J］. Management Science， 2021，68（1）：280-299.
5	Murray C C， Chu A G. The flying sidekick traveling salesman problem： Optimization of drone-assisted parcel delivery［J］. Transportation Research Part C： Emerging Technologies， 2015， 54（3）： 86-109.
6	Agatz N， Bouman P， Schmidt M.Optimization approaches for the traveling salesman problem with drone［J］. Transportation Science， 2018， 52（4）： 965-981.
7	Quang Minh H， Deville Y， Quang Dung P， et al. On the min-cost traveling salesman problem with drone［J］. Transportation Research Part C：Emerging Technologies， 2018， 86（3）： 597-621.
8	Poikonen S， Golden B， Wasil E A. A branch-and-bound approach to the traveling salesman problem with a drone［J］. Informs Journal on Computing， 2019， 31（2）：335-346.
9	de Freitas J C， Vaz Penna P H. A variable neighborhood search for flying sidekick traveling salesman problem［J］. International Transactions in Operational Research， 2020， 27（1）： 267-290.
10	Murray C C， Raj R. The multiple flying sidekicks traveling salesman problem： Parcel delivery with multiple drones［J］. Transportation Research Part C： Emerging Technologies， 2020，110（11）： 368-398.
11	Carlsson J G， Song S Y. Coordinated logistics with a truck and a drone［J］. Management Science， 2018， 64（9）： 4052-4069.
12	Wang X， Poikonen S， Golden B. The vehicle routing problem with drones： Several worst-case results［J］. Optimization Letters， 2017， 11（4）： 679-697.
13	Chen C， Edb C， Yuan H C. An adaptive large neighborhood search heuristic for the vehicle routing problem with time windows and delivery robots［J］. European Journal of Operational Research， 2021， 294（3）： 1164-1180.
14	Kitjacharoenchai P， Min B C， Lee S. Two echelon vehicle routing problem with drones in last mile delivery［J］. International Journal of Production Economics， 2020， 225（107598）：1-14.
15	Dorling K， Heinrichs J， Messier G G， et al. Vehicle routing problems for drone delivery［J］. IEEE Transactions on Systems， Man and Cybernetics-Systems， 2017，47（1）： 70-85.
16	Wu G H， Mao N， Luo Q Z， et al. Collaborative truck-drone routing for contactless parcel delivery during the epidemic［J］. IEEE Transactions on Intelligent transportation Systems， 2022，6（1）：1-15.
17	Li H， Wang H， Chen J， et al. Two-echelon vehicle routing problem with time windows and mobile satellites［J］. Transportation Research Part B： Methodological， 2020， 138（4）： 179-201.
18	颜瑞，陈立双，朱晓宁，等. 考虑区域限制的卡车搭载无人机车辆路径问题研究［J］. 中国管理科学， 2022， 30（5）： 144-155.
	Yan R， Chen L S， Zhu X N， et al. Research on vehicle routing problem with truck and drone considering regional restriction［J］. Chinese Journal of Management Science， 2022， 30（5）： 144-155.
19	Mathew N， Smith S L， Waslander S L. Planning paths for package delivery in heterogeneous multirobot teams［J］. IEEE Transactions on Automation Science and Engineering， 2015， 12（4）：1298-1308.
20	Boysen N， Briskorn D， Fedtke S， et al. Drone delivery from trucks： Drone scheduling for given truck routes［J］. Networks， 2018， 72（4）： 506-527.
21	Savuran H， Karakaya M. Efficient route planning for an unmanned air vehicle deployed on a moving carrier［J］. Soft Computing， 2020，20（7）：2905-2920.
22	Poikonen S， Golden B， Wasil E A. A branch-and-bound approach to the traveling salesman problem with a drone［J］. Informs Journal on Computing， 2019， 31（2）： 335-346.
23	Karak A， Abdelghany K. The hybrid vehicle-drone routing problem for pick-up and delivery services［J］. Transportation Research Part C： Emerging Technologies， 2019， 102（3）： 427-449.
24	Poikonen S， Golden B L. Multi-visit drone routing problem［J］. Computers & Operations Research， 2020， 113（1）：1-43.
25	郭兴海，计明军，温都苏，等. “最后一公里”配送的分布式多无人机的任务分配和路径规划［J］. 系统工程理论与实践， 2021，41（4）：946-961.
	Guo X H， Ji M J， Wen D S， et al. Task assignment and path planning for distributed multiple unmanned aerial vehicles in the “last mile”［J］. Systems Engineering -Theory & Practice， 2021， 41（4）： 946-961.
26	Macrina G， Pugliese L D P， Guerriero F， et al. Drone-aided routing： A literature review［J］. Transportation Research Part C： Emerging Technologies， 2020， 120（5）：1-25.
27	Benders J. Partitioning procedures for solving mixed-variables programing problems［J］. Numerische Mathematik， 1962， 4（1）：238-252.
28	Poojari C A， Beasley J E. Improving benders decomposition using a genetic algorithm［J］. European Journal of Operational Research， 2009， 199（1）：89-97.
29	Alfandari L， Ljubi I， de Silva M D. A tailored Benders decomposition approach for last-mile delivery with autonomous robots［J］. European Journal of Operational Research， 2022， 299 （2）：510-525.
30	Simon D. Biogeography-based optimization［J］. IEEE Transactions on Evolutionary Computation， 2008， 12（1）： 702-713.
31	Yogesh C K， Hariharan M， Ngadiran R， et al. A new hybrid PSO assisted biogeography-based optimization for emotion and stress recognition from speech signal［J］. Expert Systems with Applications， 2017， 69（4）： 149-158.
32	Albashish D， Hammouri A I， Braik M， et al. Binary biogeography-based optimization based SVM-RFE for feature selection［J］. Applied Soft Computing， 2021， 101（8）：1-18.
33	Dorigo M， Gambardella L M. Ant colony system： A cooperative learning approach to the traveling salesman problem［J］. IEEE Transactions on Evolutionary Computation， 1997， 1（1）： 53-66.
34	Qin W， Zhuang Z L， Liu Y， et al. A two-stage ant colony algorithm for hybrid flow shop scheduling with lot sizing and calendar constraints in printed circuit board assembly［J］. Computers & Industrial Engineering， 2019， 138（3）：1-12.
35	周鲜成，刘长石，周开军，等. 时间依赖型绿色车辆路径模型及改进蚁群算法［J］.管理科学学报， 2019，22（5）：57-68.
	Zhou X C， Liu C S， Zhou K J， et al. Improved ant colony algorithm and modelling of time dependent green vehicle routing problem［J］. Journal of Management Sciences in China， 2019，22（5）：57-68.
36	Jiang L， Dhiaf M， Dong J， et al. A traveling salesman problem with time windows for the last mile delivery in online shopping［J］. International Journal of Production Research， 2020，58（16）：5077-5088.
37	徐小峰，姜明月，邓忆瑞. 整合逆向物流协同配送动态路径优化问题研究［J］. 管理科学学报， 2021，24（10）：106-126.
	Xu X F， Jiang M Y， Deng Y R. Dynamic vehicle routing problem with simultaneous pickup and delivery in collaborative distribution under demand concurrent［J］. Journal of Management Sciences in China， 2021，24（10）：106-126.
38	Reinelt G. TSPLIB—a traveling salesman problem library［J］. ORSA Journal on Computing， 1991， 3（1）：376-384.

序号	Instance	\|V\|	m	n	CPLEX			BH
序号	Instance	\|V\|	m	n	Cost	Gap%	T.T	Best	Worst	Avg.	Avg.T
A01-03	eil26	26	6	19	1995.0	0.0	0.3	1995.0	1995.0	1995.0	0.4
A04-06		26	12	13	1531.7	0.0	10.5	1531.7	1531.7	1531.7	0.6
A07-09		26	18	7	958.3	0.0	15.0	958.3	958.3	958.3	0.5
A10-12	eil51	51	12	38	3221.7	0.0	766.6	3221.7	3221.7	3221.7	2.3
A13-15		51	25	25	2383.3	2.5	2541.9	2381.7	2381.7	2381.7	2.6
A16-18		51	37	13	1686.7	14.0	3600.0	1686.7	1686.7	1686.7	1.8
A19-21	eil76	76	18	57	4506.7	0.6	2451.6	4503.3	4508.3	4505.3	3.3
A22-24		76	37	38	3070.0	19.5	3600.0	3023.3	3025.0	3024.7	5.7
A25-27		76	56	19	1960.0	27.2	3600.0	1938.3	1940.0	1939.3	3.3
A28-30	eil101	101	25	75	4608.3	4.3	3600.0	4600.0	4614.0	4608.0	5.7
A31-33		101	50	50	3113.3	13.7	3600.0	3086.7	3086.7	3086.7	9.4
A34-36		101	75	25	1783.3	31.2	3600.0	1775.0	1775.0	1775.0	4.8
B01-03	eil26	26	6	19	1758.7	0.0	0.2	1758.7	1758.7	1758.7	0.2
B04-06		26	12	13	1415.0	0.0	0.2	1415.0	1415.0	1415.0	0.4
B07-09		26	18	7	967.0	0.0	11.1	967.0	967.0	967.0	0.4
B10-12	eil51	51	12	38	2692.0	0.0	0.9	2692.0	2692.0	2692.0	2.0
B13-15		51	25	25	2080.7	0.0	18.9	2080.7	2080.7	2080.7	2.6
B16-18		51	37	13	1471.3	0.0	279.8	1471.3	1471.3	1471.3	2.3
B19-21	eil76	76	18	57	3782.0	0.0	597.0	3782.0	3783.3	3782.3	2.7
B22-24		76	37	38	2884.3	22.1	3600.0	2803.7	2803.7	2803.7	4.0
B25-27		76	56	19	1851.3	21.6	3600.0	1811.7	1811.7	1811.7	3.0
B28-30	eil101	101	25	75	3938.3	5.7	3600.0	3937.3	3937.3	3937.3	3.8
B31-33		101	50	50	2817.3	17.3	3600.0	2800.0	2800.0	2800.0	5.4
B34-36		101	75	25	1743.0	29.2	3600.0	1729.3	1729.3	1729.3	3.7

序号	Instance	\|V\|	m	n	CPLEX			BH
序号	Instance	\|V\|	m	n	Cost	Gap%	T.T	Best	Worst	Avg.	Avg.T
A37-39	kroA150	150	37	112	233266.7	12.5	3600.0	230050.0	230188.3	230139.0	15.3
A40-42		150	74	75	175943.3	27.8	3600.0	162510.0	162666.7	162635.3	28.3
A43-45		150	111	38	128406.7	44.0	3600.0	116478.3	116478.3	116478.3	12.5
A46-48	kroB150	150	37	112	237045.0	12.3	3600.0	232153.3	232241.7	232212.0	17.5
A49-51		150	74	75	184176.7	32.4	3600.0	168865.0	169236.7	169044.3	28.4
A52-54		150	111	38	165615.0	58.1	3600.0	118613.3	119238.3	118968.7	14.7
A55-57	kroA200	200	49	150	274605.0	13.7	3600.0	266050.0	266116.7	266103.3	34.4
A58-60		200	99	100	268156.7	46.6	3600.0	183385.0	183691.7	183970.7	47.8
A61-63		200	149	50	235280.0	70.1	3600.0	130548.3	131175.0	130872.7	28.9
A64-66	kroB200	200	49	150	303708.3	23.9	3600.0	265915.0	266101.7	266036.7	27.0
A67-69		200	99	100	308840.0	58.0	3600.0	185508.3	185780.0	185715.7	48.5
A70-72		200	149	50	221796.7	71.6	3600.0	124405.0	124471.7	124433.0	27.4
B37-39	kroA150	150	37	112	218704.0	29.6	3600.0	206096.3	206197.7	206126.3	12.2
B40-42		150	74	75	197567.0	51.8	3600.0	162274.3	162433.0	162324.7	16.6
B43-45		150	111	38	148988.0	68.3	3600.0	117387.0	117456.7	117415.0	13.6
B46-48	kroB150	150	37	112	222178.3	33.0	3600.0	213468.0	214587.7	213947.7	15.1
B49-51		150	74	75	192248.0	54.5	3600.0	172000.3	172217.7	172136.3	17.0
B52-54		150	111	38	144391.3	68.4	3600.0	126701.7	127446.7	127108.3	14.7
B55-57	kroA200	200	49	150	269008.0	36.8	3600.0	237133.7	237288.7	237207.7	27.1
B58-60		200	99	100	236983.3	57.3	3600.0	183246.3	183674.3	183380.7	35.4
B61-63		200	149	50	194447.7	71.2	3600.0	139608.3	140283.7	139946.7	15.0
B64-66	kroB200	200	49	150	280199.3	36.6	3600.0	238463.7	238600.0	238552.7	22.1
B67-69		200	99	100	243478.3	60.4	3600.0	187088.0	187274.0	187228.7	29.2
B70-72		200	149	50	214991.7	75.4	3600.0	136066.3	136346.3	136188.7	16.3

[1]	张莉莉, 杨文文, 罗冠聪. 面向时间优化的“任务-人员”匹配逆最优值方法：以石化设备抢修为例[J]. 中国管理科学, 2023, 31(6): 276-286.
[2]	项寅. 考虑产业布局和用户满意度的氢能汽车加氢网络优化模型[J]. 中国管理科学, 2023, 31(5): 164-175.
[3]	焦媛媛, 闫鑫, 杜军, Roger Jiao. 社交网络情境下基于同侪影响的产品线规划研究[J]. 中国管理科学, 2022, 30(12): 108-119.
[4]	董银红, 郑琪, 李龙. 考虑供应风险的多源应急物资采购双层规划模型[J]. 中国管理科学, 2021, 29(11): 170-178.
[5]	项寅. 不对称信息下反恐阻止网络设计[J]. 中国管理科学, 2020, 28(9): 188-198.
[6]	项寅. 基于双层规划的反恐应急设施选址模型及算法[J]. 中国管理科学, 2019, 27(7): 147-157.
[7]	楼振凯. 应急物流系统LRP的双层规划模型及算法[J]. 中国管理科学, 2017, 25(11): 151-157.
[8]	四兵锋, 杨小宝, 高亮. 基于系统最优的城市公交专用道网络设计模型及算法[J]. 中国管理科学, 2016, 24(6): 106-114.
[9]	赵泉午, 杨茜. 考虑CO₂排放量的城市专业物流中心选址研究[J]. 中国管理科学, 2014, 22(7): 124-130.
[10]	高明霞. 基于双层规划的交通疏散中车辆出发与交通控制综合优化[J]. 中国管理科学, 2014, 22(12): 65-71.
[11]	韩强, 刘正林. 基于总量控制的工业领域能源分配双层规划模型[J]. 中国管理科学, 2013, (2): 168-174.
[12]	杨珺, 刘舒佶, 王玲. 考虑最坏中断损失下的P-中位设施选址问题的模型与算法研究[J]. 中国管理科学, 2011, 19(4): 120-129.
[13]	钟哲辉, 胡敏杰, 范文博, 叶宝忠. 基于信息共享增值机制的供应链需求均衡优化[J]. 中国管理科学, 2010, 18(4): 49-55.
[14]	何波, 孟卫东. 考虑顾客选择行为的逆向物流网络设计问题研究[J]. 中国管理科学, 2009, 17(6): 104-108.
[15]	石晓军, 张顺明, 朱芳菲. 多因素视角下商业信用期限决策的双层规划模型与实证研究[J]. 中国管理科学, 2008, 20(6): 112-122.