Department of Applied Mathematics & Physics, Kyoto University

Technical Report 2017-001 (April 26, 2017)

Routing of Carrier-Vehicle Systems with Dedicated Last-Stretch Delivery Vehicle
by Mohd Shahrizan bin Othman, Aleksandar Shurbevski, and Hiroshi Nagamochi

pdf File


We examine a routing problem arising when an unmanned aerial vehicle (UAV), or drone, is used in the last-stretch of parcel delivery to an end customer. In the scenario that we study, a delivery truck is dispatched carrying a shipment of parcels to be delivered to customers, and it is required to end its route at a predetermined location, which is not necessarily the same as the starting location. A drone is charged with making the last-stretch delivery of a parcel from the truck to a customerfs doorstep. Given a set of customers to be served, and a set of rendezvous points where the drone can meet with the truck to pick up a parcel, we ask to determine a route for the truck and an assignment for the drone to deliver parcels between rendezvous points and customers, such that all parcels are delivered to end customers in the minimum amount of time. We model this problem as a problem of finding a special type of a path in a graph. We introduce two problem models: the No-Wait Transit Last-Stretch Delivery Problem (NW-TLSDP), and the Transit Last-Stretch Delivery Problem (TLSDP). Both of these graph problems are NP-hard, and we propose polynomial time approximation algorithms for each of the problem settings. We show that in metric graphs, there is a 2.6-approximation algorithm for the NW-TLSDP, and a 2.5-approximation algorithm for the special case when the given terminating location for the truck is the same as the starting one. Further, we show a 1.6-approximation algorithm for the TLSDP in a metric graph, and a 1.5-approximation algorithm for the special case of identical starting and ending locations of the truck.