本研究以時間相依的路網為背景，結合近年來逐漸興起的共享交通運具、以及人們通勤時常使用的大眾運輸系統，提出結合上述三個主要背景的最快路徑規劃問題。我們發現在進行路徑規劃時，傳統的研究及服務上皆未能同時考慮時間相依路網、共享運具、大眾運輸系統三種不同特性。因此在本研究之中，我們基於過去研究的時間相依路網最快路徑規劃演算基礎上，更進一步提出結合轉乘共享車輛以及大眾運輸系統的演算法，使得查詢者獲得能夠最早抵達目的地的行程方案。

在本文之中我們提出三個不同的演算法，我們首先提出Basic Route Planning Algorithm (BPRA)以窮舉法尋找最佳解，並且進一步基於BRPA的基礎提出更具效率同時具有精確性的Advanced Pruning Algorithm (APA)演算法。為了克服時間相依路網上進行行程規劃耗時的問題，我們依照網格節點密度進行路網的劃分並且建立網格索引，提出Grid Index Algorithm (GIA)演算法，使得查詢的整體過程更具效率。並且在研究的最後，我們以不同面向的實驗驗證以上三個演算法的效能。

This research is based on the time-dependent road network, combined with shared transportation vehicles and public transportation systems, and proposes the fastest path planning problem that combines the above three main backgrounds. We found that traditional research and services failed to consider the three different characteristics of time-dependent road networks, shared transportation systems, and public transportation systems at the same time when planning routes. Therefore, in this research, based on the calculation of the fastest path planning of the time-dependent road network in the past, we further propose an algorithm that combines interchange shared vehicles and public transportation systems. This allows the inquirer to obtain the itinerary plan that can arrive at the destination as early as possible.

In this article we propose three different algorithms. We first proposed the Basic Route Planning Algorithm (BPRA) to find the best solution by exhaustive methods. And further based on BRPA, a more efficient and accurate Advanced Pruning Algorithm (APA) algorithm is proposed. In order to overcome the time-consuming problem of executing the itinerary planning algorithm in the time-dependent road network. We divide the road network according to the density of grid nodes and build grid indexes. The Grid Index Algorithm (GIA) algorithm is further proposed to make the query process more efficient. And we use different aspects of experiments to verify the effectiveness of the above three algorithms.

