Jämförande utvärdering av tre heuristiska metoder inom Marriage in Honey Bees Optimization för det kapaciterade fordonsruttproblemet

This study addresses the NP-hard Capacitated Vehicle Routing Problem (CVRP) through a novel integration of three local search heuristics: 2-opt (intra-route), 2-opt* (inter-route), and CROSS (inter-route), within the Marriage in Honeybee Optimization (MBO) metaheuristic framework. We propose a hybrid approach where worker heuristics refine solutions during MBO’s brood optimization phase, enabling synergistic exploration-exploitation balance. Rigorous experimentation across more than 120 CVRPLIB benchmark instances (32-150 nodes) demonstrates that: CROSS achieves superior solution quality with mean route deviations of 15.42% from optimal solutions, significantly outperforming 2-opt (30.63%) and 2-opt* (29.58%). Statistical validation via one-way ANOVA (F(2,21)=6.508, p=0.0063) and post-hoc Tukey HSD tests confirms these performance differences are significant. However, this accuracy incurs computational costs: CROSS averages 0.95 seconds per instance versus 0.16s for 2-opt variants. Scalability analysis reveals critical divergence: On complex instances (over 100 nodes), CROSS maintains robustness (14% deviation on tai150d) while simpler heuristics deteriorate beyond 30% deviation due to limited inter-route optimization. Time complexity analysis establishes consistent O(N 2 log N ) asymptotic performance for all heuristics within MBO, though CROSS exhibits higher constant factors. For green logistics applications prioritizing emission reduction through distance minimization, CROSS-enhanced MBO is recommended despite slower execution. The 15.42% average distance reduction translates to substantial fuel savings and CO2 reduction. For real-time applications, 2-opt* offers a viable speed-quality trade-off. This work bridges a critical gap in bio-inspired routing literature by systematically evaluating heuristic-MBO synergies, providing implementable strategies for sustainable transportation planning.