Planning under uncertainty



Consider Figure 1, depicting an hypotetical trip from place A to place B, over a transport network consisting also of nodes C and D (in the lefmost two figures), and also node E (in the rightmost figure). Figure 1(a) shows what happens in a deterministic scenario, with no uncertainty. The user may leave by car from node A and go towards either node C or D to find a charging station. If everything goes as planned, total trip time is 50 minutes via node C, or 1 hour via node D. However, whether a charging station will be available at either node is uncertain, as well as the arrival (and then departure) time of the bus, which may be late. In (b), we show what happens if the user’s arrival time at the charging stations is uncertain. Let us say that the user may take 30 plus/minus 5 minutes to reach node C, or 40 plus or minus 8 minutes to reach node D. In this case, it is highly likely that the user will miss the first bus leaving from either station, and she has to wait for the next bus. However, choosing to go via node D is more robust to uncertainty, as another bus is leaving in just 10 additional minutes, and the worst case travel time through node D is much better than the worst case travel time through node C. In (c), it appears clear how going through node D becomes the preferred choice. In fact, while the best case travel time is still provided by the trip through node C, if we consider the likelihood of missing the first bus from it, and the number of other options we have from D, including walking to E and take a train instead, the expected average travel time taking into account uncertainty is much shorter via D.