Measuring and evaluating the multi-compartment vehicle routing problem in dynamic environment using two hybrid meta-heuristics approaches

Abstract

This paper introduces the Dynamic Multi-Compartment Vehicle Routing Problem (DM-CVRP) as a new variant of the classic Vehicle Routing Problem (VRP). The DMCVRP combines two existing extensions: the Multi-Compartment Vehicle Routing Problem (MCVRP) and the Dynamic Vehicle Routing Problem (DVRP). To analyze and evaluate this variant, the DMCVRP is decomposed into a sequence of standard MCVRPs. A mathematical model is presented based on the MCVRP formulation, ensuring that the total customer demand for each product is fully delivered by the same vehicle, while respecting individual compartment capacities. Given the NP-hard nature of the DMCVRP, we propose and compare two hybrid metaheuristic algorithms: Hybrid Simulated Annealing (HSA) and Hybrid Adaptive Variable Neighborhood Search (HAVNS). The experimental evaluation is performed on a set of dynamic benchmark instances, and sensitivity analysis is conducted on key parameters such as frequency and magnitude of change. The results show that HAVNS outperforms HSA under high-frequency dynamic conditions, while HSA performs better than HAVNS when the frequency of change is low. These findings highlight the strengths and trade-offs of both approaches in solving complex dynamic routing problems with multi-compartment constraints.