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

Laboratory of Mathematics, Computer Science, Applications and Information Security, Faculty of Sciences, Mohammed V University in Rabat, Rabat, Morocco

^* Corresponding author: This email address is being protected from spambots. You need JavaScript enabled to view it.

Received: 30 August 2024
Accepted: 6 January 2026

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.