Network analysis and optimization

The analysis and optimization of networks is a difficult task because of their complexity: they are can be enormous in size (for example, consisting of billions of nodes and links), highly dynamic (exhibiting time-dependent travel-times matrices and demand fluctuations), decentralized (hosting autonomous drivers or distributed routing protocols), and affected by uncertainties (link failures, congestion delays).

The analysis and optimization of networks is a difficult task because of their complexity: they are can be enormous in size (for example, consisting of billions of nodes and links), highly dynamic (exhibiting time-dependent travel-times matrices and demand fluctuations), decentralized (hosting autonomous drivers or distributed routing protocols), and affected by uncertainties (link failures, congestion delays). Yet it is essential to analyse or optimize such networks efficiently. Examples range from the identification of most centralized hubs in large-scale networks to the determination of the shortest routes visiting certain locations in road networks.

Through mathematical modelling, the relevant key characteristics of the network are extracted and represented in a concise way. In combination with sophisticated techniques from discrete optimization, stochastic optimization and algorithmic game theory, the analysis and optimization of such complex networks can then be done efficiently. These techniques have broad applications in route planning and scheduling, spatial optimization, traffic regulation and management and network analysis in general. Examples of application domains include railway networks, urban mobility, freight transportation, supply chains and emergency services.

The algorithmic tools that we develop to tackle network analysis and optimization problems generally outperform the existing standard solutions in terms of solution quality and/or efficiency. Further, our algorithms are designed to provide provable performance guarantees.

Contact person: Guido Schäfer
Research groups: Networks and Optimization (N&O), Stochastics (ST)
Research partners: CPB, Rovecom, RouteXL, Municipality of Amsterdam, Port of Amsterdam, Container Terminal Vrede, GGD Flevoland