Heuristics for the bi-objective path dissimilarity problem

In this paper the path dissimilarity problem is considered. The problem has previously been studied within several contexts, the most popular of which is motivated by the need to select transportation routes for hazardous materials. The aim of this paper is to formally introduce the problem as a bi-objective optimization problem, in which a single solution consists of a set of p different paths, and two conflicting objectives arise, on one hand the average length of the paths must be kept low, and on the other hand the dissimilarity among the paths in the set should be kept high. Previous methods are reviewed and adapted to this bi-objective problem, thus we can compare the methods using the standard measures in multi-objective optimization. A new GRASP procedure is proposed and tested against the revised methods, and we show that it is able to create better approximations of efficient frontiers than existing methods.