On a two-phase solution approach for the bi-objective k-dissimilar vehicle routing problem

In the k-dissimilar vehicle routing problem, a set of k dissimilar alternatives for a Capacitated Vehicle Routing Problem (CVRP) has to be determined for a single instance. The tradeoff between minimizing the longest routing and maximizing the minimum dissimilarity between two routings is investigated. Here, spatial dissimilarity is considered. Since short routings tend to be similar to each other, an objective conflict arises. The developed heuristic approach approximates the Pareto-set with respect to this tradeoff. This paper focuses on the generation of a high-quality candidate set of routings from which k routings are extracted with respect to a spatial as well as to an edge-based dissimilarity metric. In particular two algorithmic variants are suggested which differ in generating dissimilar routings. They are further compared to each other as well as to a naive approach. The method is tested on benchmark instances of the CVRP and findings are reported for both metrics. Taking the hypervolume as a quality criterion, it could be shown that the approach provides a good approximation of the Pareto-set for both metrics. An additional comparison to the results of Talarico et al. (Eur J Oper Res 244(1):129–140, 2015) proves its competitive ability.