AI Summary & Key Takeaways
AI InsightThese 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.
📌 3 Key Takeaways
Abstract
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.
Özet
Kamyon–dron iş birliğine dayalı son-kilometre teslimat sistemleri, klasik Gezgin Satıcı Problemi'nin (TSP) menzil, kapasite ve senkronizasyon kısıtlarıyla genişletildiği NP-zor bir kombinatoryal optimizasyon sınıfı oluşturmaktadır. Literatürdeki çalışmaların önemli bir bölümü, dronun kamyonla yalnızca önceden belirlenmiş müşteri düğümlerinde buluşabildiği varsayımına dayanmaktadır. Bu çalışmada; dronların kamyonu seyir halindeyken yol segmentleri üzerinde yakalayabildiği (en-route interception), birden fazla dronun eşzamanlı görev yapabildiği ve toplam operasyon süresini (makespan) enküçüklemeyi amaçlayan genişletilmiş bir teslimat modeli önerilmektedir. Geliştirilen model; paylaşımlı tekil platform darboğazını yöneten koruyucu yerde bekleme (ground-wait) stratejisi ve ileri rota bütünlüğünü koruyan segment kilitleme mekanizmasıyla desteklenen, O(n) hesaplama karmaşıklığına sahip tek geçişli, olay güdümlü bir çözümleme prosedürüyle çözülmüştür. Önerilen optimizasyon çerçevesi; Genetik Algoritma (GA), İkili Parçacık Sürü Optimizasyonu (BPSO) ve İkili Afrika Akbabaları Optimizasyon Algoritması (BAVOA) entegrasyonuyla, üç farklı ölçekte (n≈19, n≈49, n≈99) toplam 15 referans problem örneği üzerinde test edilmiştir. Parametrik olmayan istatistiksel analizler, küçük ölçekte algoritmalar arasında anlamlı bir başarım farkı bulunmadığını (Friedman testi, p=0,135), ancak problem ölçeği büyüdükçe GA'nın hem BPSO'ya (p=0,0051) hem de BAVOA'ya (p=0,0022) karşı istatistiksel olarak anlamlı bir üstünlük sağladığını ortaya koymuştur. Elde edilen bulgular, ayrık karar uzaylarında doğrudan ikili temsile dayanan arama operatörlerinin, sürekli-uzay kökenli algoritmaların stokastik transfer fonksiyonlarına kıyasla çok daha kararlı ve yüksek kaliteli çözümler ürettiğini ampirik olarak kanıtlamaktadır.