PaperlayerView exact revision on arXiv

Source-linked AI summary

Efficient Large-Scale Multi-Drone Delivery Using Transit Networks

Shushman Choudhury, Kiril Solovey, Mykel J. Kochenderfer, Marco Pavone

arXiv:1909.11840v5cs.ROcs.AIcs.MA

TL;DR

Urban package delivery faces congestion pressures, while drones have limited range and carrying capacity. The paper combines task allocation with transit-aware multi-drone routing, and simulations report efficient solutions and extended drone range from transit use. Its model leaves delays, uncertainty, and delivery time windows for future work.

  • Problem

    Urban delivery truck traffic contributes to congestion, while drones’ limited range and carrying capacity constrain their use for package delivery.

    Source: §I · p. 1

  • Method

    The framework separates near-optimal task allocation from transit-aware drone routing, using bounded-suboptimal multi-agent pathfinding over a time-dependent transit network.

    Source: B. Approach overview · pp. 2–3, A. MAPF with Transit Networks (MAPF-TN) · p. 4, B. Conflict-Based Search for MAPF-TN · p. 5

  • Results

    Simulations on San Francisco and Washington-area transit networks demonstrate an efficient, scalable framework that lets drones significantly extend their effective range using transit.

    Source: §V · p. 5, §VI · p. 6

  • Takeaways & Limitations

    For a 400 km2 metropolitan area, the longest delivery in a task set is under two hours, and a 12-hour business day can support at least six deliveries per drone.

    Source: A. Further Insights of MAPF-TN Results · p. 12

    The model leaves transit delays and uncertainty, delivery time windows, joint ground-vehicle and drone routing, and depot placement optimization for future work.

    Source: §VI · p. 6

Abstract

from arXiv · show

We consider the problem of controlling a large fleet of drones to deliver packages simultaneously across broad urban areas. To conserve energy, drones hop between public transit vehicles (e.g., buses and trams). We design a comprehensive algorithmic framework that strives to minimize the maximum time to complete any delivery. We address the multifaceted complexity of the problem through a two-layer approach. First, the upper layer assigns drones to package delivery sequences with a near-optimal polynomial-time task allocation algorithm. Then, the lower layer executes the allocation by periodically routing the fleet over the transit network while employing efficient bounded-suboptimal multi-agent pathfinding techniques tailored to our setting. Experiments demonstrate the efficiency of our approach on settings with up to $200$ drones, $5000$ packages, and transit networks with up to $8000$ stops in San Francisco and Washington DC. Our results show that the framework computes solutions typically within a few seconds on commodity hardware, and that drones travel up to $360 \%$ of their flight range with public transit.

I. INTRODUCTION

The paper targets multi-package urban delivery with drones and public transit, seeking to minimize the maximum delivery time while addressing drone range limits and delivery-related congestion. It presents a two-layer framework against gaps in prior work on multi-agent conflicts and routing over time-dependent transit networks.

I. INTRODUCTION

  • Drones’ limited range and carrying capacity contrast with transit networks’ greater coverage and throughput, motivating their combined use for urban deliveries.The paper links delivery truck traffic to congestion and slower operations in dense communities.Source: §I · p. 1

A. Related work

  • Prior work studied single-drone transit use and drone-truck pairing, but did not address multi-agent task allocation and conflicts together.Related transit mobility-on-demand work abstracts away constraints or dynamics needed for autonomous pathfinding over large time-dependent transit networks.Source: A. Related work · pp. 1–2

B. Statement of contributions

  • The framework combines polynomial-time near-optimal task allocation with periodic fleet routing over transit networks to minimize the maximum delivery time.The lower layer uses bounded-suboptimal multi-agent pathfinding techniques tailored to the setting.Source: B. Statement of contributions · p. 2

II. METHODOLOGY

The problem is to route a centralized drone fleet through depots, package locations, and public transit while minimizing makespan and respecting energy and inter-drone constraints. The approach splits allocation from detailed routing, using transit-aware travel-time estimates to connect the layers.

A. Problem Formulation

  • The setting assumes any package can be dispatched from any depot, negligible-time recharging at depots, unlimited depot capacity, and deterministic transit travel times.The formulation accounts for time-varying transit but not travel-time uncertainty.Source: A. Problem Formulation · p. 2

