現今大眾運輸在各個城市十分發達，無論在上班通勤、旅遊等方面都有機會使用，民眾在做行程規劃時，往往會考慮自身要求來選擇不同類型的交通工具來搭乘，所以如何根據使用者不同要求，來安排適合的車輛就是一個實際且重要的課題。
過往的研究大多只考慮同類型的交通工具，但是現實情境應該會有多種交通工具讓使用者選擇，並且使用者等待時間往往被忽略，除此之外，無法根據使用者本身的要求給予不同的車輛安排。若將以上這些要素考量在內，可以更貼近實際情況，並對使用者來說，能被推薦更多元且符合需求的交通工具組合。
在本論文中，我們考慮三種交通工具，分別有公車、城際公車及計程車，並將使用者等待時間考慮在內。民眾通常搭乘交通工具會考慮時間和金額。我們根據城市的交通運輸網路以及上述條件設計一個推薦系統，能提供四種不同適地性查詢，包括總搭乘時間最短、總搭乘金額最少、在固定預算下的總搭乘時間最短以及在固定搭乘時間下的總搭乘時間最短。
我們先提出基礎的方法Baseline Vehicles Arrangement Algorithm(BVAA)，為了提升效率，我們將班表利用索引結構儲存，使資料查詢更有效率，最後提出Time and Cost Vehicles Arrangement Algorithm(TCVAA)，利用Greedy方式減少組合數，更快速找出查詢結果。
我們根據不同查詢及多項條件設計一連串的實驗，並利用台北市、新北市、桃園市裡的公車、城際公車及計程車資料來驗證我們提出的方法，方法包括BVAA、BVAAI(使用索引結構的BVAA)以及TCVAA。

Nowadays, public transportation is well developed in many cities, and people can use it for work, trip planning, etc. When people plan their trips, they often consider their own requirements to choose different types of transportation to take. Thus, how to arrange suitable vehicles according to users' different requirements is a practical and important issue.
Most of the previous studies only consider single type of transportation, but in reality, there are multiple transportation options for users, and the waiting time of users is often ignored. If these factors are taken into account, it is possible to get closer to the actual situation and to recommend a more diverse and demand-driven combination of transportation for users.
In this thesis, we consider three types of transportation, namely bus, intercity bus and taxi, and take into account the waiting time of users. We design a recommendation system that takes into account the above conditions based on the city's transportation network and can provide results based on four different location-based queries, including the shortest total travel time, the lowest total riding fare, the shortest total travel time with a fixed budget, and the lowest total riding fare with a fixed travel time.
We first propose the basic method Baseline Vehicles Arrangement Algorithm (BVAA). To enhance the efficiency, we store the schedule of transportation with index structure to make the data query more efficient. Finally, we propose the Time and Cost Saving Vehicles Arrangement Algorithm (TCVAA) to reduce the number of combinations by using the Greedy method to find the query results more quickly.
We design several experiments based on different queries and various parameters, and use the data of buses, intercity buses in Taipei City, New Taipei City, and Taoyuan City to verify our proposed methods, including BVAA, BVAAI (BVAA with index structure), and TCVAA.

