Branch-price-and-cut for trucks and drones cooperative delivery

Abstract

The truck and drone-based cooperative model of delivery can improve the efficiency of last mile delivery, and has thus increasingly attracted attention in academia and from practitioners. In this study, we examine a vehicle routing problem and apply a cooperative form of delivery involving trucks and drones. We propose a mixed-integer programming model and a branch-price-and-cut-based exact algorithm to address this problem. To reduce the computation time, we design several acceleration strategies, including a combination of dynamic programming and calculus-based approximation for the pricing problem, and various effective inequalities for the restricted master problem. Numerical experiments are conducted to validate the effectiveness and efficiency of the proposed solution.

Keywords:

• Collaborative delivery
• route optimization
• drones
• branch-price-and-cut

Additional information

Funding

This research is supported by the National Natural Science Foundation of China (Grant numbers 72025103, 71831008, 72071173).

Notes on contributors

Lu Zhen

Lu Zhen is a Professor and Dean at the School of Management, Shanghai University, Shanghai, China. His research interests include operations management and optimization; mixed-integer linear programming and algorithms; port operations and maritime transportation; urban logistics and supply chain management. He has served as an associate editor or an editorial board member of five journals such as Transportation Research Part B, Journal of the Operational Research Society, Computers & Operations Research; and he is also a Fellow of the Operational Research Society (U.K.). He has been awarded the National Funds for Distinguished Young Scientists, for Outstanding Young Scientists in China, the Changjiang Young Scholar in China, and etc.

Jiajing Gao

Jiajing Gao is a PhD student at the School of Management, Shanghai University, Shanghai, China. Her research interests include vehicle routing problem’s variants. She has published six papers on SCI international journals.

Zheyi Tan

Zheyi Tan is a Research Engineer at the School of Management, Shanghai University, Shanghai, China. His research interests include warehouse operations management and optimization, vehicle routing problem’s variants. He has published 17 papers in SCI international journals such as European Journal of Operational Research, INFORMS Journal on Applied Analytics.

Shuaian Wang

Shuaian Wang is a Professor at the Faculty of Business, The Hong Kong Polytechnic University, Hong Kong, China. His research interests include big data in shipping, green shipping, shipping operations management, port planning and operations, urban transport network modeling, and logistics and supply chain management. He is an editor-in-chief of Cleaner Logistics and Supply Chain and Communications in Transportation Research, an associate editor of Transportation Research Part E, Flexible Services and Manufacturing Journal, Transportmetrica A, and Transportation Letters, a handle editor of Transportation Research Record, an editorial board editor of Transportation Research Part B, and an editorial board member of Maritime Transport Research.

Roberto Baldacci

Roberto Baldacci is an associate professor at the College of Science and Engineering, Hamad Bin Khalifa University, Doha, Qatar. His research interests include transportation planning, logistics and distribution, and the solution of vehicle routing and scheduling problems over street networks. He is on the editorial board of Operations Research, and he has published more than 50 papers in reputable journals such as Mathematical Programming, Operations Research, Transportation Science, and INFORMS Journal on Computing.