B. Approach overview

  • The full problem is decomposed into two stages because a MILP is unlikely to scale to hundreds of drones, thousands of packages, and large transit networks.Even a simplified version is a multi-depot vehicle-routing problem.Source: B. Approach overview · p. 2
  • The upper layer assigns packages to depots and drones, orders each drone’s deliveries, and minimizes makespan with a near-optimal polynomial-time algorithm.It uses depot and package locations plus estimated travel times between locations.Source: B. Approach overview · p. 2
  • The lower layer plans time- and space-specific routes while enforcing boarding, vehicle-capacity, and battery constraints through bounded-suboptimal MAPF and receding-horizon replanning.It adapts Conflict-Based Search to transit networks for one delivery per drone, then replans as each drone completes a task.Source: B. Approach overview · p. 2
  • The allocation layer uses a transit-aware travel-time surrogate because joint allocation and multi-agent transit routing is infeasible at scale.Direct-flight estimates can be poor for out-of-range targets; the approach precomputes pairwise shortest travel times over a representative transit snapshot, with modest preprocessing.Source: B. Approach overview · p. 3

III. TASK ASSIGNMENT AND PACKAGE ALLOCATION

The task-allocation layer casts package assignment and sequencing as an m minimal visiting paths problem and solves it with MERGESPLITTOURS. The algorithm starts with depot-connecting tours, merges them, then splits the result into drone paths.

III. TASK ASSIGNMENT AND PACKAGE ALLOCATION

  • MERGESPLITTOURS guarantees a near-optimal polynomial-time solution for assigning packages to drones, depots, and delivery sequences while minimizing the maximum agent travel time.The allocation is defined over m paths, each starting and ending at depots, with every package visited by exactly one path.Source: §III · p. 3
  • The m minimal visiting paths problem seeks m depot-to-depot paths covering every package exactly once while minimizing the longest path’s travel time.It is a special asymmetric m-traveling-salesman variant; the general problem is NP-hard, while hardness of this specific instance is not known.Source: §III · p. 3
  • The allocation graph weights directed location pairs by estimated travel time and excludes depot-package edges that cannot be reached within half the allowed flight range.Dispatch constraints can also be represented by excluding edges from the corresponding depot.Source: §III · p. 3
  • MERGESPLITTOURS builds initial package-to-depot tours with the MCT problem, merges tours using depot edges, then splits the final tour into m roughly balanced paths.The split targets path lengths proportional to the final tour length divided by m.Source: §III · p. 3

A. Algorithm Overview

MERGESPLITTOURS builds delivery tours and adapts them into depot-to-depot drone paths. Under stated graph conditions, its makespan is bounded near the optimum, and the algorithm runs in polynomial time.

A. Algorithm Overview

  • MERGESPLITTOURS starts by solving a minimal-connecting tours problem, then merges and adapts the resulting tours into delivery sequences.The MCT solution encodes which allocation-graph edges are used and how many times.Source: A. Algorithm Overview · p. 3

B. Theoretical Guarantees

  • MERGESPLITTOURS assigns every package to exactly one depot-to-depot path, with makespan at most OPT + α + β when the allocation graph is strongly connected and its depot subgraph is a directed clique.The bound adds α + β to OPT for the longest path.Source: B. Theoretical Guarantees · p. 4
  • For m = 5 and k = 200, the approximation ratio is 1.09; for m = 10 and k = 500, it is 1.06.The paper attributes the tightness of the bound when m ≪ |VP| to α and β being small relative to OPT.Source: B. Theoretical Guarantees · p. 4
  • MERGESPLITTOURS is polynomial-time because solving the fractional relaxation of MCT yields its integer optimum, and MCT is a minimum-cost circulation problem.The integrality result follows from total unimodularity of the constraint matrix.Source: B. Theoretical Guarantees · p. 4

IV. MULTI-AGENT PATH FINDING

The routing layer treats each depot–package–depot delivery leg as a task in receding-horizon MAPF over transit networks. It seeks low-travel-time feasible paths while respecting flight-energy limits and shared transit constraints.

IV. MULTI-AGENT PATH FINDING

  • The routing layer splits each allocated delivery sequence into depot–package–depot tasks and replans when a drone completes a task.Each task leaves a depot carrying a package, visits its delivery location, and returns to a depot without exceeding the energy capacity.Source: §IV · p. 4

