Network connectivity optimization: An evaluation of heuristics applied to complex networks and a transportation case study

Jeremy Auerbach, Hyun Kim

Research output: Other contribution

1 Downloads (Pure)

Abstract

Network optimization has generally been focused on solving network flow problems, but recently there have been investigations into optimizing network characteristics. Optimizing network connectivity to maximize the number of nodes within a given distance to a focal node and then minimizing the number and length of additional connections has not been as thoroughly explored, yet is important in several domains including transportation planning, telecommunications networks, and geospatial analysis. We compare several heuristics to explore this network connectivity optimization problem with the use of random networks, including the introduction of two planar random networks that are useful for spatial network simulation research, and a real-world case study from urban planning and public health. We observe significant variation between nodal characteristics and optimal connections across network types. This result along with the computational costs of the search for optimal solutions highlights the difficulty of finding effective heuristics. A novel genetic algorithm is proposed and we find this optimization heuristic outperforms existing techniques and describe how it can be applied to other combinatorial and dynamic problems.
Original languageEnglish
TypePre-print of article
Media of outputarXiv pre-print repository
Publication statusPublished - 31 Jul 2020

Publication series

NamearXiv

Keywords

  • Physics - Physics and Society
  • Computer Science - Computational Engineering
  • Finance
  • and Science
  • Computer Science - Social and Information Networks

Fingerprint

Dive into the research topics of 'Network connectivity optimization: An evaluation of heuristics applied to complex networks and a transportation case study'. Together they form a unique fingerprint.

Cite this