Cooperative Truck-Drone Scheduling Approach for Last-Mile Deliveries (Extended Abstract)

Abstract

We present our ongoing work on the cooperation between a truck and drones in a last-mile package delivery scenario. We model this application as an optimization problem where each delivery is associated with a cost (drone's energy), a profit (delivery's priority), and a time interval (launch and rendezvous times from and to the truck). We aim to find an optimal scheduling for drones that maximizes the overall profit subject to the energy constraints while ensuring that the same drone performs deliveries whose time intervals do not intersect. After seeing that this problem is NP-hard, we first devise an optimal Integer Linear Programming (ILP) formulation. We then design an optimal pseudo-polynomial algorithm using dynamic programming and a polynomial-time approximation algorithm that exploits optimal coloring on interval graphs for the single drone case. We also provide an approximation algorithm for the multiple drone case.

Department(s)

Computer Science

Keywords and Phrases

Approximation algorithms; Drones; Dynamic programming

International Standard Serial Number (ISSN)

1613-0073

Document Type

Article - Conference proceedings

Document Version

Citation

File Type

text

Language(s)

English

Rights

© 2024 RWTH Aachen University, All rights reserved.

Publication Date

01 Dec 2021

This document is currently not available here.

Share

 
COinS