The quadratic shortest path problem

Quadratic Shortest Path Problem (QSPP) is a variation of the Shortest Path problem, where the objective function is quadratic. In addition to a cost associated with each edge in a graph, there is a cost with each pair of edges in the graph. The cost of a path is the sum of the costs of each edge in the path and the quadratic costs for each pair of edges in the path. This makes the problem NP-hard. polynomial-time algorithms are known for restricted versions of QSPP, such as Adjacent-QSPP, where the quadratic cost is only considered between adjacent pairs of vertices in the path. Integer programs with different bounds have also been discussed for QSPP with non-negative cost matrices. In this thesis, we provide integer programs for solving QSPP with arbitrary cost matrices. We compare our formulation where sub-tours are eliminated with the well-known MTZ constraints with one where sub-tours are eliminated iteratively by introducing the violated constraints only. We also provide two heuristic polynomial time solutions to the QSPP, the Basic Algorithm and the Multi Start Algorithm. We compare the Multi Start Algorithm with solutions obtained from the integer programs with MTZ constraints and show that the Multi Start Algorithm is a good heuristic to QSPP.