A. MAPF with Transit Networks (MAPF-TN)

  • MAPF-TN extends standard multi-agent path finding by allowing agents to use one or more transit modes in addition to moving.Its input includes drone tasks and a directed operation graph.Source: A. MAPF with Transit Networks (MAPF-TN) · p. 4
  • The time-expanded operation graph represents transit trips as sequences of time-stamped stop locations and generates flight edges on demand rather than enumerating the dense graph.Edges carry traversal time, energy expenditure, and capacity; transit edges connect consecutive stops on the same trip.Source: A. MAPF with Transit Networks (MAPF-TN) · p. 4
  • Feasible multi-drone paths respect each drone’s flight-distance limit, prohibit simultaneous boarding of the same vehicle at a stop, and keep transit-edge use within capacity.The global objective is to minimize the maximum individual path completion time.Source: A. MAPF with Transit Networks (MAPF-TN) · p. 5

B. Conflict-Based Search for MAPF-TN

The routing method adapts conflict-based search for time-dependent transit networks, where boarding and vehicle-capacity violations create conflicts. Its experiments examine allocation and routing efficiency on large transit-network instances, with some high agent-to-depot settings timed out and excluded.

B. Conflict-Based Search for MAPF-TN

  • CBS resolves boarding and capacity conflicts by adding path constraints for conflicting agents and recomputing their individual paths.ECBS uses bounded-suboptimal focal search at both levels and is reported to achieve orders-of-magnitude speedups over CBS.Source: B. Conflict-Based Search for MAPF-TN · p. 5
  • Focal-MCSP extends constrained shortest-path search to focal search, maintaining non-dominated paths under both traversal-time and flight-distance criteria in an implicit graph.The path-wide distance constraint makes shortest-path search NP-hard, and several constrained-search methods require explicitly enumerated edges.Source: B. Conflict-Based Search for MAPF-TN · p. 5
  • ECBS with Focal-MCSP returns a bounded-suboptimal feasible solution for MAPF-TN.Focal-MCSP yields bounded-suboptimal feasible individual paths, and the multi-agent guarantee follows from the ECBS analysis.Source: B. Conflict-Based Search for MAPF-TN · p. 5

V. EXPERIMENTS AND RESULTS

  • The evaluation focuses on efficiency and scalability rather than a full-problem MILP baseline, which the authors estimate would have about 10^7 variables and exponential constraints.The implementation was tested on a 6-core 3.7 GHz CPU with 16 GiB RAM.Source: §V · p. 5
  • The MAPF-TN experiments use bus networks in San Francisco and Washington, with 4,192 and 7,608 time-expanded transit stops, respectively.The flight-range constraint is 7 km and average drone speed is 25 kph; the study evaluates both allocation and routing layers.Source: §V · p. 5
  • For MAPF-TN settings with m/ℓ = 10, trials exceeding 180 seconds timed out and were discarded.Table III reports times in seconds across depot and agent settings, using ECBS suboptimality factor 1.1.Source: Table III · p. 6

A. Task Allocation

The framework combines polynomial-time task allocation with transit-network routing, and the evaluations report scaling to large fleets and networks. The conclusion identifies operational costs, congestion, externalities, and model extensions as future work.

A. Task Allocation

  • MERGESPLITTOURS has roughly quadratic runtime growth along a Table II row or column and remains reasonable for up to 5,000 deliveries.The authors omit a naive MILP comparison because it would have more than (ℓ·k)^2 variables, besides expensive subtour-elimination constraints.Source: A. Task Allocation · p. 6

B. MAPF with Transit Networks (MAPF-TN)

  • 200 agents and nearly 8,000 vertices were handled; highest average true-delivery makespan was 3380.9 s for SFMTA and 6140.2 s for WMATA.Drones used up to 9 transit options per route and extended their range by up to 3.6x; trials over 3 minutes were discarded, and simultaneous releases made runtimes pessimistic.Source: B. MAPF with Transit Networks (MAPF-TN) · p. 6

VI. CONCLUSION AND FUTURE WORK

  • The framework combines task allocation and transit-network routing, and simulations on two real-world networks show that judicious transit use extends drones’ effective range.The conclusion proposes operational-cost and congestion studies, assessment of noise and disparate impacts, and extensions for transit delays, delivery windows, joint vehicle routing, and depot placement.Source: §VI · p. 6

APPENDIX I TASK ALLOCATION: ADDITIONAL DETAILS AND PROOFS

MERGESPLITTOURS builds a package-covering tour, merges depot-connected tours, and partitions the resulting tour into paths for the agents. Its completeness argument relies on the MCT assignment forming tours and on a bounded number of merging iterations.

