.png){kind=icon}
返回
Approximation Algorithms for Drone Delivery Packing Problem
.png){kind=icon}
OA
AI
DOI：10.1145/3571306.3571411.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
Recent advancements in unmanned aerial vehicles, also known as drones, have motivated logistics to use drones for multiple operations. Collaboration between drones and trucks in a last-mile delivery system has numerous benefits and reduces a number of challenges. In this paper, we introduce drone-delivery packing problem (DDP), where we have a set of deliveries and respective customers with their prescribed locations, delivery time intervals, associated cost for deliveries, and a set of drones with identical battery budgets. The objective of the DDP is to find an assignment for all deliveries to the drones by using the minimum number of drones subject to the battery budget and compatibility of the assignment of each drone. We prove that DDP is NP-Hard and formulate the integer linear programming (ILP) formulation for it. We proposed two greedy approximation algorithms for DDP. The first algorithm uses at most 2OPT + (Delta + 1) drones. The second algorithm uses at most 2OPT +omega drones, where OPT is the optimum solution for DDP, omega is the maximum clique size, and Delta is the maximum degree of the interval graph G constructed from the delivery time intervals.
Keyword:
Approximation Algorithm
Drone Delivery
Truck
Last-mile Delivery System
Time complexity