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.