An improved multi-directional local search algorithm for the multi-objective consistent vehicle routing problem

This article presents a multi-objective variant of the Consistent Vehicle Routing Problem (MoConVRP). Instead of modeling consistency considerations such as driver consistency and time consistency as constraints as in the majority of the ConVRP literature, they are included as objectives. Furthermore, instead of formulating a single weighted objective that relies on specifying relative priorities among objectives, an approach to approximate the Pareto frontier is developed. Specifically, an improved version of multidirectional local search (MDLS) is developed. The updated algorithm, IMDLS, makes use of large neighborhood search to find solutions that are improved according to at least one objective to add to the set of nondominated solutions at each iteration. The performance of IMDLS is compared with MDLS and five other multi-objective algorithms on a set of ConVRP test instances from the literature. The computational study validates the competitive performance of IMDLS. Furthermore, results of the computational study suggest that pursuing the best compromise solution among all three objectives may increase travel costs by about 5% while improving driver and time consistency by approximately 60% and over 75% on average, when compared with a compromise solution having lowest overall travel distance. Supplementary materials are available for this article. Go to the publishe's online edition of IIE Transactions for datasets, additional tables, detailed proofs, etc.