On the selection of k routes in multi-objective Hazmat route planning

Hazardous material (hazmat) transportation has received several attention in the past. On the one hand, this is motivated by the practical interest that hazmat transportation covers for safety reasons; on the other hand, it has attracted the study of those researchers working on vehicle routing, since relevant hazardous material transportation issues are concerned with finding routes with minimum cost and minimum risk. The former objective is mainly related to the carrier point of view, whereas the latter objective takes into account the government point of view. In this paper, we propose a new approach for planning routes for hazmat shipments that selects k efficient paths with respect to the minimization of length, time (cost) and risk; in particular, the selection is made by choosing k representative paths among the set of efficient paths, with high spatial dissimilarity. This allows one to guarantee an equitable distribution of the risk over the network. The proposed approach first exploits the Martins’ algorithm to find the set of efficient paths, and the k-means algorithm to partition the latter set into k classes of paths, minimizing the total variance of the objective vector values of the paths in the same class. Next, one path from each one of the k classes is chosen by heuristically solving the problem of selecting paths maximizing the total spatial dissimilarity. Computational results are presented on random graphs and on a real-life case study.