A linear programming based heuristic for robust optimization problems: a case study on solving the restricted robust shortest path problem
Résumé
We study the Restricted Robust Shortest Path problem (R-RSP), a robust optimization version of the classical restricted shortest path problem, which is a N P-hard problem. The arcs are associated with cost intervals and with a length value. The goal is to find a path connecting an origin to a destination vertices respecting a maximum length constraint and minimizing a robust criterion called restricted robustness cost. The robust criteria over the cost is a way to deal with uncertainties associated to path costs. To the best of our knowledge, R-RSP has not been studied in the literature and this is the first ever work to model and to propose procedures for solving the R-RSP. This problem models practical applications such as using electrical vehicles in urban areas, where one looks for a path taking into account traffic jams, and satisfying the vehicles autonomy. In addition, the strategies for solving the R-RSP present several challenges for building efficient procedures. An important theoretical result which reduces the search space on many robust optimization problems is generalized to this new problem. We present a heuristic based on mathematical programming, along with computational experiments that show its effectiveness on solving instances adapted from the literature.