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
- Hongyao Shen (ORCID: https://orcid.org/0000-0002-4391-1950)
- Yangfan Sun
- Kai Wu
- Xinhua Yao
Institutions
- State Key Laboratory Fluid Power and Mechatronic Systems (CN)
- Zhejiang University (CN)
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
- 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