The cost of carrier consistency: Last-mile delivery by vehicle and drone for subscription-based orders

Abstract

We investigate a deterministic last-mile delivery problem in which a firm delivering scheduled orders determines a subset of customers to be prioritized for drone delivery, relegating the rest to vehicle delivery. The vehicle and drone deliver in tandem over a planning horizon. The problem is amenable to a multi-day Traveling Salesman Problem with Drone, with consistency in the assignment of customers to each carrier across all days. We develop a mixed-integer program (MIP) that yields provably optimal solutions for instances having up to 40 customers over a 6-day horizon. We also devise a heuristic underpinned by the MIP to effectively and accurately prioritize customers for drone delivery. A computational study involving instances with up to 150 customers ordering over 6 days shows the matheuristic often matching the results of the proposed MIP, and also reveals a logistical burden of less than 0.5% on average over a solution lacking carrier consistency..

Keywords:

• Last-mile delivery
• drone
• routing
• traveling salesman
• optimization

Disclosure statement

No potential conflict of interest was reported by the authors.

Data availability statement

The data that support the findings of this study are freely available in Gituhub at https://bit.ly/3l2phXV.

Notes

1 All instances as well as best-known solutions available at: https://bit.ly/3l2phXV