Qixu Gong, Huiping Cao , Parth Nagarkar, "Skyline Queries Constrained by Multi-Cost Transportation Networks", ICDE, 2019.
Jiashun Liu, Yu Yuan, Feng Li, Wei Ding, "Bus Trip Planning Service Based On Real Time Data", Annual SRII Global Conference, 2011.
Jing Fan, Jinting Xu, Chenyu Hou, Bin Cao, Tianyang Dong, Shiwei Cheng, "Uroad: An Efficient Algorithm for Large-scale Dynamic Ridesharing Service", ICWS, 2018.
Shuo Ma, Yu Zheng, Senior Member, IEEE, and Ouri Wolfson, Fellow, IEEE, "Real-Time City-Scale Taxi Ridesharing" , TKDE, 2015.
Guo, D., Zhao, Z., Xu, W., Lan, J., Zhang, T., Liu, S., Li, J. and Zhou, Y., 2015. "How to Find a Comfortable Bus Route -Towards Personalized Information Recommendation Services.", Data Science Journal, 14, p.14. DOI: http://doi.org/10.5334/dsj-2015-014
Mehdi Sharifzadeh, Mohammad Kolahdouzan, Cyrus Shahabi, "The Optimal Sequenced Route Query.", VLDB Journal, 2007.
Nikhil Bansal, Avrim Blum, Shuchi Chawla, Adam Meyerson, "Approximation Algorithms for Deadline-TSP and Vehicle Routing with Time-Windows." In: Proc. of FOCS, 2004.
Pranali Yawalkar, Sayan Ranu, "Route Recommendations on Road Networks for Arbitrary User Preference Functions", ICDE, 2019.
Yuya Sasaki , Yoshiharu Ishikawa , Yasuhiro Fujiwara, Makoto Onizuka, "Sequenced Route Query with Semantic Hierarchy", EDBT, 2018.
Robert Geisberger, Moritz Kobitzsch and Peter Sanders, "Route Planning with Flexible Objective Functions", In Proceedings of the 12th Workshop on Algorithm Engineering and Experiments (ALENEX'10), pages 124–137. SIAM, 2010.
Siqiang Luo, Reynold Cheng, Ben Kao, Xiaokui Xiao,Shuigeng Zhou, Jiafeng Hu, "ROAM: A Fundamental Routing Query on Road Networks with Efficiency," in TKDE, vol.32, no.8, Aug.2020.
E. W. Dijkstra, "A note on two problems in connexion with graphs", Numerische Mathematik, 1:269–271, 1959.
Hart, P., Nilsson, N. Raphael, B., 1968. "A Formal Basis for the Heuristic Determination of Minimum Cost Paths". IEEE Transactions on Systems Science and Cybernetics, 4(2), pp.100–107.
Ittai Abraham, Daniel Delling, Andrew V Goldberg, and Renato F Werneck.2011. "A hub-based labeling algorithm for shortest paths in road networks". In SEA. 230–241.
Ittai Abraham, Daniel Delling, Andrew V Goldberg, and Renato F Werneck.2012. "Hierarchical hub labelings for shortest paths". In ESA. 24–35
Muhammad Farhan, Qing Wang, Yu Lin, Brendan McKay, "A Highly Scalable Labelling Approach for Exact Distance Queries in Complex Networks", in Proceedings of the22nd International Conference on Extending Database Technology (EDBT), March26-29, 2019, ISBN 978-3-89318-081-3 on OpenProceedings.org
Guttman, A.: "R-trees: A dynamic index structure for spatial searching". In: Proc. of ACM Management of Data (SIGMOD), Massachusetts, USA, 18–21 June 1984, pp. 47–57
S.VSaltenis, C. S. Jensen, S. T. Leutenegger, and M. A. Lopez. "Indexing the positions of continuously moving objects". SIGMOD, 29(2):331–342, May 2000.
D. Pfoser, C. S. Jensen, Y. Theodoridis, et al. "Novel approaches to the indexing of moving object trajectories". In Proceedings of VLDB,pages395–406, 2000.
R. Zhong, G. Li, K. Tan, and L. Zhou. G-tree: an efficient index for KNN search on road networks. In CIKM, pages 39–48, 2013.
R. Zhong, G. Li, K. L. Tan, L. Zhou, and Z. Gong. "G-tree: An efficient and scalable index for spatial search on road networks". TKDE, 27(8):2175–2189, Aug 2015.
Zijian Li, Lei Chen, Yue Wang, "G∗-Tree: An Efficient Spatial Index on Road Networks", ICDE, 2019.
V-tree:Efficient knn search on moving objects with road-network constraints. In Tsinghua Technical Report, http://dbgroup.cs.tsinghua.edu.cn/ligl/vtree.pdf.
Radi Muhammad Reza, Mohammed Eunus Ali, Muhammad Aamir Cheema,"The Optimal Route and Stops for a Group of Users in a Road Network", In SIGSPATIAL'17, November 7–10, 2017.
T. A. J. Nicholson, "Finding the shortest route between two points in a network" Comput. J., vol. 9, no. 3, pp. 275–280, 1966.
E. Ahmadi and M. A. Nascimento, "A Mixed Breadth-Depth First Search Strategy for Sequenced Group Trip Planning Queries," 2015 16th IEEE International Conference on Mobile Data Management, 2015, pp. 24-33, doi: 10.1109/MDM.2015.49.
F. Aklam and W. Osborn, "Dynamic Group Trip Planning Queries in Spatial Databases," 2020 IEEE Canadian Conference on Electrical and Computer Engineering (CCECE), 2020, pp. 1-6, doi: 10.1109/CCECE47787.2020.9255682.
E. Ahmadi and M. A. Nascimento, "IBS: An Efficient Stateful Algorithm for Optimal Sequenced Group Trip Planning Queries," 2017 18th IEEE International Conference on Mobile Data Management (MDM), 2017, pp. 212-221, doi: 10.1109/MDM.2017.36.
L. R. Celsi, A. Di Giorgio, R. Gambuti, A. Tortorelli and F. Delli Priscoli, "On the many-to-many carpooling problem in the context of multi-modal trip planning," 2017 25th Mediterranean Conference on Control and Automation (MED), 2017, pp. 303-309, doi: 10.1109/MED.2017.7984135.
J. Mu, J. Zhang, T. Zhang, B. Zhao and W. Zhang, "Online Trip Planning for Public Bike Systems," 2020 IEEE 17th International Conference on Mobile Ad Hoc and Sensor Systems (MASS), 2020, pp. 515-523, doi: 10.1109/MASS50613.2020.00069.
Li, Ke and Chen, Lisi and Shang, Shuo, "Towards Alleviating Traffic Congestion: Optimal Route Planning for Massive-Scale Trips," Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, 2020, pp. 3400--3406, doi: 10.24963/ijcai.2020/470.