隨著都市化進程加速，停車場內的交通壅塞問題日益嚴重，尤其在高負載或突發事件情況下，傳統管理方法無法有效處理即時交通變化。本研究提出了一套適用於停車場環境的動態路徑規劃系統，透過改良式 A* 演算法與動態等待時間機制，有效預測並主動避開潛在的壅塞點，大幅降低車輛的平均行駛與等待時間。此外，本研究設計了動態路徑重規劃機制，能即時處理如車道臨時封閉等突發事件，快速重新規劃替代路徑。
實驗結果顯示，改良式 A* 演算法可將車輛整體平均等待時間降低約62.02%，並且動態重規劃機制在突發事件情境下之重新規劃成功率達到100%，證明本研究提出之方法在緩解停車場壅塞問題上具有高度即時性與可靠性，具備良好的實務應用與推廣潛力。

With the acceleration of urbanization, traffic congestion within parking lots has become increasingly severe. Traditional management methods are inadequate to effectively handle real-time traffic changes, especially under high-load conditions or unforeseen incidents. This study proposes a dynamic path planning system tailored for parking lot environments, integrating an improved A* algorithm with a dynamic waiting time mechanism to proactively predict and avoid potential congestion points, significantly reducing vehicles' average travel and waiting times. Additionally, this study develops a dynamic path replanning mechanism capable of swiftly handling unexpected incidents, such as temporary lane closures, by promptly recalculating alternative routes. Experimental results demonstrate that the improved A* algorithm reduces the average vehicle waiting time by approximately 62.02%, and the dynamic replanning mechanism achieves a 100% success rate in replanning under incident conditions. The results indicate that the proposed methods exhibit high immediacy and reliability in mitigating parking lot congestion issues, highlighting strong potential for practical application and further development.

目錄
第一章	緒論	1
1.1	研究動機與背景	1
1.2	研究目的	3
1.3	論文架構	5
第二章	背景技術與相關研究	7
2.1	路徑規劃演算法概述	7
2.2	傳統 A* 演算法之基本原理及應用	9
2.3	停車場壅塞管理相關研究	12
2.3.1	傳統靜態管理方法	12
2.3.2	動態資訊導引系統	12
2.3.3	模擬與演算法輔助管理方法	13
2.3.4	動態重規劃方法	14
2.3.5	本研究的切入點與創新點	14
第三章	研究方法設計	16
3.1	停車場環境與地圖模型	16
3.2	動態等待時間機制	17
3.3	壅塞預測和路徑選擇	23
3.4	動態路徑重規劃機制	29
3.4.1	障礙物偵測和事件觸發機制	29
3.4.2	判斷受影響的車輛並重新規劃路徑	30
3.4.3	車輛重新規劃路徑的優先排序策略	30
3.5	系統實現和執行機制	32
3.5.1	車輛生成和進場模式	32
3.5.2	多執行緒和同步機制	32
3.5.3	實驗用地圖的選擇理由	33
第四章	實驗結果與分析	34
4.1	實驗設計	34
4.1.1	實驗目標	34
4.1.2	實驗環境設定	35
4.2	實驗方法及步驟	37
4.2.1	效能統計模擬程式實驗步驟	37
4.2.2	動態路徑重規劃模擬程式實驗步驟	40
4.3	實驗結果與分析	43
4.3.1	統計數據結果與分析	43
4.3.2	分析與討論	47
4.3.3	動態路徑重規劃機制驗證	49
4.4	本章小結	53
第五章	結論與未來研究	55
5.1	研究成果總結	55
5.1.1	改良式 A* 演算法的效能驗證成果	55
5.1.2	動態路徑重規劃機制驗證成果	56
5.1.3	整體系統對壅塞問題的貢獻	57
5.2	研究貢獻	58
5.2.1	改良式 A* 與動態等待時間機制的整合	58
5.2.2	突發事件下的動態路徑重規劃機制	59
5.2.3	完整且互補的實驗驗證方法	59
5.2.4	實際價值和未來推廣性	60
參考文獻	61

圖目錄
圖 1 車輛停車流程圖	23
圖 2壅塞預測和路徑選擇流程圖	28
圖 3 動態路徑重規劃機制流程圖	31
圖 4停車場 13×12 地圖示意圖	37
圖 5 效能統計模擬程式流程	39
圖 6動態路徑重規劃前後之模擬示意圖（a）重規劃前；（b）重規劃後	40
圖 7 動態路徑重規劃模擬程式流程圖	42
圖 8 某次模擬中之極端壅塞案例車輛停車位置與進場順序示意圖	44
圖 9 遭遇突發事件後之首次路徑重規劃成功案例	52
圖 10 首次重規劃失敗後允許迴轉之成功重規劃案例	52

表目錄
表 1車輛平均行駛和等待時間比較	45
表 2未做IQR過濾的樣本數據	46
表 3做完 IQR 過濾的樣本數據	46

