A MULTI-STAGE LEXICOGRAPHIC DECOMPOSITION FOR THE PRIZE-COLLECTING VRP: COMPARING BRANCH-CUT-AND-PRICE WITH A COMMERCIAL SOLVER

This article investigates the exact solution of the Prize-Collecting Vehicle Routing Problem with a minimum-demand constraint using a Branch-Cut-and-Price (BCP) framework implemented in VRPSolver. We compare three approaches: (i) a monolithic integrated formulation; (ii) a basic sequential decomposition; and (iii) a lexicographic decomposition that separates prize selection (multiple knapsack problem) from routing, explores alternative optimal subsets with no-good cuts, and uses Hybrid Genetic Search (HGS) solutions as primal bounds. In our experiments, the monolithic model often exhibits weak bounds and slow convergence, while the basic decomposition can lock in a single prize configuration and miss other equally profitable route structures. The proposed hybrid architecture enumerates optimal prize subsets and to obtain tight bounds the subsequent routing phase, yielding faster optimality proofs and improved solution quality over the baselines, and enabling a direct comparison against a commercial heuristic solver.