Dynamic Multi-compartment Vehicle Routing Problem: Formulation and Algorithm

In this paper, two complex variations of the classic vehicle routing problem (VRP) are combined together to present a new VRP variant called the Dynamic Multi-Compartment Vehicle Routing Problem (DMCVRP). The aim of DMCVRP is to minimize the total traveled distance, in this type of problems different product types are loaded into a fleet of homogeneous vehicle with multiple compartments, and each compartment is dedicated to a single type of products. During the execution of the multi-compartment vehicle routing problem (MCVRP) routes the dynamic behavior of the problem shows up and causes some changes in the MCVRP routes. In this problem, we divide the DMCVRP into a set of standard MCVRP, and we present the mathematical model of DMCVRP as a MCVRP model, in which the total customer demands for each product must be fully delivered by the same vehicle with respect of each compartment capacity. Moreover, the distance traveled by each vehicle is subject to a constraint Considering the NP-hardness of the proposed problem, we propose the hybrid adaptive variable neighborhood search (HAVNS) to solve the problem.