Emma Ahrens: Flows over Time and Their Applications

 

This project explores differently structured flows over time as, e.g., temporally repeated or chain-decomposable flows. It aims to exploit the structures of flow networks and flow solutions and to obtain fast algorithms for sparse flow networks or sparse solutions.

Furthermore, we want to apply the obtained algorithms in the field of health care. We analyze the optimization of logistical processes in hospitals and focus on the transportation of beds from the storage area to the hospital stations. The transportation problem is modeled using flow over time networks. We aim to find transportation plans which are easily executable by humans and obtain them by considering temporally repeated flows. Furthermore, they should be optimal with regard to other criteria such as having a minimal overall execution time (hence finding an optimal solution of the Quickest Transshipment Problem) or engaging as few employees as possible at every point in time. Here, we found that the algorithm of Ford and Fulkerson for computing maximal temporally repeated flows can be modified to compute maximal temporally repeated flows where the maximal costs over all points in time are minimal. This allows us to find execution plans for the transportation of beds in hospitals, where the number of employees carrying beds is minimal at every point in time.

We study theoretical aspects of flows over time and focus on robustness. Flows over time are calculated on flow networks specifying capacities, transit times, costs, and demand. Spontaneous changes in the network are common and should be considered during the calculation of flows. We already considered the minimization of costs and found reasonable results.