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

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

Abstract

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

CLC Number:

TP391

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.

Figures/Tables 8

References 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]	LIU Zi-Long, LI Xiao-Han, TANG Jia-Fu. The Impact of Major Public Health Emergency and Its Prevention and Control Policy on Labor Productivity of Internet Gig Economy Platform: A Case Study of Food Deliveryman [J]. Chinese Journal of Management Science, 2023, 31(3): 81-91.
[2]	LI Tong, CHEN Chou-yong. Plant Growth Simulation Algorithm for Solving Nonlinear Bilevel Programming [J]. Chinese Journal of Management Science, 2012, (4): 160-166.
[3]	ZHONG Zhe-hui, HU Min-jie, FAN Wen-bo, YE Bao-zhong. On the Optimization & Equilibrium of Demand in Supply Chain Based on the Value-adding Mechanism of Information Sharing [J]. Chinese Journal of Management Science, 2010, 18(4): 49-55.
[4]	SHI Xiao-jun, ZHANG Shun-ming, ZHU Fang-fei. A Bilevel Programming Approach to Trade Credit Term Decision and Empirical Evidences [J]. Chinese Journal of Management Science, 2008, 20(6): 112-122.
[5]	ZHANG Hao-zhi, Gao Zi-you. Optimization Approach for Traffic Road Network Design Problem [J]. Chinese Journal of Management Science, 2007, 15(2): 86-91.
[6]	LI Xia, LIU Jia-zhuang, RONG Xiao-xia. Research on High Education Optimal Investment Bilevel Programming Models [J]. Chinese Journal of Management Science, 2004, (5): 102-106.
[7]	SHAN Lian-long, GAO Zi-you . A Stochastic Equilibrium Network Design Model and Its Solution Algorithm for Transit System [J]. Chinese Journal of Management Science, 2001, (1): 41-49.

A Bilevel Heuristic for the Contactless Delivery Problem Coordinated with Trucks and Drones

RichHTML

PDF (PC)

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 8

References 38

Related Articles 7

Metrics

Comments

Recommended 0