APPENDIX I TASK ALLOCATION: ADDITIONAL DETAILS AND PROOFS

  • MCT first constructs a minimum-total-distance collection of tours covering each package exactly once; the algorithm then merges tours and partitions the result into agent paths.The merging routine chooses depot pairs minimizing the sum of their two directed connection costs; each resulting path starts and ends at a depot, and path lengths are proportional to the tour length divided by the number of agents.Source: Appendix I · p. 8

A. Completeness and optimality

  • Under the stated assumptions, each MCT solution can be represented by vertex-disjoint tours because package edges are selected once and depot in-degrees equal out-degrees.The balanced degrees allow an Eulerian tour traversing each selected edge according to its assignment multiplicity.Source: A. Completeness and optimality · p. 8
  • The appendix presents MERGESPLITTOURS-FULL as the procedure that returns paths in which every package is visited exactly once.Its stages use MCT, connected-depot identification, iterative merging, and path construction.Source: A. Completeness and optimality · p. 8
  • The merging loop preserves a collection of tours and runs at most m−1 times, since the initial number of connected depot sets is at most m.The algorithm then obtains the final tour and partitions it into m paths.Source: A. Completeness and optimality · p. 8

B. Computational complexity

The computational bottleneck is solving MCT. The appendix recasts it as a minimum-cost circulation problem so its linear relaxation yields an integer optimum.

B. Computational complexity

  • Figure 3 illustrates allocation-graph construction, MCT’s package-to-depot assignments, and a subsequent merge of depot clusters.Its three panels show how the tour-merging process follows the MCT assignment.Source: Figure 3 · p. 9
  • MCT is the identified computational bottleneck, and its linear relaxation yields an integer optimum after transformation to minimum-cost circulation.The argument invokes total unimodularity when edge capacities are integral.Source: B. Computational complexity · p. 9
  • The circulation transformation adds a copy p′ for each package and requires the edge (p, p′) to carry one unit.The modified graph retains depot-to-package and package-to-depot edges from the allocation graph.Source: B. Computational complexity · p. 9

APPENDIX II MAPF-TN: ADDITIONAL DETAILS

The appendix details MAPF-TN conflict handling and search speedups, including preprocessing that supplies admissible heuristics for routing over transit networks. It also notes limits from conflict-resolution cost and timetable assumptions.

A. Capacity Conflicts in (E)CBS

  • For a transit edge with p > C(e) > 1 drones, Enhanced CBS generates every set of p − C(e) constraints to preserve bounded suboptimality.Each set restricts a different subset of p − C(e) drones from using that edge.Source: A. Capacity Conflicts in (E)CBS · p. 9
  • Conflict resolution is a significant MAPF-TN bottleneck, and enumerating all constraint subsets may degrade performance in pathological scenarios.The authors identify principled analysis of enumeration and suboptimality as future work.Source: A. Capacity Conflicts in (E)CBS · p. 9

B. Speedup Techniques

  • The authors devised two low-level search speedups that maintain bounded suboptimality, while noting that these techniques are not exhaustive.MAPF-TN combines the NP-hardness of multi-agent path finding with energy constraints and large, dense graphs.Source: B. Speedup Techniques · p. 9

1) Preprocessing Public Transit Networks:

  • Preprocessing builds a complete trip metagraph and uses Floyd–Warshall to compute least-flight-distance costs between trips and depot or package locations.Trip-to-trip costs use the shortest drone-flight distance feasible within the time between their stops; depot/package pairs use direct-flight distance.Source: 1) Preprocessing Public Transit Networks · p. 10
  • The distance heuristic hN uses precomputed trip-metagraph costs as a lower bound on flight distance to a depot or package goal.The elapsed-time heuristic uses direct-flight time as a lower bound when average drone speed exceeds average transit speed.Source: 1) Preprocessing Public Transit Networks · pp. 9–10
  • The heuristics ignore timetable delays and disruptions, assuming travel times between locations do not vary greatly throughout the day.Handling dynamic networks and timetable delays is outside the work’s scope.Source: 1) Preprocessing Public Transit Networks · p. 10

2) Pruning Focal-MCSP search space:

Focal-MCSP prunes transit-stop connections by retaining only non-dominated options in time and flight distance. This reduces neighbor generation while preserving bounded suboptimality.

