Mathematical formulation

Shortest path problem

The problem of finding the least cost route through a network is known as the shortest path problem. We can state this problem via binary variables use_a associated with each arc a where use_a=1 if arc a is selected and 0 otherwise.

For every node in the network except the source and sink nodes we establish a flow balance constraint: the sum of incoming travel is the same as the outgoing travel. The source node only has a single outgoing used arc, the sink node has a single incoming used arc. In the following, we define an arc a via its origin ARC_a,1 and its destination node ARC_a,2.

In the model formulation above, we can add the delays caused by roadworks as an additional coefficient to the objective function so that they are taken into account by the shortest path calculation:

However, this means that we assume

1. all delays take their maximum value and
2. all roads incur delays.

These assumptions yield an overly conservative prediction. This case provides an upper bound on the total travel time estimate but it can certainly be considered as fairly unlikely to happen.

Robust optimization problem

The problem that we really wanted to state is

1. delays take values up to their specified maximum value and
2. up to N roads incur delays.

This means that the value of the delay per arc is not fixed, but uncertain. If delay_a denotes the uncertain duration of the delay associates with arc a∈Arcs we can state the cardinality constrained uncertainty set as follows:

The resulting robust optimization problem then has the following form.