[1] D. Canales et al., “Connected Urban Growth: Public-Private Collaborations for Transforming Urban Mobility.” [Online]. Available: http://newclimateeconomy.net/content/cities-working-papers.
[2] UNU Motor, “Global Moped Sharing Market Report 2020.”
[3] K. Baek, H. Lee, J.-H. Chung, and J. Kim, “Electric scooter sharing: How do people value it as a last-mile transportation mode?,” Transportation Research Part D: Transport and Environment, vol. 90, p. 102642, Jan. 2021, doi: 10.1016/j.trd.2020.102642.
[4] Y. Wang, G. Li, and N. Tang, “Querying shortest paths on time dependent road networks,” Proceedings of the VLDB Endowment, vol. 12, no. 11, pp. 1249–1261, 2018, doi: 10.14778/3342263.3342265.
[5] Y. Yang, H. Li, J. Wang, Q. Hu, X. Wang, and M. Leng, “A novel index method for k nearest object query over time-dependent road networks,” Complexity, vol. 2019, 2019, doi: 10.1155/2019/4829164.
[6] F. Luan, Q. Li, K. Cao, and L. Wang, “Multi-constrained dominate route queries in time-dependent road networks,” Communications in Computer and Information Science, vol. 945, no. 611602323, pp. 135–148, 2018, doi: 10.1007/978-981-13-2922-7_9.
[7] Y. Yuan, X. Lian, G. Wang, L. Chen, Y. Ma, and Y. Wang, “Weight-constrained route planning over time-dependent graphs,” Proceedings - International Conference on Data Engineering, vol. 2019-April, no. 1, pp. 914–925, 2019, doi: 10.1109/ICDE.2019.00086.
[8] J. Sauer, D. Wagner, and T. Zündorf, “Faster Multi-Modal Route Planning with Bike Sharing Using ULTRA,” Leibniz International Proceedings in Informatics, LIPIcs, vol. 160, no. 16, pp. 1–14, 2020, doi: 10.4230/LIPIcs.SEA.2020.16.
[9] P. Cheng, C. Xu, P. Lebreton, Z. Yang, and J. Chen, “TERP: Time-event-dependent route planning in stochastic multimodal transportation networks with bike sharing system,” IEEE Internet of Things Journal, vol. 6, no. 3, pp. 4991–5000, 2019, doi: 10.1109/JIOT.2019.2894511.
[10] O. Dib, M. A. Manier, L. Moalic, and A. Caminada, “A multimodal transport network model and efficient algorithms for building advanced traveler information systems,” Transportation Research Procedia, vol. 22, pp. 134–143, 2017, doi: 10.1016/j.trpro.2017.03.020.
[11] H. Huang, D. Bucher, J. Kissling, R. Weibel, and M. Raubal, “Multimodal Route Planning with Public Transport and Carpooling,” IEEE Transactions on Intelligent Transportation Systems, vol. 20, no. 9, pp. 3513–3525, 2019, doi: 10.1109/TITS.2018.2876570.
[12] M. Gendreau, G. Ghiani, and E. Guerriero, “Time-dependent routing problems: A review,” Computers and Operations Research, vol. 64. Elsevier Ltd, pp. 189–197, Jul. 02, 2015, doi: 10.1016/j.cor.2015.06.001.
[13] B. Ding, J. X. Yu, and L. Qin, “Finding time-dependent shortest paths over large graphs,” in Advances in Database Technology - EDBT 2008 - 11th International Conference on Extending Database Technology, Proceedings, 2008, pp. 205–216, doi: 10.1145/1353343.1353371.
[14] B. C. Dean, “Continuous-Time Dynamic Shortest Path Algorithms,” Electrical Engineering, p. 116, 1999.
[15] Y. Wang and N. Tang, “Querying Shortest Paths on Time Dependent Road Networks services . Consider a group of tourists shopping in the Desert,” vol. 12, no. 11.
[16] O. Dib, M. A. Manier, L. Moalic, and A. Caminada, “A multimodal transport network model and efficient algorithms for building advanced traveler information systems,” Transportation Research Procedia, vol. 22, no. 2016, pp. 134–143, 2017, doi: 10.1016/j.trpro.2017.03.020.
[17] Demiryurek U, Banaei-Kashani F, Shahabi C, Ranganathan A. Online computation of fastest path in time-dependent spatial networks. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 2011;6849 LNCS:92-111. doi:10.1007/978-3-642-22922-0_7
[18] M. H. Ahmadi and V. Haghighatdoost, “General Time-Dependent Sequenced Route Queries in Road Networks,” in 2017 IEEE 15th Intl Conf on Dependable, Autonomic and Secure Computing, 15th Intl Conf on Pervasive Intelligence and Computing, 3rd Intl Conf on Big Data Intelligence and Computing and Cyber Science and Technology Congress(DASC/PiCom/DataCom/CyberSciTech), Nov. 2017, pp. 949–956, doi: 10.1109/DASC-PICom-DataCom-CyberSciTec.2017.158.
[19] A. Shaheen, “UC Berkeley Recent Work Title Shared Micromoblity Policy Toolkit: Docked and Dockless Bike and Scooter Sharing,” 2019, doi: 10.7922/G2TH8JW7.
[20] N. F. Galatoulas, K. N. Genikomsakis, and C. S. Ioakimidis, “Spatio-temporal trends of e-bike sharing system deployment: A review in Europe, North America and Asia,” Sustainability (Switzerland), vol. 12, no. 11, 2020, doi: 10.3390/su12114611.
[21] S. He and K. G. Shin, “Dynamic Flow Distribution Prediction for Urban Dockless E-Scooter Sharing Reconfiguration,” in The Web Conference 2020 - Proceedings of the World Wide Web Conference, WWW 2020, Apr. 2020, pp. 133–143, doi: 10.1145/3366423.3380101.
[22] Y. Pan, R. C. Zheng, J. Zhang, and X. Yao, “Predicting bike sharing demand using recurrent neural networks,” in Procedia Computer Science, 2019, vol. 147, pp. 562–566, doi: 10.1016/j.procs.2019.01.217.
[23] Q. Cai and Z. Fang, “Rebalancing Dockless Bike Sharing Systems,” 2018. [Online]. Available: www.aaai.org.
[24] H. Bast et al., “Route Planning in Transportation Networks,” Apr. 2015, [Online]. Available: http://arxiv.org/abs/1504.05140.
[25] D. Tischner, “Multi-Modal Route Planning in Road and Transit Networks,” Sep. 2018, [Online]. Available: http://arxiv.org/abs/1809.05481.
[26] A. Idri, M. Oukarfi, A. Boulmakoul, K. Zeitouni, and A. Masri, “A new time-dependent shortest path algorithm for multimodal transportation network,” in Procedia Computer Science, 2017, vol. 109, pp. 692–697, doi: 10.1016/j.procs.2017.05.379.