A new Hybrid Genetic Variable Neighborhood search heuristic for the Vehicle Routing Problem with Multiple Time Windows

摘要

The Vehicle Routing Problem (VRP) is a known optimization problems falling under the category of NP-Hard set of problems. VRP, along with its variations, continue to be extensively explored by the research community due to their large domain of application (environment, agriculture, industry, etc.) and economic impact on improving the overall performance, Quality of Services and reducing the operational cost. In this paper, we focus on VRPMTW; a variant of VRP with Multiple Time Windows constraints. We introduce a novel Hybrid Genetic Variable Neighborhood Search (HGVNS) based heuristic for the optimization of VRPMTW. The proposed framework uses genetic cross-over operators on a list of best parents and new implementations of local search operators. Computational results on benchmark data show substantial performance improvement when using the newly introduced heuristic.