由於資訊科技的繁榮發展，車輛路徑問題對於設計者而言有了更多可實行
的方式來達成他們的構想。一個良好的路徑規劃演算法不僅可以有效地解決路
徑選擇問題，同時還可能緩解由交通壅塞、管制或事故等狀況所引起的交通問
題。除了考慮歐幾里德距離，道路的條件狀況和交通流量的影響也可以用於提
高搜索演算法運行的有效性。大多數的路徑規劃演算法是專為汽車或其他大型
車輛所開發的，然而在許多人口稠密型國家中，特別是在於一些亞洲的城市，
常常可以觀察到由於複雜之交通流量而引起的交通壅塞現象。因此本論文針對
在台灣國內高度汽機車混合車流情況下的機車族，開發了一種基於兩段式左轉
和具重複路由策略的旅行導航系統。本系統可以利用車輛的行駛資訊和道路運
行狀況來改善車輛旅行效率。提出的演算法能夠定期地檢查所規劃路線其所能
持續的有效性，考量交通流量的影響與交通號誌控制的因素，為每個目標機車
尋找出最快速的行經路徑。模擬結果顯示，本導航系統可以有效地為在市區環
境中的機車族來改善他們的實際旅行時間。此種方法顯著的減少了在複雜交叉
路口中的等待通行時間。

Due to the prosperity of information technology, vehicle routing problems have much more feasible manner for designers to achieve their ideas. The favorable path planning algorithms can effectively not only solve the path selection but also ease up many traffic problems, such as the traffic congestion, the traffic control, and the traffic accidents, especially in heavy urban environment. In addition to the Euclidean distance, the road conditions and influence of traffic flow could be used for improving effectiveness of search algorithm as well. Most of path planning algorithms are developed for cars or other large vehicles. In many densely populated countries, however, traffic congestion is commonly observable due to the complex traffic flow, especially in some Asian cities. Therefore, this thesis develops a novel travel navigation system based on hook turn constraint and rerouting policy for scooters with the heavy scooter–vehicle mixed flows in Taiwan. The system can improve the travel efficiency by using the vehicular driving information and the on-road conditions. The proposed algorithm can periodically check the continuous efficiency of the routes, the traffic flow impact, and the traffic light control factors to search for the fastest route for each task scooter. The simulation results show that the navigation system can effectively reduce the travel time for scooter riders in urban environments. This approach substantially decreases the waiting time at the complex intersections.

