A Feasibility-Driven Anytime Hybrid Search for the 3L-CVRP with CoM-Aware Load Balancing

This paper addresses the 3L-CVRP under practical loading constraints arising in multi-stop FMCG distribution. We consider heterogeneous vehicle payload and compartment capacity, non-overlap, orthogonal packing with restricted rotations, last-in-first-out unloading compatibility, fragility constraints, and minimum supporting-area requirements. The proposed method follows a feasible-first anytime design that preserves loading feasibility throughout the search and accounts for center of mass balance through a penalty integrated into the routing objective. The approach first builds a minimum spanning tree over customer locations to guide decomposition, then generates customer clusters via feasibility-driven merging to eliminate unloadable groupings early. Each feasible cluster is refined by an anytime ant colony optimization procedure, followed by greedy route consolidation and relocation-based neighborhood search to reduce routing cost while preserving loading feasibility. The method is evaluated on two benchmark suites (D1 and D2) and an FMCG-oriented dataset (D3) under repeated runs and fixed wall-clock budgets, with TS and ALNS-DBLF as baselines. Across these datasets, the proposed approach achieves 100% feasibility reliability, faster time-to-first-feasible solutions, stronger run-to-run stability, and better load-balance quality. On D1, time-to-first-feasible drops to 1.77 s, while the safe-vehicle ratio reaches 75.81%, with a 9.62% routing-distance penalty relative to the strongest distance baseline on the common feasible subset. On D2, the method maintains 100% checkpoint success at 15 s as instance size increases. On D3, it achieves the best average distance, fewest vehicles, highest fill rate, and highest safe-vehicle ratio. These results show a practical balance between routing efficiency, computational responsiveness, and load-balance quality for time-constrained FMCG distribution.