3D Multi-Trajectory and Pick-Up Optimization of UAV for Minimizing Delivery Time With Weight Restriction

Gitae Park, Woongsup Lee, Kisong Lee

Research output: Contribution to journalArticlepeer-review

Abstract

In this study, we explore a three-dimensional trajectory and pick-up design of an unmanned aerial vehicle (UAV) for parcel delivery. In particular, we consider the real-world scenario in which a weight-restricted UAV cannot pick up all parcels within a single route; therefore the parcel delivery must be divided into multiple trajectories while avoiding no-fly zones. We formulate this problem mathematically as the minimization of total delivery time, which jointly optimizes the pick-up indicators, the lengths of the time slots, and the horizontal and vertical trajectories. To address the non-convexity of the formulated mixed-integer nonlinear programming, we employ a successive convex approximation to convert the problem into a convex form concerning optimization variables and utilize a penalty convex-concave procedure to preserve the binary characteristics of the pick-up indicators. Subsequently, we propose an iterative algorithm based on a block decent algorithm to efficiently identify the optimal solution by solving the relaxed convex problem. To address the problem of high computational complexity associated with the optimization-based algorithm, we also present an unsupervised deep learning (DL)-based heuristic algorithm. The simulation results confirm that the proposed schemes achieve considerably shorter delivery times than the baseline schemes in various scenarios. Furthermore, the DL-based scheme requires about 10% longer delivery time than the optimization-based scheme, but it can approximate the UAV strategy with substantially reduced computation time.

Original languageEnglish
Pages (from-to)17562-17573
Number of pages12
JournalIEEE Transactions on Intelligent Transportation Systems
Volume25
Issue number11
DOIs
StatePublished - 2024

Keywords

  • 3D trajectory
  • Unmanned aerial vehicle
  • convex optimization
  • deep learning
  • parcel delivery
  • pick-up design

Fingerprint

Dive into the research topics of '3D Multi-Trajectory and Pick-Up Optimization of UAV for Minimizing Delivery Time With Weight Restriction'. Together they form a unique fingerprint.

Cite this