[1] Y. Hu, J. Ou, and L. Hu, “A Review of Research on Traffic Conflicts Based on Intelligent Vehicles Perception Technology,” in International Conference on Advances in Construction Machinery and Vehicle Engineering (ICACMVE), May. 2019, pp. 1–6.
[2] Road traffic statistics. [Online]. Available: https://roadtraffic.dft.gov.uk/summary, 2020.
[3] Taiwan’s traffic statistics. [Online]. Available: https://stat.motc.gov.tw/mocdb/stmain.jsp?sys=100, 2020.
[4] K. Irawan, R. Yusuf, and A. S. Prihatmanto, “A Survey on Traffic Flow Prediction Methods,” in International Conference on Interactive Digital Media (ICIDM), Dec. 2020, pp. 1–4.
[5] L. Zhi, X. Zhou, and J. Zhao, “Vehicle Routing for Dynamic Road Network Based on Travel Time Reliability,” IEEE Access, vol. 8, pp. 190 596–190 604, Oct. 2020.
[6] S. Sinha, M. K. Nirala, S. Ghosh, and S. K. Ghosh, “Hybrid Path Planner for Efficient Navigation in Urban Road Networks through Analysis of Trajectory Traces,” in International Conference on Pattern Recognition (ICPR), Aug. 2018, pp. 1–6.
[7] C. Wu, S. Zhou, and L. Xiao, “Dynamic Path Planning Based on Improved Ant Colony Algorithm in Traffic Congestion,” IEEE Access, vol. 8, pp. 180 773–180 783, Oct. 2020.
[8] O. T. T. Kim, V. Nguyen, S. I. Moon, and C. S. Hong, “Finding realistic shortest path in road networks with lane changing and turn restriction,” in Asia-Pacific Network Operations and Management Symposium (APNOMS), Oct. 2016, pp. 1–4.
[9] L. Qi and M. Schneider, “Trafforithm: A Traffic-aware Shortest Path Algorithm in Real Road Networks with Traffic Influence Factors,” in IEEE Transactions on Knowledge and Data Engineering, Apr. 2015, pp. 1–6.
[10] M. S. Shirazi and B. T. Morris, “Looking at Intersections: A Survey of Intersection Monitoring, Behavior and Safety Analysis of Recent Studies,” IEEE Transactions on Intelligent Transportation Systems, vol. 18, pp. 4–24, Jan. 2017.
[11] Z. Cai, X. Cui, X. Su, Q. Mi, L. Guo, and Z. Ding, “A Novel Vector-Based Dynamic Path Planning Method in Urban Road Network,” in IEEE Access, vol. 8, Dec. 2019, pp. 9046–9060.
[12] G. Sun, Y. Zhang, H. Yu, X. Du, and M. Guizani, “Intersection Fog-Based Distributed Routing for V2V Communication in Urban Vehicular Ad Hoc Networks,” IEEE Transactions on Intelligent Transportation Systems, vol. 6, pp. 2409–2426, June. 2020.
[13] R. Zhong, J. Xiong, Y. Huang, A. Sumalee, A. H. F. Chow, and T. Pan, “Dynamic System Optimum Analysis of Multi-Region Macroscopic Fundamental Diagram Systems With State-Dependent Time-Varying Delays,” IEEE Transactions on Intelligent Transportation Systems, vol. 21, pp. 4000–4016, June. 2020.
[14] C.-L. Lan and G.-L. Chang, “A Traffic Signal Optimization Model for Intersections Experiencing Heavy Scooter–Vehicle Mixed Traffic Flows,” IEEE Transactions on Intelligent Transportation Systems, vol. 16, pp. 1771–1783, Aug. 2015.
[15] F. Gunes, S. Bayrakli, and A. H. Zaim, “Flow Characteristics of Traffic Flow at Signalized Intersections and Performance Comparison using Queueing Theory,” in International Symposium on Multidisciplinary Studies and Innovative Technologies (ISMSIT), Oct. 2020, pp. 1–9.
[16] X. T. Cui, X. S. Li, X. L. Zheng, X. Y. Zhang, L. Zhao, and J. Zhang, “Research on Traffic Characteristics of Signal Intersections with Mixed Traffic Flow,” in International Conference on Intelligent Transportation Engineering (ICITE), Sept. 2020, pp. 1–7.
[17] Z. Cao, L. Lu, C. Chen, and X. Chen, “Modeling and Simulating Urban Traffic Flow Mixed With Regular and Connected Vehicles,” IEEE Access, vol. 9, pp. 10 392– 10 399, Jan. 2020.
[18] O. Dib, M.-A. Manier, and L. Moalic, “Advanced Modeling Approach for Computing Multicriteria Shortest Paths in Multimodal Transportation Networks ,” in IEEE International Conference on Intelligent Transportation Engineering (ICITE), Aug. 2016, pp. 1–5.
[19] M. Owais and A. Alshehri, “Pareto Optimal Path Generation Algorithm in Stochastic Transportation Networks,” IEEE Access, vol. 8, pp. 58 970–58 981, Mar. 2020.
[20] H. Wen, Y. Lin, and J. Wu, “Co-Evolutionary Optimization Algorithm Based on the Future Traffic Environment for Emergency Rescue Path Planning,” IEEE Access, vol. 8, pp. 148 125–148 135, Oct. 2020.
[21] SUMO Simulation of Urban MObility. [Online]. Available: http://www.dlr.de/ts/en/desktopdefault.aspx/tabid-9883/16931 read-41000/, 2020.
[22] The registration number of motor vehicle in Tainan City . [Online]. Available: https://www.taiwanstat.com/vp-tainan/traffic report.html, 2020.