Transportation Problem
Routing of Carrier-Vehicle Systems with Dedicated Last-Stretch Delivery Vehicle

概要

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's 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.

産業界への展開例・適用分野

Routing, Drones, Carrier-vehicle systems, Approximation algorithms

研究者

氏名	専攻	研究室	役職/学年
Othman Mohd Shahrizan bin	数理工学専攻	Discrete Optimizatio	博士2回生

---