Affiliations: [a] Henan Key Laboratory of Big Data Analysis and Processing, Henan University, Kaifeng, China
| [b]
College of Computer and Information Engineering, Henan University, Kaifeng, China
Correspondence:
[*]
Corresponding author. Gaojuan Fan, College of Computer and Information Engineering, Henan University, Kaifeng 475004, China. E-mail: [email protected].
Abstract: Multi-compartment vehicle routing problem (MCVRP) is an extension of the classical capacitated vehicle routing problem where products with different characteristics are transported together in one vehicle with multiple compartments. This paper deals with this problem, whose objective is to minimize the total travel distance while satisfying the capacity and maximum route length constraints. We proposed a hybrid iterated local search metaheuristic (HILS) algorithm to solve it. In the framework of iterated local search, the current solution was improved iteratively by five neighborhood operators. For every obtained neighborhood solution after the local search procedure, a large neighborhood search-based perturbation method was executed to explore larger solution space and get a better neighborhood solution to take part in the next iteration. In addition, the worse solutions found by the algorithm were accepted by the nondeterministic simulated annealing-based acceptance rule to keep the diversification of solutions. Computation experiments were conducted on 28 benchmark instances and the experimental results demonstrate that our presented algorithm finds 17 new best solutions, which significantly outperforms the existing state-of-the-art MCVRP methods.
Keywords: Multi-compartment vehicle routing problem, hybrid metaheuristic, iterated local search, large neighborhood search, simulated annealing
