Optimal Network Layout - Overview

Petra Heijnen
08 December, 2020

Outline

Overview
Purpose
Why this is different
Network Design - Graph Theory
Anaconda - Spyder
Further reading
Team

Overview

The optimal-network-layout tool is a tool to find the minimum-cost layout for a new network transporting a certain commodity from one or more producers to one or more consumers. The method takes into account route restrictions if needed. These restrictions can consist of predefined paths that the network must follow, for example streets in a city, or of predefined obstacles that the network must not cross, for example nature reserves or water.

The algorithm not only finds the optimal layout for the network, but it will also determine per connection the minimum capacity required to meet the demand at all given time steps. The nodes to be connected can change role per time step, being a producer at some times and a consumer at other times.

If desired and applicable, the new network connections can also be connected to an existing network in the most cost-effective way.

Purpose

The main purpose is to help decision makes to explore the different options they have when deciding about the location of new networks given a set of realistic restrictions. Not only can they find optimal network-layouts that might be not so easily determined by hand, they can also experiment with different sets of inputs to see what the effect will be on the optimal layout and capacity of the network. One might think of what if …

• New producers or consumers would like to be connected at a later stage?
• Specific regions might or might not be crossed?
• Demand and supply profiles and volumes will change in the coming future?
• Capacity of existing connections is or is not increased or used?

Why is this different?

Infrastructure networks have a large number of degrees of freedom, which makes it hard to intuitively compare the cost-effectiveness of alternatives. This method supports network developers by quickly finding least-cost network topologies. The method developed is particularly useful in a multi-actor process, since it enables a quick analysis of low cost networks, while real-world alternatives are discussed among stakeholders on the negotiation table.

Network Design with Graph Theory

In Graph Theory networks are modelled as graphs that consist of nodes and edges. The nodes are here the producers and consumers and, if required, crossings in a routing network, extra splitting nodes to combine or split connections and bending points around obstacles. The nodes have attributes for their location, for their demand or supply at different time steps and for their specific type. The edges are here the new to build or existing connections between the nodes. Each edge is defined by the two nodes it connects. Edges have attributes for their length, the assigned capacity and, if applicable, their current capacity if they are existing connections.

Modelling framework: Spyder (Anaconda)

The model is written in Python 3 and developed in Spyder, which is part of Anaconda. Anaconda can be downloaded here

Further reading

Model: The model is open source and can be accessed online.

Tutorial: A tutorial of the core features.

Scientific publications about the work:

• A method for designing minimum‐cost multisource multisink network layouts, PW Heijnen, EJL Chappin, PM Herder - Systems Engineering, 2019 https://onlinelibrary.wiley.com/doi/pdf/10.1002/sys.21492
• An approach for flexible design of infrastructure networks via a risk sharing contract: The case of CO2 transport infrastructure, Y Melese, P Heijnen, R Stikkelman, P Herder - International Journal of Greenhouse Gas Control, 2017, https://www.sciencedirect.com/science/article/abs/pii/S1750583616305515
• Infrastructure network design with a multi-model approach: Comparing geometric graph theory with an agent-based implementation of an ant colony optimization, P Heijnen, E Chappin, I Nikolic - Journal of Artificial Societies and Social Simulation 17 (4), 1 http://jasss.soc.surrey.ac.uk/17/4/1.html
• Maximising the Worth of Nascent Networks, PW Heijnen, A Ligtvoet, RM Stikkelman, PM Herder - Networks and Spatial Economics, 2014, https://link.springer.com/article/10.1007/s11067-013-9199-1

Team

Petra Heijnen	Emile Chappin	Paulien Herder	Rob Stikkelman
Contact