AI Research Portal

This paper introduces the Multi-Agent Flying Sidekick Traveling Salesman Problem (MA-FSTSP), an extension of FSTSP that models multiple trucks, each with multiple drones, operating over real road networks. The core idea is a novel three-phase algorithm: first, customers are partitioned into truck groups using a set-based distance heuristic; second, initial truck routes are determined via a Set TSP formulation; and third, drone deployment patterns are optimized using dynamic programming. The main empirical claim is that this method achieves over 30% cost reduction compared to existing approaches and scales effectively to problems with up to 150 customers within a 20-minute computational time-bound on real-world road networks.

The paper addresses several bottlenecks in existing truck-drone delivery systems:

Simplified operational environments: Previous models like FSTSP assume a single truck-drone pair operating on a fully connected graph, which does not capture real-world complexities.
: Early models restricted drones to taking actions only at customer nodes, simplifying path-finding.

Development of a Mixed-Integer Linear Programming (MILP) formulation for the MA-FSTSP.
Proposal of a novel 3-phase method that achieves state-of-the-art performance and scalability.
Introduction of a set-based distance heuristic in the first phase for efficient customer assignment to truck groups.
Introduction of Set TSP in the second phase to approximate feasible drone operations and determine customer serving sequences.
Implementation of simultaneous truck-drone route planning in the third phase using dynamic programming.
Validation of the approach through experiments on real-world road networks, demonstrating over 30% cost reduction compared to baselines and significant scalability to large instances.

The proposed solution for MA-FSTSP is a novel three-phase algorithm.

Phase 1: Set-based partition algorithms This phase decomposes the problem by assigning customers to truck groups using a set-based heuristic.

