A branch-and-cut algorithm for the vehicle routing problem with drones. (February 2021)

• Record Type: Journal Article
• Authors: Tamke, Felix; Buscher, Udo
• Is Part Of: Transportation research. Volume 144(2021)
• Page Start: 174
• Page End: 203
• Publication Date: 2021-02
• Subjects: Vehicle routing problem -- Drones -- Branch-and-cut -- Valid inequalities; Transportation -- Research -- Periodicals; Transportation -- Mathematical models -- Periodicals
• DOI: 10.1016/j.trb.2020.11.011
• Languages: English
• ISSNs: 0191-2615

Abstract

Highlights: We propose a new MILP formulation for the vehicle routing problem with drones. We introduce new valid inequalities and a separation routine for extended subtour elimination constraints. We are able to optimally solve considerably larger instances than currently known approaches. We introduce a relaxation that provides good lower bounds and approximated objective function values at reduced run times. Integrating truck drone tandems into transportation systems can reduce fleet size without slowing down the delivery process. Abstract: Increasing online purchases and higher customer requirements in terms of speed, flexibility, and costs of home deliveries are challenges to every company involved in last mile delivery. Technological advances have paved the way for last mile deliveries by unmanned aerial vehicles (UAV). Yet, the limited range and capacity of UAVs remain a challenge. This makes the possibility of pairing drones with well-established means of transportation highly attractive. However, the optimization problem arising in joint delivery by truck and drone has only recently been considered in the literature. We develop a new mixed integer linear programming (MILP) model for the vehicle routing problem with drones (VRPD) with two different time-oriented objective functions. Additionally, we introduce new valid inequalities based on problem properties to strengthen the linear relaxation. One type of valid inequalities is an extension of the well known subtour elimination constraints. As the number of these constraints grows exponentially with instance size, we provide a separation routine that identifies violated cuts in relaxed solutions to add them efficiently. We therefore derive the first branch-and-cut algorithm for the VRPD. Extensive numerical experiments are performed to demonstrate the competitiveness of our MILP formulation and to show the impact of different combinations of valid inequalities. We optimally solve instances with unrestricted drone ranges with up to 20 nodes and instances with range-limited drones with up to 30 nodes. These are significantly larger instance sizes than the previously known exact approaches are able to handle. In addition, we introduce a relaxation of the VRPD that provides good lower bounds in notable reduced run times. To provide managerial insights, we show that integrating truck-drone tandems into transportation systems can not only lead to improvements regarding the speed of deliveries, but can also be used to reduce the fleet size without slowing down the delivery process and increasing the workload of truck drivers.