The quadratic shortest path problem (QSPP) is a NP-hard problem which aims to find a path between two vertices in a directed graph such that the sum of all pairwise interaction costs of its constituent arcs is minimized. Previous authors have obtained algorithms for solving the QSPP, though these are often limited to special cases and leave room for improvement. This research aims to develop an algorithm that can solve general instances of the QSPP in a more efficient way than previous authors. The performance of the developed algorithm will be thoroughly analysed. We will compare the results with those of other authors. A fair comparison requires an implementation of their algorithms and a relevant test set of graphs. A comparison will also be made with the performance of general purpose solvers, like Integer Linear Programming software, applied to the QSPP.
In a second part of the research, we will identify problems related to the QSPP. An example is the extension to the case where multiple edge-disjoint shortest paths must be found. We will look how well the QSPP alorithm performs when directly applied (or with minor changes) to these problems. We will also focus on developing new algorithms, each optimised for a specific related problem. These will set a baseline performance for future authors to beat, as many problems related to the QSPP remain unexplored.