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.
Show replies by date