An exact reduction technique for the k-Colour Shortest Path Problem. (January 2023)

• Record Type: Journal Article
• Authors: Cerrone, Carmine; Russo, Davide Donato
• Is Part Of: Computers & operations research. Volume 149(2023)
• Publication Date: 2023-01
• Subjects: Graph reduction -- Dijkstra algorithm -- Shortest path -- Labelled graph; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2022.106027
• Languages: English
• ISSNs: 0305-0548

Abstract

Abstract: The k-Colour Shortest Path Problem is a variant of the classic Shortest Path Problem. This problem consists of finding a shortest path on a weighted edge-coloured graph, where the maximum number of different colours used in a feasible solution is fixed to be k . The k-CSPP has several real-world applications, particularly in network reliability. It addresses the problem of reducing the connection cost while improving the reliability of the network. In this work, we propose a heuristic approach, namely Colour-Constrained Dijkstra Algorithm (CCDA), which is able to produce effective solutions. We propose a graph reduction technique, namely the Graph Reduction Algorithm (GRA), which removes more than 90% of the nodes and edges from the input graph. Finally, using a Mixed-Integer Linear Programming (MILP) model, we present an exact approach, namely Reduced Integer Linear Programming Algorithm (RILP), that takes advantage of the heuristic CCDA and the GRA. Several tests were performed to verify the effectiveness of the proposed approaches. The computational results indicate that the produced approaches perform well, in terms of both the solution's quality and computation times. Highlights: The k-CSPP is a variant of the Shortest Path Problem defined on edge-coloured graph. The proposed reduction technique can significantly reduce the size of the input graph The Colour-Constrained Dijkstra Algorithm can produce effective solutions