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
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
customerfs 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.