DOI: 10.34088/kojose.2041394 ISSN: 2667-484X

Scale-Dependent Performance Analysis of Metaheuristic Approaches for the Multi-Drone En-Route Truck-Drone Delivery Problem

Samet Diri
Show PDF Cite
Truck-drone collaborative last-mile delivery systems extend the classical Traveling Salesperson Problem through complex range, capacity, and synchronization constraints. While most existing studies restrict drone-truck rendezvous to predetermined customer nodes, this study proposes an extended delivery model permitting en-route interception along road segments with multiple concurrent drones to minimize total makespan. The optimization problem is resolved via an O(n) single-pass, event-driven decoding procedure that incorporates a protective ground-wait strategy for the shared single-platform bottleneck and a segment-locking mechanism to prevent retroactive schedule disruption. The framework benchmarks two native-discrete paradigms—a Genetic Algorithm (GA) and a discrete Tabu Search (TS) baseline—against two continuous-domain, sigmoid-binarized metaheuristics: Binary Particle Swarm Optimization (BPSO) and the Binary African Vultures Optimization Algorithm (BAVOA), evaluated across 15 benchmark instances spanning three problem scales (n≈19, n ≈49, and n ≈99) under strictly equal function-evaluation budgets. Nonparametric statistical analyses reveal no significant performance divergence at the small scale (Friedman test, p =0.392). However, as the problem scale increases, native-discrete methods demonstrate statistically significant superiority over both BPSO (p=0.0051) and BAVOA (p=0.0033), achieving near-zero percentage gaps relative to the best-found solutions (GA: 0.016%, TS: 0.011%), while showing no significant difference from each other (Wilcoxon test, p =0.499). Furthermore, runtime evaluations demonstrate that this performance advantage incurs no computational overhead, with GA and TS exhibiting identical execution latencies. These findings provide empirical evidence that direct binary search operators yield significantly more robust and higher-quality solutions than the stochastic transfer functions used in continuous metaheuristics for discrete synchronization problems.

More from our Archive