Heuristic approaches for the cumulative vehicle routing problem

The Cumulative Vehicle Routing Problem (CmVRP) consists of defining routes that minimize a simplified measure of energy consumption while respecting vehicle capacity constraints. It is an NP-hard problem, and therefore heuristics and metaheuristics are employed to obtain high-quality solutions within a reasonable time. This work compares the metaheuristics Adaptive Large Neighborhood Search (ALNS) and Multi-Parent Biased Random-Key Genetic Algorithm with Implicit Path Relinking (BRKGA-MP-IPR). ALNS performs solution destruction and reconstruction with dynamic adaptation of operators, while BRKGA-MP-IPR uses random keys, biased crossover, and local search through path relinking. Both approaches start from a semi-greedy constructive heuristic with a restricted candidate list to generate initial solutions. Experiments conducted on instances from the literature ranging from 32 to 101 clients show that the ALNS achieved an average gap of 0.23% and was 21 times faster than BRKGA-MP-IPR, which frequently reached timeout, indicating that ALNS is more robust for solving the CmVRP.