Integrating Minimum Spanning Tree and MILP in Urban Planning: A Novel Algorithmic Perspective
This paper presents a novel eight-step iterative algorithm for optimizing the layout of a neighborhood, focusing on the efficient allocation of houses to strategically placed facilities, herein referred to as ’points of interest’. The methodology integrates a mixed integer linear programming (MILP)...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2024-01-01
|
| Series: | Buildings |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2075-5309/14/1/213 |
| _version_ | 1797339992721195008 |
|---|---|
| author | Wilson Pavon Myriam Torres Esteban Inga |
| author_facet | Wilson Pavon Myriam Torres Esteban Inga |
| author_sort | Wilson Pavon |
| collection | DOAJ |
| description | This paper presents a novel eight-step iterative algorithm for optimizing the layout of a neighborhood, focusing on the efficient allocation of houses to strategically placed facilities, herein referred to as ’points of interest’. The methodology integrates a mixed integer linear programming (MILP) approach with a heuristic algorithm to address a variant of the facility location problem combined with network design considerations. The algorithm begins by defining a set of geographic coordinates to represent houses within a predefined area. It then identifies key points of interest, forming the basis for subsequent connectivity and allocation analyses. The methodology’s core involves applying the Greedy algorithm to assign houses to the nearest points of interest, subject to capacity constraints. The method is followed by computing a Minimum Spanning Tree (MST) among these points to ensure efficient overall connectivity. The proposed algorithm’s iterative design is a key attribute. The most promising result of this approach is its ability to minimize the distance between houses and points of interest while optimizing the network’s total length. This dual optimization ensures a balanced distribution of houses and an efficient layout, making it particularly suitable for urban planning and infrastructure development. The paper’s findings demonstrate the algorithm’s effectiveness in creating a practical and efficient neighborhood layout, highlighting its potential application in large-scale urban planning and development projects. |
| first_indexed | 2024-03-08T09:55:34Z |
| format | Article |
| id | doaj.art-1fcf9a9250bb49608a43f971fb0be535 |
| institution | Directory Open Access Journal |
| issn | 2075-5309 |
| language | English |
| last_indexed | 2024-03-08T09:55:34Z |
| publishDate | 2024-01-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Buildings |
| spelling | doaj.art-1fcf9a9250bb49608a43f971fb0be5352024-01-29T13:49:16ZengMDPI AGBuildings2075-53092024-01-0114121310.3390/buildings14010213Integrating Minimum Spanning Tree and MILP in Urban Planning: A Novel Algorithmic PerspectiveWilson Pavon0Myriam Torres1Esteban Inga2Engineering Department, Universidad Politécnica Salesiana, Quito 170525, EcuadorArchitecture Department, Universidad Politécnica Salesiana, Quito 170525, EcuadorPostgraduated Department, Universidad Politécnica Salesiana, Quito 170525, EcuadorThis paper presents a novel eight-step iterative algorithm for optimizing the layout of a neighborhood, focusing on the efficient allocation of houses to strategically placed facilities, herein referred to as ’points of interest’. The methodology integrates a mixed integer linear programming (MILP) approach with a heuristic algorithm to address a variant of the facility location problem combined with network design considerations. The algorithm begins by defining a set of geographic coordinates to represent houses within a predefined area. It then identifies key points of interest, forming the basis for subsequent connectivity and allocation analyses. The methodology’s core involves applying the Greedy algorithm to assign houses to the nearest points of interest, subject to capacity constraints. The method is followed by computing a Minimum Spanning Tree (MST) among these points to ensure efficient overall connectivity. The proposed algorithm’s iterative design is a key attribute. The most promising result of this approach is its ability to minimize the distance between houses and points of interest while optimizing the network’s total length. This dual optimization ensures a balanced distribution of houses and an efficient layout, making it particularly suitable for urban planning and infrastructure development. The paper’s findings demonstrate the algorithm’s effectiveness in creating a practical and efficient neighborhood layout, highlighting its potential application in large-scale urban planning and development projects.https://www.mdpi.com/2075-5309/14/1/213urban planning optimizationfacility location problemheuristic algorithmsMixed Integer Linear Programming (MILP)Geographic Information Systems (GIS)Minimum Spanning Tree (MST) |
| spellingShingle | Wilson Pavon Myriam Torres Esteban Inga Integrating Minimum Spanning Tree and MILP in Urban Planning: A Novel Algorithmic Perspective Buildings urban planning optimization facility location problem heuristic algorithms Mixed Integer Linear Programming (MILP) Geographic Information Systems (GIS) Minimum Spanning Tree (MST) |
| title | Integrating Minimum Spanning Tree and MILP in Urban Planning: A Novel Algorithmic Perspective |
| title_full | Integrating Minimum Spanning Tree and MILP in Urban Planning: A Novel Algorithmic Perspective |
| title_fullStr | Integrating Minimum Spanning Tree and MILP in Urban Planning: A Novel Algorithmic Perspective |
| title_full_unstemmed | Integrating Minimum Spanning Tree and MILP in Urban Planning: A Novel Algorithmic Perspective |
| title_short | Integrating Minimum Spanning Tree and MILP in Urban Planning: A Novel Algorithmic Perspective |
| title_sort | integrating minimum spanning tree and milp in urban planning a novel algorithmic perspective |
| topic | urban planning optimization facility location problem heuristic algorithms Mixed Integer Linear Programming (MILP) Geographic Information Systems (GIS) Minimum Spanning Tree (MST) |
| url | https://www.mdpi.com/2075-5309/14/1/213 |
| work_keys_str_mv | AT wilsonpavon integratingminimumspanningtreeandmilpinurbanplanninganovelalgorithmicperspective AT myriamtorres integratingminimumspanningtreeandmilpinurbanplanninganovelalgorithmicperspective AT estebaninga integratingminimumspanningtreeandmilpinurbanplanninganovelalgorithmicperspective |