Efficient Labeling Algorithms for Adjacent Quadratic Shortest Paths

The main focus of this dissertation is to study the Adjacent Quadratic Shortest Path Problem (AQSPP), which consists in finding the shortest path on a directed graph when its total weight component also includes the impact of consecutive arcs. We provide a formal description of the AQSPP and propose an extension of Dijkstra's algorithm for solving AQSPPs in polynomial-time, providing a proof of its correctness under mild assumptions. We introduce an adjacent quadratic A* algorithm (that we denote aqA*) with a backward search for cost-to-go estimation to speed up the search. We assess the performance of both algorithms by comparing their relative performance with benchmark algorithms from the scientific literature and carry out a thorough collection of sensitivity analyses of the methods on a set of problem characteristics using randomly generated graphs. Numerical results suggest that aqA* outperforms all other algorithms, with performance significantly superior than the considered alternatives.