## Invited Session Fri.3.H 3503

#### Friday, 15:15 - 16:45 h, Room: H 3503

**Cluster 23: Telecommunications & networks** [...]

### Robust network design and applications

**Chair: Christian Raack**

**Friday, 15:15 - 15:40 h, Room: H 3503, Talk 1**

**Agostinho Agra**

The robust vehicle routing problem with time windows

**Coauthors: Marielle Christiansen, Rosa Figueiredo, Lars Magnus Hvattum, Michael Poss, Cristina Requejo**

**Abstract:**

This work addresses the robust vehicle routing problem with time windows. We are motivated by a problem that arises in maritime transportation where delays are frequent and should be taken into account. Our model only allows routes that are feasible for all values of the travel times in a predetermined uncertainty polytope, which yields a robust optimization problem. We propose two new formulations for the robust problem, each based on a different robust approach. The first formulation extends the well-known resource inequalities formulation by employing robust programming with recourse. We propose two techniques, which, using the structure of the problem, allow to reduce significantly the number of extreme points of the uncertainty polytope. The second formulation generalizes a path inequalities formulation to the uncertain context. The uncertainty appears implicitly in this formulation, so that we develop a new cutting plane technique for robust combinatorial optimization problems with complicated constraints. In particular, efficient separation procedures are discussed. We compare the two formulations on maritime transportation instances.

**Friday, 15:45 - 16:10 h, Room: H 3503, Talk 2**

**Sara Mattia**

The robust network loading problem

**Abstract:**

The Robust Network Loading (RNL) problem is a generalization of the well known Network Loading (NL) problem. Given a graph with capacity installation costs for the edges, the RNL problem consists of choosing minimum cost integer capacities to serve all the demands belonging to a given polyhedron of feasible traffic matrices. If the routing scheme must be the same for all the matrices, it is called static or oblivious; if it can be changed according to the matrix, it is called dynamic. If each point-to-point demand in the matrix must be routed using a single path, the flows are called unsplittable, otherwise they are said to be splittable. In this talk we present an algorithm for solving the RNL with dynamic routing and splittable flows and a preliminary comparison between the static and the dynamic approach.

**Friday, 16:15 - 16:40 h, Room: H 3503, Talk 3**

**Fabio D'Andreagiovanni**

On the adoption of multi-band uncertainty in robust network design

**Coauthor: Christina Büsing**

**Abstract:**

Handling uncertainty in the design of telecommunication networks has become a key challenge for leading network operators. Uncertainty in Network Design has been mainly tackled by the Bertsimas-Sim model (BS). However, the central assumption of BS that the deviation band of each uncertain parameter is single may be too limitative in practice: experience indeed suggests that relevant deviations also occur internally and asymmetrically over the band. Breaking the band into multiple sub-bands looks thus advisable.

In this work, we study the robust counterpart of an LP with uncertain coefficient matrix, when a multi-band uncertainty set is considered. We show that the robust counterpart corresponds to a compact LP formulation and that separating robustness cuts corresponds to solving a min-cost flow problem. Finally, we assess the effectiveness of our approach on realistic instances of robust network design problems considered by our industrial partners.

- D. Bertsimas, M. Sim, The Price of Robustness, Oper. Res. 52 (1), 35-53, 2004

C. Büsing, F. D'Andreagiovanni, New results about multi-band uncertainty in Robust Optimization, to appear in Proc. of SEA2012