A branch-and-price-and-cut algorithm for the vehicle routing problem with load-dependent drones

Yang Xia, Wenjia Zeng, Canrong Zhang and Hai Yang

Transportation Research Part B: Methodological, 2023, vol. 171, issue C, 80-110

Abstract: In this paper, we consider the vehicle routing problem with load-dependent drones (VRPLD), in which the energy consumption of drones is load-dependent and represented by a nonlinear function. To strengthen the collaboration between trucks and drones, a kind of facility called the docking hub is introduced to extend the service coverage of drones. When a truck visits the hub, a part number of parcels are transferred to the drones departing from the hub to serve the designated customers. We propose a mixed-integer model for the problem, which is nonlinear due to the load-dependent energy consumption. To solve the model, we develop a branch-and-price-and-cut algorithm based on the Danzig–Wolfe decomposition framework, and propose a series of acceleration strategies, including two valid inequalities, to expedite the convergence of the exact algorithm. Computational results on a set of randomly generated instances reflect that the proposed algorithm outperforms Gurobi in terms of both efficiency and effectiveness. Compared with VRPLD, the vehicle routing problem with drones (VRPD) which ignores the load-dependent constraints underestimates the total travel cost by 6.83%. Another drawback of VRPD is that some results may become infeasible when considering the load-dependent energy consumption. The results under VRPLD further reveal that a more accurate description of the energy consumption makes the drones rely more on services from auxiliary facilities. We also conduct sensitivity analysis to draw some managerial insights that setting the hub at a reasonable location can significantly reduce the delivery cost and improve truck and drone cooperation efficiency.

Keywords: Vehicle routing problem with load-dependent drones; Docking hubs; Nonlinear energy function; Branch-and-price-and-cut algorithm (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0191261523000383
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:transb:v:171:y:2023:i:c:p:80-110

Ordering information: This journal article can be ordered from
http://www.elsevier.com/wps/find/supportfaq.cws_home/regional
https://shop.elsevie ... _01_ooc_1&version=01

DOI: 10.1016/j.trb.2023.03.003

Access Statistics for this article

Transportation Research Part B: Methodological is currently edited by Fred Mannering

More articles in Transportation Research Part B: Methodological from Elsevier
Bibliographic data for series maintained by Catherine Liu ().