skip to main content


Title: A-VRPD: Automating Drone-Based Last-Mile Delivery Using Self-Driving Cars
Drone-based last-mile delivery is an emerging technology that uses drones loaded onto a truck to deliver parcels to customers. In this paper, we introduce a fully automated system for drone-based last-mile delivery through incorporation of autonomous vehicles (AVs). A novel problem called the autonomous vehicle routing problem with drones (A-VRPD) is defined. A-VRPD is to select AVs from a pool of available AVs based on crowd sourcing, assign selected AVs to customer groups, and schedule routes for selected AVs to optimize the total operational cost. We formulate A-VRPD as a Mixed Integer Linear Program (MILP) and propose an optimization framework to solve the problem. A greedy algorithm is also developed to significantly improve the running time for large-scale delivery scenarios. Extensive simulations were conducted taking into account real-world operational costs for different types of AVs, traveled distances calculated considering the real-time traffic conditions using Google Map API, and varying load capacities of AVs. We evaluated the performance in comparison with two different state-of-the-art solutions: an algorithm designed to address the traditional vehicle routing problem with drones (VRP-D), which involves human-operated trucks working in tandem with drones to deliver parcels, and an algorithm for the two echelon vehicle routing problem (2E-VRP), wherein parcels are first transported to satellite locations and subsequently delivered from those satellites to the customers. The results indicate a substantial increase in profits for both the delivery company and vehicle owners compared with the state-of-the-art algorithms.  more » « less
Award ID(s):
2209829
NSF-PAR ID:
10483486
Author(s) / Creator(s):
; ;
Publisher / Repository:
IEEE
Date Published:
Journal Name:
IEEE Transactions on Intelligent Transportation Systems
Volume:
24
Issue:
9
ISSN:
1524-9050
Page Range / eLocation ID:
9599 to 9612
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. Given the surge in rural logistics services and the disparities between urban and rural delivery services, a compelling necessity emerges to explore innovative drone-based delivery solutions. The challenges inherent in truck-drone delivery due to technological and physical barriers affect service quality for some rural customers, thus magnifying concerns about delivery fairness. To investigated delivery equity, we present a truck-drone cooperative delivery model to analyze rural customers’ accessibility to such innovative delivery technology. This model accommodates rural residents’ delivery preferences while optimizing truck routes. Drones are dispatched from designated trucks to serve customers within their flight distance. Our proposed heuristic algorithm, founded on graph-based truck-drone delivery preferences, solves this intricate problem efficiently. Numerical experiments underscore the efficacy of our approach, highlighting substantial reductions in delivery costs and an impressive 20% increase in drone deliveries on a large-scale network. Through sensitivity analyses exploring drone operational costs and flight distances–affected by government policies and technological advancements–we devise an equity metric that gauges the efficiency and accessibility of rapid rural delivery services under the truck-drone delivery framework. Our research contributes to equity analysis, addressing challenges faced by logistics companies and rural residents. Moreover, it bridges the gap between urban and rural logistics, fostering an inclusive and equitable delivery ecosystem benefiting all customers, regardless of their location. 
    more » « less
  2. We consider a variant of the vehicle routing problem (VRP) where each customer has a unit demand and the goal is to minimize the total cost of routing a fleet of capacitated vehicles from one or multiple depots to visit all customers. We propose two parallel algorithms to efficiently solve the column-generation-based linear-programming relaxation for this VRP. Specifically, we focus on algorithms for the “pricing problem,” which corresponds to the resource-constrained elementary shortest path problem. The first algorithm extends the pulse algorithm for which we derive a new bounding scheme on the maximum load of any route. The second algorithm is based on random coloring from parameterized complexity which can be also combined with other techniques in the literature for improving VRPs, including cutting planes and column enumeration. We conduct numerical studies using VRP benchmarks (with 50–957 nodes) and instances of a medical home care delivery problem using census data in Wayne County, Michigan. Using parallel computing, both pulse and random coloring can significantly improve column generation for solving the linear programming relaxations and we can obtain heuristic integer solutions with small optimality gaps. Combining random coloring with column enumeration, we can obtain improved integer solutions having less than 2% optimality gaps for most VRP benchmark instances and less than 1% optimality gaps for the medical home care delivery instances, both under a 30-minute computational time limit. The use of cutting planes (e.g., robust cuts) can further reduce optimality gaps on some hard instances, without much increase in the run time. Summary of Contribution: The vehicle routing problem (VRP) is a fundamental combinatorial problem, and its variants have been studied extensively in the literature of operations research and computer science. In this paper, we consider general-purpose algorithms for solving VRPs, including the column-generation approach for the linear programming relaxations of the integer programs of VRPs and the column-enumeration approach for seeking improved integer solutions. We revise the pulse algorithm and also propose a random-coloring algorithm that can be used for solving the elementary shortest path problem that formulates the pricing problem in the column-generation approach. We show that the parallel implementation of both algorithms can significantly improve the performance of column generation and the random coloring algorithm can improve the solution time and quality of the VRP integer solutions produced by the column-enumeration approach. We focus on algorithmic design for VRPs and conduct extensive computational tests to demonstrate the performance of various approaches. 
    more » « less
  3. We consider the problem of routing a large fleet of drones to deliver packages simultaneously across broad urban areas. Besides flying directly, drones can use public transit vehicles such as buses and trams as temporary modes of transportation to conserve energy. Adding this capability to our formulation augments effective drone travel range and the space of possible deliveries but also increases problem input size due to the large transit networks. We present a comprehensive algorithmic framework that strives to minimize the maximum time to complete any delivery and addresses the multifaceted computational challenges of our problem through a two-layer approach. First, the upper layer assigns drones to package delivery sequences with an approximately optimal polynomial time allocation algorithm. Then, the lower layer executes the allocation by periodically routing the fleet over the transit network, using efficient, bounded suboptimal multi-agent pathfinding techniques tailored to our setting. We demonstrate the efficiency of our approach on simulations with up to 200 drones, 5000 packages, and transit networks with up to 8000 stops in San Francisco and the Washington DC Metropolitan Area. Our framework computes solutions for most settings within a few seconds on commodity hardware and enables drones to extend their effective range by a factor of nearly four using transit. 
    more » « less
  4. Abstract

    The logistics and delivery industry is undergoing a technology-driven transformation, with robotics, drones, and autonomous vehicles expected to play a key role in meeting the growing challenges of last-mile delivery. To understand the public acceptability of automated parcel delivery options, this U.S. study explores customer preferences for four innovations: autonomous vehicles, aerial drones, sidewalk robots, and bipedal robots. We use an Integrated Nested Choice and Correlated Latent Variable (INCLV) model to reveal substitution effects among automated delivery modes in a sample of U.S. respondents. The study finds that acceptance of automated delivery modes is strongly tied to shipment price and time, underscoring the importance of careful planning and incentives to maximize the trialability of innovative logistics options. Older individuals and those with concerns about package handling exhibit a lower preference for automated modes, while individuals with higher education and technology affinity exhibit greater acceptance. These findings provide valuable insights for logistics companies and retailers looking to introduce automation technologies in their last-mile delivery operations, emphasizing the need to tailor marketing and communication strategies to meet customer preferences. Additionally, providing information about appropriate package handling by automated technologies may alleviate concerns and increase the acceptance of these modes among all customer groups.

     
    more » « less
  5. The advancement of wireless networking has significantly enhanced beamforming capabilities in Autonomous Unmanned Aerial Systems (AUAS). This paper presents a simple and efficient classical algorithm to route a collection of AUAS or drone swarms extending our previous work on AUAS. The algorithm is based on the sparse factorization of frequency Vandermonde matrices that correspond to each drone, and its entries are determined through spatiotemporal data of drones in the AUAS. The algorithm relies on multibeam beamforming, making it suitable for large-scale AUAS networking in wireless communications. We show a reduction in the arithmetic and time complexities of the algorithm through theoretical and numerical results. Finally, we also present an ML-based AUAS routing algorithm using the classical AUAS algorithm and feed-forward neural networks. We compare the beamformed signals of the ML-based AUAS routing algorithm with the ground truth signals to minimize the error between them. The numerical error results show that the ML-based AUAS routing algorithm enhances the accuracy of the routing. This error, along with the numerical and theoretical results for over 100 drones, provides the basis for the scalability of the proposed ML-based AUAS algorithms for large-scale deployments.

     
    more » « less