2) Pruning Focal-MCSP search space:

  • The implicit operation graph saves memory by storing vertices only, but requires outgoing edges to be computed during search.Pruning candidate neighbors helps address this computation cost without sacrificing bounded suboptimality.Source: 2) Pruning Focal-MCSP search space · p. 10
  • Only non-dominated transit stops in time difference and flight distance need to be added as candidate connections, preserving Focal-MCSP’s bounded suboptimality.A stop is non-dominated when no alternative is both earlier and closer.Source: 2) Pruning Focal-MCSP search space · p. 10
  • Pruning a consecutive stop dominated on both measures does not change the solution, because the route through the earlier, closer stop dominates the direct connection.The two partial paths reach the same time-stamped stop, but the path through the earlier stop accumulates less flight distance.Source: 2) Pruning Focal-MCSP search space · pp. 10–11
  • Kung’s algorithm finds non-dominated transit vertices in O(n log n) time, while the existing time order lets this implementation add neighbors in O(n) time.The general bound includes sorting; the implementation’s input is already sorted by traversal time.Source: 2) Pruning Focal-MCSP search space · p. 11

APPENDIX III SURROGATE TRAVEL TIME ESTIMATE

The surrogate travel-time estimate uses preprocessing over representative locations and transit trips to support upper-layer task allocation. The appendix also outlines further MAPF-TN, replanning, and surrogate-estimate results.

APPENDIX III SURROGATE TRAVEL TIME ESTIMATE

  • Preprocessing samples representative locations across the operating area, then stores transit-network travel-time estimates between every pair for a representative time window.The locations form a Voronoi decomposition of the area.Source: APPENDIX III SURROGATE TRAVEL TIME… · p. 11
  • At runtime, MERGESPLITTOURS looks up the precomputed estimate between the representative sites nearest each depot or package location.If both locations share a cell, the method instead uses their direct-flight time.Source: APPENDIX III SURROGATE TRAVEL TIME… · pp. 11–12
  • The estimate uses 100 representative points for San Francisco and 150 for Washington DC; more points typically improve coverage and estimate quality.The authors note that local knowledge of the transit network and travel times may yield a higher-quality estimate than their domain-agnostic approach.Source: APPENDIX III SURROGATE TRAVEL TIME… · p. 12

APPENDIX IV FURTHER RESULTS

  • Further results examine MAPF-TN behavior, compare two replanning strategies, and quantify the effect of two surrogate travel-time estimates.Source: APPENDIX IV FURTHER RESULTS · p. 12

A. Further Insights of MAPF-TN Results

The results examine MAPF-TN scalability and delivery times, compare two replanning strategies, and show that the better travel-time surrogate depends on the setting.

A. Further Insights of MAPF-TN Results

  • Depot placement can significantly affect computation time and scalability, making it an important future-work question given depot construction costs.Each low-level search concatenates two Focal-MCSP searches, so the effective agent count is 2m.Source: A. Further Insights of MAPF-TN Results · p. 12
  • Washington DC’s larger area, larger transit network, and sparser suburban bus service increase transit use and conflicts, while larger-graph searches also take longer without conflicts.Source: A. Further Insights of MAPF-TN Results · p. 12
  • For a 400 km2 metropolitan area, the longest delivery is under 2 hours; a representative window repeated through a 12-hour day implies at least six deliveries per drone.Source: A. Further Insights of MAPF-TN Results · p. 12

B. Replanning Strategies

  • Receding-horizon replanning reroutes a drone after its current task; Replan-1 computes one new path, while Replan-m recomputes paths for all drones.Replan-m is optimal among replanning strategies but most computationally expensive; Replan-1 accounts for the other drones’ paths as boarding and capacity constraints.Source: B. Replanning Strategies · p. 12
  • Replan-1 achieves similar solution quality to Replan-m at fairly lower computational cost across the tested scenarios.The comparison covers a subset of San Francisco depot-agent scenarios and averages 20 trials per setting.Source: Table IV · p. 12, B. Replanning Strategies · p. 13
  • Replan-1 can have a larger quality gap when unfinished paths conflict with the new path and resolving conflicts would prioritize the newly finished drone; this condition did not occur in trials with l = 20.Source: B. Replanning Strategies · p. 13

C. Comparison of Surrogate Estimates

  • The better surrogate depends on the setting: preprocessed transit estimates perform better with fewer depots or frequent transit use, while direct flight estimates often yield lower makespan with at least 10 San Francisco depots.In almost all Washington settings except the first, Preprocessed is strictly better than Direct Flight for both computation time and makespan.Source: C. Comparison of Surrogate Estimates · p. 13
Loading 1909.11840v5…