For each customer c ∈ C, a set of neighbor vertices Sc(θ) is defined as: Sc(θ) := {n ∈ V(G) : d(n, c) < θ}, where θ is a distance parameter and d(n, c) is the distance between vertex n and customer c.
A set-based distance metric, dset(Sc(θ), Sc'(θ)), is defined between two sets Sc(θ) and Sc'(θ) to approximate the time required for a truck group to visit customer c' after visiting customer c.
This metric is normalized based on drone and truck speeds (sdr and str).
Customers are then assigned to truck groups using either a Nearest-Neighbor (NN) or Minimum Spanning Tree (MST) partition algorithm, substituting the set-based distance metric for geometric distance.

Phase 2: Set TSP Heuristic This phase determines the customer visiting order for each truck group.

The Traveling Salesman Problem (TSP) is extended to a Set TSP (STSP), where a "visit" to a location set is defined as consecutively visiting one or more locations within the set.
For a truck group Ti, its starting depot pi, and assigned customers Ci, the STSP is formed by collecting |Ci| + 1 location sets Sc(θ), c ∈ Ci and {pi}.
The traveling cost w(u, v) from u ∈ Sc(θ) to v is defined, which includes a term ῶ(c; u, v) for drone operations: ῶ(c; u, v) = min {max { d(u, c) + d(c, v) / sdr, d(u,v) / str }, dtr(u, c) + dtr(c, v) / str }
The objective function for the Set TSP minimizes the sum of costs of the edges traversed by the route: Σ Σ w(u, v) · γu,v + Σ Σ Σ w(u, v) · δu,v c∈Ci∪{pi} u,v∈Sc c,c'∈Ci∪{pi} u∈Sc v∈Sc' where γu,v and δu,v are binary variables related to drone tours and truck collection/launch.

Phase 3: Dynamic Programming for Truck-Drone Optimization This phase computes the simultaneous truck-drone route, given the customer visiting order from Phase 2.

Two key functions are defined:
- TIME(u, v; s, t): minimum time for the truck group to serve customers os, os+1, ..., os+t-1 using t drones launched simultaneously from u, with final drone collection at v.
- VALUE(s, v): optimal cost from depot pi to vertex v after serving the first s customers.
Key Equations:
- For a single drone (t = 1), TIME(u, v; s, 1) is defined with two cases based on drone range limitations.
- For multiple drones (t ≥ 2), TIME(u, v; s, t) is updated recursively.
- VALUE(s, v) is computed using a transition function that considers the k preceding states for a truck group with k drones: VALUE(s, v) = min 0≤t≤k, u∈Ss-t(r),w∈Ss(r) [ d(w, v)/str + TIME(u, w; s - t + 1, t) + VALUE(s - t, u) ]
The optimal cost for truck group Ti is VALUE(|Ci|, pi), and the route is reconstructed by backward tracing.

Road Network Representation: Strongly connected directed graph G = (V, E) where V is the set of vertices and E is the set of edges.
Distance Metric: d(u, v) ≥ 0, representing Euclidean or geometric distance. Shortest path length dtr(u, v; G) is used for truck travel.
Objective: Minimize total delivery cost, proportional to the truck's operating time.
Constraints:
- Trucks follow road network; drones fly directly.
- Drones depart from and return to assigned truck at network nodes.
- Each drone visits one customer per flight, constrained by payload and battery limits (max travel distance r).
- All groups depart from/return to same depots, serving all customers exactly once.
Optimization Solver: MILP solved by Gurobi 10.0.2 (Gurobi Optimization, LLC 2023) with a time limit of 7200 seconds.
Implementation Language: All algorithms implemented in Python.
Computational Environment: Server running Ubuntu 20.04.6 LTS with an AMD Ryzen Threadripper 3990X 64-Core Processor.
Parameters:
- Number of drones per truck: 2 (Partial Manhattan), 3 (Complete Manhattan), 4 (Boston).
- Truck speed (str): 30 km/h.
- Drone speed (sdr): 48 km/h.
- Drone delivery distance limit (r): 1.5 km.

Datasets:
- Partial Manhattan: Strongly connected component with 20 vertices. Datasets with 2 depots and 5/10/15 customers.
- Complete Manhattan: Full Manhattan road network with 1,024 vertices. Datasets with 5 depots and 50/100/150 customers.
- Boston: OpenStreetMap-derived network with 11,000 vertices. Datasets with 10 depots and 50/100/150 customers.
- Each dataset contains 100 instances.
Metrics: Solution quality (delivery cost) and computational efficiency (runtime).
Baselines:
- Column Generation (CG) (Gao et al. 2023)
- Greedy (custom implementation)
- Ant Colony Optimization (ACO) (Dorigo and Gambardella 2002)
- Variable Neighborhood Search (VNS) (Chinnasamy et al. 2022)
- Set-based methods (SNN, SMST) combined with standard TSP or Set TSP (STSP).
Numeric Results:
- Overall Performance: Our method provides the minimum cost solutions across all test scenarios (Partial Manhattan, Complete Manhattan, Boston road networks).
  - On Complete Manhattan with 150 customers, our method achieved a cost of 27.89 and time of 3.23 minutes, compared to the next best (Greedy) with cost 57.08 and time 5.17 minutes.
  - On Boston with 150 customers, our method achieved a cost of 99.64 and time of 21.42 minutes, compared to VNS with cost 176.93 and time 83.99 minutes.
- Cost Reduction: Achieves more than 30% cost reduction over the next-best method.
- Scalability: Effectively handles problems with up to 300 customers on the Manhattan map and 150 customers on the Boston map within a 20-minute computational time-bound. Computational time increases exponentially with the number of customers |C| when depots |P| are fixed.
- Set-based Methods Effectiveness: SMST + STSP consistently achieves the lowest cost across all problem sizes, outperforming standard TSP in solution quality.
Runtime/Training Cost:
- Our method maintains the fastest execution time in medium and larger instances compared to other methods, which struggle or fail to produce solutions.
- Computational time grows exponentially with drone delivery range r due to the linear increase in boundary vertices.

Computational Bottleneck: The Set-TSP problem in Phase 2 represents the primary computational bottleneck, suggesting a clear direction for future algorithmic optimizations.
Discrete Vertex-Based Setting: The current discrete vertex-based setting could be extended to allow continuous drone operations along road edges to produce more efficient delivery strategies.

Method evidence: "We propose a novel three-phase algorithm that first partitions customers using a set-based distance heuristic, then computes initial truck routes via a Set TSP formulation, and finally optimizes drone deployment patterns by dynamic programming." (section: Abstract)
Result evidence: "Through extensive experiments on real-world road networks from Manhattan (1,024 nodes) and Boston (11,000 nodes), we demonstrate that our method achieves more than 30% cost reduction compared to existing approaches while scaling effectively to problems with 150 customers within a 20-minute computational time-bound." (section: Abstract)
Limitation evidence: "First, the computational bottleneck in the Set-TSP could be addressed by adapting heuristic algorithms like the Lin-Kernighan Heuristic (LKH) (Lin and Kernighan 1973), potentially improving scalability without compromising solution quality. Second, the discrete vertex-based setting could be extended to allow continuous drone operations along road edges to produce more efficient delivery strategies." (section: 5 Conclusion)

Optimization of Multi-Agent Flying Sidekick Traveling Salesman Problem over Road Networks

Summary

Problem

Key Contributions

Method

Technical Details

Results

Weaknesses / Limitations

Evidence

Additional Figures