skip to main content
US FlagAn official website of the United States government
dot gov icon
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
https lock icon
Secure .gov websites use HTTPS
A lock ( lock ) or https:// means you've safely connected to the .gov website. Share sensitive information only on official, secure websites.

Explore Research Products in the PAR
It may take a few hours for recently added research products to appear in PAR search results.


Title: Efficient Large-Scale Multi-Drone Delivery using Transit Networks
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
Award ID(s):
1830554
PAR ID:
10316894
Author(s) / Creator(s):
; ; ;
Date Published:
Journal Name:
Journal of Artificial Intelligence Research
Volume:
70
ISSN:
1076-9757
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. ; ; (, IEEE Transactions on Intelligent Transportation Systems)
    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
  2. ; ; ; ; ; (, IEEE Transactions on Intelligent Transportation Systems)
    The emerging prevalence of electric vehicles (EVs) in shared mobility services has led to a groundbreaking trend for decarbonizing the shared mobility sector. However, it is still unclear how to maximize the efficiency of EVs to reduce greenhouse gas (GHG) emissions while maintaining high service quality, particularly considering the ongoing transition towards a fully electrified service fleet. In this paper, focusing on meal delivery, we proposed an eco-friendly on-demand meal delivery (ODMD) system to maximize the utilities of EVs to mitigate GHG emissions and maintain low operational cost and delay cost. The main feature of our system is that its fleet consists of electric and gasoline vehicles mirroring the evolving electrification trend in the shared delivery sector. A rolling horizon framework integrated with the adaptive large neighborhood search (RHALNS) algorithm was proposed to efficiently solve the meal order dispatching and routing problem with the mixed fleet. Three delivery policies were explored in the numerical study. Experiment results demonstrated that it is necessary for online meal delivery platforms to actively collect information of electric vehicles and take initiative to employ an eco-friendly delivery policy. 
    more » « less
  3. ; ; (, Transportation Research Record: Journal of the Transportation Research Board)
    Increasing e-commerce activity, competition for shorter delivery times, and innovations in transportation technologies have pushed the industry toward instant delivery logistics. This paper studies a facility location and online demand allocation problem applicable to a logistics company expanding to offer instant delivery service using unmanned aerial vehicles or drones. The problem is decomposed into two stages. During the planning stage, the facilities are located, and product and battery capacity are allocated. During the operational stage, customers place orders dynamically and real-time demand allocation decisions are made. The paper explores a multi-armed bandit framework for maximizing the cumulative reward realized by the logistics company subject to various capacity constraints and compares it with other strategies. The multi-armed bandit framework provides about 7% more rewards than the second-best strategy when tested on standard test instances. A case study based in Portland Metro Area showed that multi-armed bandits can outperform the second-best strategy by more than 20%. 
    more » « less
  4. ; ; ; (, 2021 IEEE International Intelligent Transportation Systems Conference (ITSC))
    Charging infrastructure is the coupling link between power and transportation networks, thus determining charging station siting is necessary for planning of power and transportation systems. While previous works have either optimized for charging station siting given historic travel behavior, or optimized fleet routing and charging given an assumed placement of the stations, this paper introduces a linear program that optimizes for station siting and macroscopic fleet operations in a joint fashion. Given an electricity retail rate and a set of travel demand requests, the optimization minimizes total cost for an autonomous EV fleet comprising of travel costs, station procurement costs, fleet procurement costs, and electricity costs, including demand charges. Specifically, the optimization returns the number of charging plugs for each charging rate (e.g., Level 2, DC fast charging) at each candidate location, as well as the optimal routing and charging of the fleet. From a case-study of an electric vehicle fleet operating in San Francisco, our results show that, albeit with range limitations, small EVs with low procurement costs and high energy efficiencies are the most cost-effective in terms of total ownership costs. Furthermore, the optimal siting of charging stations is more spatially distributed than the current siting of stations, consisting mainly of high-power Level 2 AC stations (16.8 kW) with a small share of DC fast charging stations and no standard 7.7kW Level 2 stations. Optimal siting reduces the total costs, empty vehicle travel, and peak charging load by up to 10%. 
    more » « less
  5. ; ; (, OSA Continuum)
    We investigate the problem of dynamic routing and spectrum assignment for advance reservation anycast requests using a novel algorithm called Delayed Spectrum Allocation (DSA) which delays allocation of resources until immediately before transmission begins. We evaluate the flexible window STSD (demands that specify start-time and duration) to further improve request blocking. Through extensive simulation results, we show that anycast with flexible STSD using DSA approach can significantly reduce blocking probability of anycast and unicast requests compared to traditional Immediate Spectrum Allocation (ISA). The improvement is up to 50 percent in unicast traffic and even higher in anycasting. We also propose balanced routing for anycast algorithms to reduce the blocking. 
    more » « less
  • Citation Formats
  • MLA
  • APA
  • Chicago
  • BibTeX
  • Save / Share this Record
  • Send to Email