Robust Optimization: theory and applications
Different approaches have been proposed to deal with uncertainty in a combinatorial optimization model. Stochastic programming is one of these models. The main drawback of such an approach is that it sometimes produces models that are difficult to handle from an algorithmic point of view, and however it is often difficult to express uncertainty in probabilistic terms. In parallel, a different stream of research leading to what is called robust optimization, has been explored. The robust optimization framework has been mainly developed from a theoretical point of view. Concerning algorithmic developments, the target was primarily to understand how algorithms perform on robust problems with respect to their classic counterpart. What is missing, in our opinion is the development of an extended robust optimization theory oriented to real-world problems. We believe that an analysis of the potentialities of robust optimization from a practical point of view would lead to new theoretical advances in the robust optimization theory. This project will then approach robust optimization from a complementary point of view, with respect to what has been done until now: we will study practical real-world applications in the optic of robust optimization, developing realistic models and algorithms and, in turn, new theoretical developments. These developments could be ideally defined application-driven extensions to the known theory. According to our background, we will focus our attention to two main application fields: transportations and telecommunications. Vehicle Routing Problems arise in the fields of logistics and transportations. They concern the transportation of items between depots and customers by means of a fleet of vehicles. Solving a VRP means to find an optimal set of routes servicing all customers demands, while respecting the operational constraints, typically concerning vehicles capacity, time windows, drivers maximum working time, etc. Our aim is to identify new applications of interval data robust optimization in real-world transportation problems and to consequently develop models and algorithms for these problems.