Enhanced Artificial Bee Colony Algorithm for the Probabilistic Traveling Salesman Problem with Deadlines

Abstract

This study tackles time-sensitive routing under uncertainty. It proposes ABC-DT, an enhanced
Artificial Bee Colony algorithm for the #P-hard Probabilistic Traveling Salesman Problem with Deadlines
(PTSPD). Literature highlights ABC’s efficacy in combinatorial optimization, due to its parameter efficiency
and robust exploration–exploitation balance [1,2]. ABC is chosen for its adaptability to discrete problems like
PTSPD. It outperforms traditional heuristics in stochastic environments [3]. However, standard ABC suffers
from premature convergence and suboptimal handling of probabilistic structures. Thus, ABC-DT combines
three innovations: (1) adaptive neighborhood operators weighted by probabilities and deadlines, (2) dynamic
parameter tuning, and (3) hybrid scout diversification. Experiments on benchmarks (22–100+ nodes) show
7–23% lower expected costs, with reduced variability compared to ABC-standard. Validation studies confirm
this (+10–15% costs without weighted operators). The algorithm scales well, handling 152-node instances,
and is flexible for fixed or proportional penalties, making it viable for urgent logistics.