A Graph-Theoretic Optimization Framework for Underground Parking Lot Layout Planning

Underground parking layout design is challenged by irregular spatial configurations, dense structural obstacles, and the low efficiency of manual planning. This paper proposes a CAD-based optimization framework for underground parking layout under structural constraints. First, structural elements such as walls, columns, and equipment rooms are extracted from CAD drawings to identify feasible layout regions. The parking space–aisle co-layout problem is then formulated as a minimum connected dominating set problem, aiming to maximize parking-region count while ensuring topological accessibility and traffic connectivity. To address instances of different sizes, exact, tabu search, and hybrid optimization methods are developed to balance solution quality and computational efficiency. Experimental results show that the proposed framework reports BILP solutions for the smaller tested instances, returns heuristic solutions for the larger tested cases, whose optimality gaps remain unknown, and yields more stalls in the illustrative manual comparison. Evaluated on 10 engineering drawings, the framework yielded 12 additional stalls in one illustrative manual comparison, subject to engineering verification. The results demonstrate that complex underground parking layout can be effectively transformed into a tractable combinatorial optimization problem, providing an approach evaluated on ten drawings for constrained parking facility planning.

Authors

Institutions

Publication Details

Journal
Algorithms
Published
2026-11-18
DOI
https://doi.org/10.3390/a19111012
Primary Topic
Smart Parking Systems Research
Type
article
Field-Weighted Citation Impact
0.00

Funders

Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
article

A Graph-Theoretic Optimization Framework for Underground Parking Lot Layout Planning

Hongyao Shen, Yangfan Sun, Kai Wu, Xinhua Yao
1 links
Algorithms
Smart Parking Systems Research
article

A Graph-Theoretic Optimization Framework for Underground Parking Lot Layout Planning

Hongyao Shen, Yangfan Sun, Kai Wu, Xinhua Yao
article en

Abstract

Underground parking layout design is challenged by irregular spatial configurations, dense structural obstacles, and the low efficiency of manual planning. This paper proposes a CAD-based optimization framework for underground parking layout under structural constraints. First, structural elements such as walls, columns, and equipment rooms are extracted from CAD drawings to identify feasible layout regions. The parking space–aisle co-layout problem is then formulated as a minimum connected dominating set problem, aiming to maximize parking-region count while ensuring topological accessibility and traffic connectivity. To address instances of different sizes, exact, tabu search, and hybrid optimization methods are developed to balance solution quality and computational efficiency. Experimental results show that the proposed framework reports BILP solutions for the smaller tested instances, returns heuristic solutions for the larger tested cases, whose optimality gaps remain unknown, and yields more stalls in the illustrative manual comparison. Evaluated on 10 engineering drawings, the framework yielded 12 additional stalls in one illustrative manual comparison, subject to engineering verification. The results demonstrate that complex underground parking layout can be effectively transformed into a tractable combinatorial optimization problem, providing an approach evaluated on ten drawings for constrained parking facility planning.

AlgorithmsVol. 19(11)
State Key Laboratory Fluid Power and Mechatronic Systems (CN), Zhejiang University (CN)
Ministry of Education of the People's Republic of China, National Key Research and Development Program of China, Key Research and Development Program of Zhejiang Province
Sustainable cities and communities, Industry, innovation and infrastructure
Smart Parking Systems Research
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon