The k-dissimilar vehicle routing problem

In this paper we defi?ne a new problem, the aim of which is to fi?nd a set of k dissimilar alternative solutions for a vehicle routing problem (VRP) on a single instance. ?This problem has several practical applications in the cash-in-transit sector and in the transportation of hazardous materials. A min-max mathematical formulation is developed that minimizes the objective function value of the worst solution. A distance measure is de?fined based on the edges shared between pairs of alternative solutions. An iterative heuristic algorithm to generate k dissimilar alternative solutions is also presented. ?The solution approach is tested using large and medium size benchmark instances for the capacitated vehicle routing problem.