Research: taking truck-routing and drone-resupply decisions

Online customers expect faster delivery. Last-mile logistics operators normally deliver goods on the same day that they receive them at their local facilities, creating the challenge of planning delivery routes while simultaneously receiving new requests. Once delivery vehicles have started their routes, these operators commonly employ two strategies to manage the arrival of new orders: dispatch a new vehicle to deliver these orders or instruct an en-route vehicle to return to the depot to collect them. Both options incur additional worker time and vehicle travel.

An alternative for faster delivery is using a drone to send newly available orders to delivery vehicles while they are en route, which allows them to continue their distribution without the need to return to the depot periodically. The paper investigates the benefits of this alternative considering a single delivery truck; the traditional strategy (where the truck must return to the depot to pick up newly available orders) versus the drone-resupply strategy What is appealing about this scenario is that it leverages the cost and environmental savings that drones can bring but at the same time eliminates the serious issues of drones interacting directly with customers.

A recent paper by Pina-Pardo, Silva and Smith, introduces the traveling salesman problem with release dates and drone resupply, which consists of finding a minimum time route for a single truck that can receive newly available orders en route via a drone sent from the depot. The researchers developed a Mixed-Integer Linear Program and a solution approach for larger instances based on decomposing the problem into the truck-routing and the drone-resupply decisions.

Numerical experiments show that using drones for resupply can reduce the total delivery time by up to 20%. Additionally, experiments show that the decomposition can rapidly obtain high-quality solutions. For instances of 10 and 15 customers, the decomposition solved the majority to optimality, with a trivial gap. For larger instances, this approach provided lower delivery times than a traditional parcel delivery system using a truck only. Investigations on the effects of drone speed, drone capacity, depot location, constraint addition, and allowing the truck to return to the depot are studied.

Source: Juan C. Pina-Pardo, Daniel F. Silva, Alice E. Smith (2021), The traveling salesman problem with release dates and drone resupply, Computers & Operations Research, Volume 129 2021

Also, check out this publication from Erasmus University/RSM: Optimization Approaches for the Traveling Salesman Problem with Drone – The benefits of combining drones and trucks for deliveries.

Leave a Reply

Your email address will not be published. Required fields are marked *