E. Conde Sánchez, M. Leal Palazón, J. Puerto Albandoz
Motivated by real-life applications in transportation, we consider a Shortest Path Problem (SPP) or a Traveling Salesman Problem (TSP) where the arc costs depend on their relative position on the given path. Furthermore, we assume that there exist uncertain cost parameters. We handle the uncertainty using the minmax regret criterion from Robust Optimization. Hence, we study a minmax regret version of the problem under different types of uncertainty of the involved parameters. First, we provide a Mixed Integer Linear Programming formulation by using strong duality in the uncertainty interval case for the SPP. Second, we develop three algorithms, based on Benders decomposition, for a new and more general case in which we consider polyhedral sets of uncertainty for both the SPP and TSP. We use constant factor approximations to initialize the algorithms, extending existing results. Finally, we report some computational experiments for different uncertainty sets.
Keywords: Integer programming, minmax regret models, Benders decomposition
Scheduled
GT10-1 Transport: Ángel Marín. In memoriam
September 5, 2019 10:40 AM
I3L10. Georgina Blanes building