Pietro Belotti » Robust minimum congestion with dynamic demands - Dept. of Industrial & Systems Engineering, Lehigh University

Robust minimum congestion with dynamic demands

A network defined by a graph $G=(V,A)$ and a capacity function $c:A\to I\!\!R$ . A set $Q$ of demands to be routed on this network is defined by a 5-tuple $(s_q,t_q,d_q,a_q,b_q)$ . The last two parameters refer to a start and end time for the demand, meaning that the demands are not all simultaneous but share a part of their “life” with other demands.

The purpose of this project is to develop an optimization model and a simulation model for the problem of minimizing the maximum congestion over the network: we need a routing for all demands such that the maximum congestion, which is probably reached in a given time interval of the network’s lifetime, is minimized to ensure smooth functioning even when many demands overlap.

Data instance: use the nobel-eu instance provided on the sndlib webpage. The topology of the network, i.e., the graph $G=(V,E)$ , is given, as well as the capacity and the demand source, destination, and volume. As for the parameters $(a_q, b_q)$ of each demand, generate them randomly such that $a_q \in [0,\frac{3}{4}T]$ and $b_q=\min\{a_q+\mu, T\}$ with $\mu$ a random number in $[\frac{1}{10}T,\frac{1}{3}T]$ .