TY - JOUR
T1 - Infrastructure network design with a multi-model approach
T2 - Comparing geometric graph theory with an agent-based implementation of an ant colony optimization
AU - Heijnen, Petra
AU - Chappin, Emile
AU - Nikolic, Igor
PY - 2014
Y1 - 2014
N2 - Network infrastructures, such as roads, pipelines or the power grid face a multitude of challenges, from organizational and use changes, to climate change and resource scarcity. These challenges require the adaptation of existing infrastructures or their complete new development. Traditionally, infrastructure planning and routing issues are solved through top-down optimization strategies such as mixed integer non linear programming or graph approaches, or through bottom up approaches such as particle swarm optimizations or ant colony optimizations. While some integrated approaches have been proposed int he literature, no direct comparison of the two approaches as applied to the same problem have been reported. Therefore, we implement two routing algorithms to connect a single source node to multiple consuming nodes in a topology with hard boundaries and no-go areas. We compare a geometric graph algorithm finding an (sub)optimum edge-weighted Steiner minimal tree with a Ant Colony Optimization algorithm implemented as an Agent Based Model. Experimenting with 100 randomly generated routing problems, we find that both algorithms perform surprisingly similar in terms of topology, cost and computational performance. We also discovered that by approaching the problem from both top-down and bottom-up perspective, we were able to enrich both algorithms in a co-evolutionary fashion. Our main findings are that the two algorithms, as currently implemented in our test environment hardly differ in the quality of solution and computational performance. There are however significant differences in ease of problem encoding and future extensibility.
AB - Network infrastructures, such as roads, pipelines or the power grid face a multitude of challenges, from organizational and use changes, to climate change and resource scarcity. These challenges require the adaptation of existing infrastructures or their complete new development. Traditionally, infrastructure planning and routing issues are solved through top-down optimization strategies such as mixed integer non linear programming or graph approaches, or through bottom up approaches such as particle swarm optimizations or ant colony optimizations. While some integrated approaches have been proposed int he literature, no direct comparison of the two approaches as applied to the same problem have been reported. Therefore, we implement two routing algorithms to connect a single source node to multiple consuming nodes in a topology with hard boundaries and no-go areas. We compare a geometric graph algorithm finding an (sub)optimum edge-weighted Steiner minimal tree with a Ant Colony Optimization algorithm implemented as an Agent Based Model. Experimenting with 100 randomly generated routing problems, we find that both algorithms perform surprisingly similar in terms of topology, cost and computational performance. We also discovered that by approaching the problem from both top-down and bottom-up perspective, we were able to enrich both algorithms in a co-evolutionary fashion. Our main findings are that the two algorithms, as currently implemented in our test environment hardly differ in the quality of solution and computational performance. There are however significant differences in ease of problem encoding and future extensibility.
KW - Ant Colony Optimization
KW - Infrastructure
KW - Model Comparison
KW - Routing
KW - Steiner Minimal Tree
UR - http://www.scopus.com/inward/record.url?scp=84908426326&partnerID=8YFLogxK
U2 - 10.18564/jasss.2533
DO - 10.18564/jasss.2533
M3 - Article
AN - SCOPUS:84908426326
SN - 1460-7425
VL - 17
JO - JASSS
JF - JASSS
IS - 4
ER -