|
 
|
[BD02] Integer Linear Programming for the Robust Shortest Path Problem
Rapport Scientifique : Date de dépot: 2002/01/01, (Tech. Rep.: CEDRIC-02-345)
motcle:
Résumé:
The shortest path problem in a network with nonnegative arc lengths can be solved easily in polynomial time. We study here the case of uncertainty of the arc lengths and we adopt the scenario approach to characterize uncertainties. With each edge a of the network G is associated card(S) values c(a,r), r belonging to S, the set of scenarios. We consider here the absolute robust shortest path (ARSP) problem defined as finding in a network the path that minimizes the maximum path length from an origin node to a destination node over all scenarios. We show in this paper that it is possible to solve large sized instances of the ARSP problem by using a mixed integer programming tool.
Keywords : Shortest path, uncertainty, robustness, scenario, integer programming, experiments.
BibTeX
| @techreport { | |||
| BD02, | |||
| title | = | "{Integer Linear Programming for the Robust Shortest Path Problem}", | |
| author | = | "A. Billionnet and K. Djebali", | |
| number | = | "{CEDRIC-02-345}", | |
| institution | = | "{CEDRIC laboratory, CNAM-Paris, France}", | |
| date | = | {01-01-2002}, | |
| } | |||
