New Models for Finding K Short and Dissimilar Paths

We address the problem of finding sets of K paths, K∈N, which simultaneously considers two criteria: the minimization of the total paths’ cost and the maximization of their dissimilarity. The purpose of these objectives is to find cheap solutions fairly different from one another, which are relevant considerations in applications that range from hazardous materials transportation to cash collection, where aspects like the safety or the reliability of the solutions are concerns.Two approaches are used to measure the dissimilarity of a set of paths: the extent of the overlap of the paths, in terms of the number of times that each arc appears in more than one of them; and the number of times that the arcs shared by two or more paths appear in that solution. The bi-objective problems resulting from each of these approaches are modeled in terms of integer linear programs, and an ε-constraint method is then designed to solve them. Computational results are presented for the two approaches in terms of the time efficiency, the quality of the sets of solutions obtained, and the dissimilarity of the efficient solutions.