[Talks@IDSIA] 24.11 1130 NE Toklu - Robust Traveling Salesman Problem Under Dynamic Uncertainty

24 Nov 1130-1200 IDSIA meeting room, Galleria 1, Manno Nihat Engin Toklu, Okan University, Computer Engineering Department, Istanbul, Turkey (joint work with Seda Yanik, Istanbul Technical University, Industrial Engineering Department, Istanbul Turkey) Robust Traveling Salesman Problem Under Dynamic Uncertainty In the field of robust optimization, we study problems in which the problem data are not exactly known (i.e. problem data are under uncertainty). Considering that multiple (or infinite) scenarios emerge out of the uncertainty, the goal is to find a robust solution which does not "go bad" under most or all scenarios. A very popular approach for robust optimization was proposed by Bertsimas & Sim (2003, 2004), where the uncertain problem data are expressed by intervals, and there is a Gamma parameter for tuning the model's conservativeness (i.e. pessimism: on how much of the coefficients do we assume unluckiness will happen?). In this talk, we propose a robust traveling salesman problem model which can be considered as a generalization of the study of Bertsimas & Sim. Representing the fact that the traffic on the paths change from time to time, our model considers that each path has more than one uncertainty profile, each profile having a different activation time, and imposing a different cost interval. Furthermore, we show that our model does not complicate the process of tuning in terms of conservativeness, depending on a single Gamma parameter.