A linear programming based heuristic for robust optimization problems: a case study on solving the restricted robust shortest path problem

Abstract : 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.
Document type :
Conference papers
Complete list of metadatas

https://hal-utt.archives-ouvertes.fr/hal-02293214
Contributor : Jean-Baptiste Vu Van <>
Submitted on : Friday, September 20, 2019 - 4:26:04 PM
Last modification on : Saturday, October 5, 2019 - 7:27:15 AM

Identifiers

  • HAL Id : hal-02293214, version 1

Collections

Citation

Lucas Assunção, Thiago Ferreira de Noronha, Andréa Cynthia Santos, Rafael Castro de Andrade. A linear programming based heuristic for robust optimization problems: a case study on solving the restricted robust shortest path problem. 5th International Workshop on Model-Based Metaheuristics (Matheuristics 2014), Jun 2014, Hambourg, Germany. ⟨hal-02293214⟩

Share

Metrics

Record views

9