Hybrid Strategies for CVRP Initial Solution: Leveraging Weighted Score Insertion with Grid Search and Multiple Insertion with Iterative Tournament.

This paper presents two novel strategies for solving the Capacitated Vehicle Routing Problem (CVRP): Weighted Score Insertion with Grid Search (WSI-GS) and Multiple Insertion with Iterative Tournament Selection (MIITS). The novelty of WSI-GS lies in its weighted demand-distance heuristic which uses balancing customer demand and proximity to the depot for node insertion, refined by systematic parameter optimization using a grid search. MIITS novelty is integration of iterative tournament selection to enhance solution diversity by a balance between exploration and exploitation in node insertion. This improves adaptability to various problem settings. Despite improved savings-based algorithms like Clarke-Wright and Parker-Holmes often showing superior overall performance, proposed methods outperformed in several Augerat benchmark instances, reaching optimal or better-than optimal (WSI-GS: P-n22-k2; MI-ITS: B-n50-k7, B-n52-k7, P-n19-k2, P-n20-k2, P-n21-k2, and P-n22-k2). The complementary characteristics of WSI-GS and MI-ITS position them as viable candidates for future hybrid frameworks, providing improved robustness and exploration in CVRP solutions. [ABSTRACT FROM AUTHOR]