參考文獻
[1] D.  C.  Shoup, “The High Cost of Free Parking.” Chicago, IL, USA: Planners Press, 2005. 
[2]  Y.  Sun, “Research on strategies to address urban parking issues in China,” Frontiers in Humanities and Social Sciences, vol. 4, no. 1, pp. 128–133, 2024. 
[3]  M.  R.  Islam et al., “Smart parking management system to reduce congestion in urban area,” in Proc. 2nd Int. Conf. Electr., Control Instrum. Eng. (ICECIE), Kuala Lumpur, Malaysia, Aug. 2020, pp. 1–6. 
[4] S.  Koenig and M.  Likhachev, “Fast replanning for navigation in unknown terrain,” IEEE Trans. Robot., vol. 21, no. 3, pp. 354–363, Jun. 2005.
[5] J. L.  Lupien et al., “Entropy based dynamic programming for efficient vehicle parking,” arXiv, arXiv:2411.17014, Nov. 2024. [Online].
[6]  H.  Taghipour, A.  B.  Parsa, and A.  K.  Mohammadian, “A dynamic approach to predict travel time in real time using data driven techniques and comprehensive data sources,” Transportation Engineering, vol. 2, p. 100025, 2020. 
[7] B.  Adabala and Z.  Ajanović, “A multi heuristic search based motion planning for automated parking,” arXiv, arXiv:2307.07857, Jul. 2023.
[8] B.  Paden, M.  Čáp, S.  Z.  Yong, D.  Yershov, and E.  Frazzoli, “A survey of motion planning and control techniques for self driving urban vehicles,” IEEE Trans. Intell. Veh., vol. 1, no. 1, pp. 33–55, Mar. 2016.
[9] G.  F.  Newell, “A simplified theory of kinematic waves in highway traffic—Part I: General theory,” Transportation Research B, vol. 27, no. 4, pp. 281–287, 1993.
[10] D.  C.  Gazis and R.  Herman, “The moving and ‘phantom’ bottlenecks,” Transportation Science, vol. 26, no. 3, pp. 223–229, 1992.
[11] N.  Fulman and I.  Benenson, “Approximation of search times for on street parking based on supply and demand,” Geosimulation Lab, Tel Aviv Univ., 2024. 
[12]	T.  Fabusuyi and R.  C.  Hampshire, “Rethinking performance based parking pricing: A case study of SFpark,” Transp. Res. Inst., Univ. Michigan, 2024.
[13]  C. Nugent, “Americans’ addiction to parking lots is bad for the climate. California wants to end it,” TIME, Sep. 28 2022. [Online]. Available: https://time.com/6217873/parking-lots-climate-change-california/. [Accessed: May 2 2025].
[14] A.  Stentz, “The Focussed D* algorithm for real time replanning,” in Proc. 14th Int. Joint Conf. Artif. Intell. (IJCAI), Montréal, QC, Canada, Aug. 1995, pp. 1652–1659.
[15] A.  Stentz, “Optimal and efficient path planning for partially known environments,” in Proc. IEEE Int. Conf. Robot. Autom. (ICRA), San Diego, CA, USA, 1994, pp. 3310–3317.
[16]  S.  Koenig and M.  Likhachev, “D* Lite,” in Proc. AAAI Conf. Artif. Intell., Edmonton, AB, Canada, Jul. 2002, pp. 476–483.
[17] P.  E. Hart, N.  J.  Nilsson, and B.  Raphael, “A formal basis for the heuristic determination of minimum cost paths,” IEEE Trans. Syst. Sci. Cybern., vol. 4, no. 2, pp. 100–107, Jul. 1968.
[18] M.  Likhachev, G.  J.  Gordon, and S.  Thrun, “ARA*: Anytime A* with provable bounds on sub optimality,” IEEE Trans. Robot., vol. 21, no. 3, pp. 343–352, Jun. 2005.
[19] S.  Choi and W.  Yu, “Any angle path planning on non uniform costmaps,” in Proc. IEEE Int. Conf. Robot. Autom. (ICRA), Shanghai, China, May 2011, pp. 5615–5621.
[20] B.  Angulo, A.  I.  Panov, and K.  Yakovlev, “Policy optimization to learn adaptive motion primitives in path planning with dynamic obstacles,” arXiv, arXiv:2212.14307, Dec. 2022.
[21] C.  Zhou, B.  Huang, and P.  Fränti, “A review of motion planning algorithms for intelligent robots,” Journal of Intelligent Manufacturing, vol. 33, pp. 387–424, 2022, doi: 10.1007/s10845 021 01867 z.
[22] A.  Jones, M.  Schwager, and C.  Belta, “A receding horizon algorithm for informative path planning with temporal logic constraints,” in Proc. IEEE Int. Conf. Robot. Autom. (ICRA), Karlsruhe, Germany, May 2013, pp. 5019–5024.
[23] E.  W.  Dijkstra, “A note on two problems in connexion with graphs,” Numerische Mathematik, vol. 1, pp. 269–271, 1959.
[24]   T.  H.  Cormen, C.  E.  Leiserson, R.  L.  Rivest, and C.  Stein, Introduction to Algorithms, 3rd ed. Cambridge, MA, USA: MIT Press, 2009. 
[25] A.  Buluç, S.  Beamer, K.  Madduri, K.  Asanović, and D.  Patterson, “Distributed memory breadth first search on massive graphs,” in Parallel Graph Algorithms, D. Bader, Ed. Boca Raton, FL, USA: CRC Press, 2015, ch. 6, pp. 87–106.
[26]  R.  E.  Tarjan, “Depth first search and linear graph algorithms,” SIAM J. Comput., vol. 1, no. 2, pp. 146–160, 1972.
[27] D.  Ferguson, M.  Likhachev, and A.  Stentz, “A guide to heuristic based path planning,” in Proc. IEEE/RSJ Int. Conf. Intell. Robots Syst. (IROS), Edmonton, AB, Canada, Aug. 2005, pp. 212–217.
[28]  S.  Koenig, M.  Likhachev, and D.  Furcy, “Lifelong planning A*,” Artificial Intelligence, vol. 155, no. 1–2, pp. 93–146, 2004.
[29] 	S. M. LaValle, Planning Algorithms. Cambridge, U.K.: Cambridge Univ. Press, 2006.
[30]  M.  Likhachev, D.  Ferguson, G.  J.  Gordon, A.  Stentz, and S.  Thrun, “Anytime dynamic A*: An anytime, replanning algorithm,” in Proc. AAAI Conf. Artif. Intell., Pittsburgh, PA, USA, Jul. 2005, pp. 262–267.
[31]  L.  Guo, S.  Huang, J.  Zhuang, and A.  W.  Sadek, “Modeling parking behavior under uncertainty: A static game theoretic versus a sequential neo additive capacity modeling approach,” Networks and Spatial Economics, vol. 13, no. 3, pp. 327–350, 2013. 
[32] M.  Chen and T.  Chang, “A parking guidance and information system based on wireless sensor network,” in Proc. IEEE Int. Conf. Inf. Autom., Shenzhen, China, Jun. 2011, pp. 601–605. 
[33]  J.  Yang, J.  Portilla, and T.  Riesgo, “Smart parking service based on wireless sensor networks,” in Proc. IEEE Int. Conf. Ind. Technol. (ICIT), Cape Town, South Africa, Feb. 2013, pp. 6029–6034.  
[34]  M.  Quiñones, V.  González, L.  Quiñones, C.  Valdivieso, and W.  Yaguana, “Design of a smart parking system using wireless sensor network,” in Proc. IEEE Int. Conf. Inf. Autom., Loja, Ecuador, Aug. 2015. 
[35]  X.  Chi, Z.  Liu, J.  Huang, F.  Hong, and H.  Su, “Optimization based motion planning for autonomous parking considering dynamic obstacle: A hierarchical framework,” arXiv, arXiv:2210.13112, Oct. 2023.
[36] D.  Ferguson and A.  Stentz, “Field D*: An interpolation based path planner and replanner,” in Robotics Research: The 11th Int. Symp., Berlin, Germany: Springer, 2007, pp. 239–253. 
[37] J.  W.  Tukey, Exploratory Data Analysis. Reading, MA, USA: Addison Wesley, 1977. 
[38]  J.  Portley, “5 ways smart parking systems improve urban transportation,” KnowHow, May 22 2024. [Online]. Available: https://knowhow.distrelec.com/transportation/5-ways-smart-parking-systems-improve-urban-transportation/. [Accessed: May 2 2025]. 
[39] “Smart parking system: A solution for narrow, high traffic lanes,” LED Traffic Pro, 2025. [Online]. Available: https://www.ledtrafficpro.com/blogs/knowledge-share/smart-parking-system. [Accessed: May 2 2025]. 
[40] R.  T.  Dunphy, “SFpark: Solving parking and traffic problems with pricing,” Urban Land Magazine, Sep. 1 2015. [Online]. Available: https://urbanland.uli.org/infrastructure-transit/sfpark-solving-parking-traffic-problems-pricing. [Accessed: May 2 2025]. 
[41]  K.  Barry, “City parking smartens up with Streetline,” WIRED, Nov. 29 2010.[Online].Available: https://www.wired.com/2010/11/city-parking-smartens-up-with-streetline/. [Accessed: May 2 2025]. 
[42]  H.  Choset et al., Principles of Robot Motion: Theory, Algorithms, and Implementations. Cambridge, MA, USA: MIT Press, 2005.