Optimization algorithms for the restricted robust shortest path problem

Abstract

This dissertation introduces the Restricted Robust Shortest Path problem (R-RSP), a robust optimization version of the Restricted Shortest Path problem (R-SP), a classical NP-hard problem. Given a digraph G, we associate a cost interval and a resource consumption value with each arc of G. R-RSP aims at nding a path from an origin to a destination vertices in G that satises a resource consumption constraint and minimizes a robust optimization criterion, called restricted robustness cost. This problem has practical applications, as routing electrical vehicles in urban areas, when one looks for a path from a location to another taking into account trac jams and the vehicles' autonomy. R-RSP belongs to a new class of problems composed by robust optimization problems whose classical versions (i.e., parameters known in advance) are already NP-hard. We refer to this class as robust-hard problems. Problems in this class are particularly challenging, as solely evaluating the cost of a solution requires solving a NP-hard problem, which corresponds to the classical counterpart of the problem considered. In this study, we discuss some theoretical aspects of R-RSP, including its computational complexity. Indeed, we show that both R-RSP and its decision version are NP-hard. We also derive a MILP formulation (with a polynomial number of variables and an exponential number of constraints) for R-RSP. Based on this formulation, we propose a heuristic method for R-RSP that consists in solving an approximate compact MILP formulation that uses dual information of the linear relaxation of R-SP. Moreover, a Benders-like decomposition approach is proposed to solve R-RSP at optimality. We also present some techniques to improve the convergence speed of the method by providing initial bounds, as well as by generating additional Benders cuts. Computational experiments show the eectiveness of the proposed algorithms. We highlight that the procedures to solve R-RSP presented in this dissertation are not limited to the referred problem, as they can be extended to other robust-hard problems.