A reduction technique for the k-Colour Shortest Path Problem

Over the years were defined many variants of the classic Shortest Path Problem. The k-Colour Shortest Path Problem (k-CSPP) is one of those variants. It consists of finding the shortest path on a weighted edge-coloured graph when the maximum number of colours used in a feasible solution is fixed apriori. This problem addresses several real-world applications; in particular, the k-CSPP can model problems related to network reliability or intermodal logistic. In this work, we propose an effective reduction technique, namely Graph Reduction Algorithm (GRA), that, starting from a heuristic solution, can remove more than 90% of the nodes and the edges from the input graph. It is also proposed the Colour-Constrained Dijkstra Algorithm (CCDA), a heuristic approach, used in conjunction with our reduction algorithm. Finally, an exact method, namely RILP, is described. It is based on the GRA combined with a MILP model. Several tests were performed to assess the effectiveness of the proposed approaches in terms of solution quality and computation times.