隨著都市化與即時叫車服務的快速發展，動態共乘計程車逐漸成為提升都市交通效率的重要研究方向。近年來的研究已將轉乘機制引進動態共乘系統中，以提升乘客服務率與車輛利用率。然而現有的方法往往依賴預設的轉乘點、路網分區或網格化表徵來縮減搜尋空間，這可能會限制轉乘的靈活性，且隨著路網規模擴大，計算成本也會變得異常高昂。為了解決上述問題，本研究提出一種基於轉乘的動態共乘機制。與現有方法不同的是，本研究將路網中的每個節點均視為潛在的轉乘點，從而消除了對預設轉乘位置的需求。為了控制搜尋空間，本文引入了一種基於橢圓的可行區域過濾機制。系統以候選車輛的當前位置及其下一個排定服務的節點作為橢圓的兩個焦點，並將長軸定義為該候選車輛既定行程中所剩餘的最嚴格時間預算。藉由此橢圓可行區域，可快速判斷在維持既有乘客服務品質（QoS）限制的前提下，該候選車輛是否仍具有足夠的剩餘時間預算，將轉乘乘客直接送達其目的地，從而降低不必要的路徑可行性檢查並提升整體搜尋效率。本研究所提出的方法被整合至滾動式時窗批次更新框架中。在原始的共乘派遣程序完成後，系統會針對未受服務的乘客啟動多車轉乘機制。本研究採用深度優先搜尋來建構可行的轉乘路徑，同時滿足服務品質限制條件，包括乘客等候時間、車內繞道時間以及車輛容量限制。此轉乘機制亦與三種具代表性的共乘派遣方法相結合：單一請求批次指派（SBA）、最佳排程池（OSP）以及考量旅行時間之單一請求批次指派（SRBAT）。實驗結果表明，本研究提出的方法能有效提升乘客服務率與車輛座位利用率，同時減少未受服務的請求數量。在不同的車隊規模，均能取得一致的性能提升，證實了本方法在維持服務品質與計算效率的同時，亦能有效強化動態共乘系統。

With the rapid growth of urbanization and real-time ride-hailing services, dynamic ride-sharing taxis have become an important research topic for improving urban transportation efficiency. Recent studies have incorporated transfer mechanisms into dynamic ride-sharing systems to improve passenger service rates and vehicle utilization. However, existing approaches often rely on predefined transfer points, road network partitioning, or grid-based representations to reduce the search space, which may limit transfer flexibility and become computationally expensive as the road network grows. To address these issues, this study proposes a transfer-based dynamic ride-sharing mechanism. Unlike existing approaches, every node in the road network is treated as a potential transfer point, eliminating the need for predefined transfer locations. To control the search space, an ellipse-based feasible region filtering mechanism is introduced. The current location of a candidate vehicle and its next scheduled service node are used as the two focal points of an ellipse, while the major axis is defined by the most restrictive remaining time budget of the candidate vehicle's existing schedule. Based on this feasible region, the system can efficiently determine whether the candidate vehicle still has sufficient remaining time budget to directly deliver the transfer passenger to the destination without violating the Quality of Service (QoS) constraints of existing passengers, thereby reducing unnecessary route feasibility checks and improving search efficiency. The proposed method is integrated into a rolling horizon batch update framework. After the original ride-sharing dispatching process is completed, a multi-vehicle transfer mechanism is activated for unserved passengers. Depth-First Search (DFS) is employed to construct feasible transfer paths while satisfying service quality constraints, including passenger waiting time, in-vehicle detour time, and vehicle capacity. The proposed transfer mechanism is integrated with three representative ride-sharing dispatching methods: Single-request Batch Assignment (SBA), Optimal Schedule Pool (OSP), and Single-request Batch Assignment with Travel Time Considerations (SRBAT). Experimental results demonstrate that the proposed method improves passenger service rates and vehicle seat utilization while reducing the number of unserved requests. Under different fleet sizes, consistent performance improvements are achieved, confirming the effectiveness of the proposed approach in enhancing dynamic ride-sharing systems while maintaining service quality and computational efficiency.

[1] Abdelmoumène, H., Bencheriet, C. E., Belleili, H., Touati, I., & Zemouli, C. (2024). Dynamic matching optimization in ridesharing system based on reinforcement learning. IEEE Access, 12, 29525-29535.
[2] Al-Abbasi, A. O., Ghosh, A., & Aggarwal, V. (2019). Deeppool: Distributed model-free algorithm for ride-sharing using deep reinforcement learning. IEEE Transactions on Intelligent Transportation Systems, 20(12), 4714-4727.
[3] Alonso-Mora, J., Samaranayake, S., Wallar, A., Frazzoli, E., & Rus, D. (2017). On-demand high-capacity ride-sharing via dynamic trip-vehicle assignment. Proceedings of the National Academy of Sciences, 114(3), 462-467.
[4] Alonso-Mora, J., Wallar, A., & Rus, D. (2017, September). Predictive routing for autonomous mobility-on-demand systems with ride-sharing. In 2017 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS) (pp. 3583-3590). IEEE.
[5] Bathla, K., Raychoudhury, V., Saxena, D., & Kshemkalyani, A. D. (2018, November). Real-time distributed taxi ride sharing. In 2018 21st international conference on intelligent transportation systems (ITSC) (pp. 2044-2051). IEEE.
[6] Chen, X. M., Chen, X., Zheng, H., & Xiao, F. (2021). Efficient dispatching for on-demand ride services: Systematic optimization via Monte-Carlo tree search. Transportation Research Part C: Emerging Technologies, 127, 103156.
[7] Chen, Y. L., Ssu, K. F., & Chang, Y. J. (2020, December). Real-time transfers for improving efficiency of ridesharing services in the environment with connected and self-driving vehicles. In 2020 International Computer Symposium (ICS) (pp. 165-170). IEEE.
[8] Coltin, B., & Veloso, M. (2014, September). Ridesharing with passenger transfers. In 2014 IEEE/RSJ International Conference on Intelligent Robots and Systems (pp. 3278-3283). IEEE.
[9] Cortés, C. E., Matamala, M., & Contardo, C. (2010). The pickup and delivery problem with transfers: Formulation and a branch-and-cut solution method. European Journal of Operational Research, 200(3), 711-724.
[10] Dui, H., & Zhang, C. (2021). Simulations for urban taxi sharing system on routes and passengers with numerical experiments. Journal of Simulation, 15(4), 273-283.
[11] Fu, Z., & Chow, J. Y. (2022). The pickup and delivery problem with synchronized en-route transfers for microtransit planning. Transportation Research Part E: Logistics and Transportation Review, 157, 102562.
[12] Ghandeharioun, Z., & Kouvelas, A. (2023). Real-time ridesharing operations for on-demand capacitated systems considering dynamic travel time information. Transportation Research Part C: Emerging Technologies, 151, 104115.
[13] Haliem, M., Mani, G., Aggarwal, V., & Bhargava, B. (2021). A distributed model-free ride-sharing approach for joint matching, pricing, and dispatching using deep reinforcement learning. IEEE Transactions on Intelligent Transportation Systems, 22(12), 7931-7942.
[14] Hosni, H., Naoum-Sawaya, J., & Artail, H. (2014). The shared-taxi problem: Formulation and solution methods. Transportation Research Part B: Methodological, 70, 303-318.
[15] Hou, Y., Zhong, W., Su, L., Hulme, K., Sadek, A. W., & Qiao, C. (2016). TASeT: Improving the efficiency of electric taxis with transfer-allowed rideshare. IEEE transactions on vehicular technology, 65(12), 9518-9528.
[16] Hua, S., Zeng, W., Liu, X., & Qi, M. (2022). Optimality-guaranteed algorithms on the dynamic shared-taxi problem. Transportation Research Part E: Logistics and Transportation Review, 164, 102809.
[17] Jung, J., Jayakrishnan, R., & Park, J. Y. (2016). Dynamic shared‐taxi dispatch algorithm with hybrid‐simulated annealing. Computer‐Aided Civil and Infrastructure Engineering, 31(4), 275-291.
[18] Lartey, B., Bedada, W., Yan, X., Homaifar, A., Karimoddini, A., & Tunstel, E. (2024). An efficient profit-aware scalable vehicle dispatch framework for on-demand ridesharing. IEEE Transactions on Industrial Cyber-Physical Systems, 2, 542-555.
[19] Laupichler, M., & Sanders, P. (2024). Fast many-to-many routing for dynamic taxi sharing with meeting points. In 2024 Proceedings of the Symposium on Algorithm Engineering and Experiments (ALENEX) (pp. 74-90). Society for Industrial and Applied Mathematics.
[20] Li, C., Parker, D., & Hao, Q. (2021, May). Optimal online dispatch for high-capacity shared autonomous mobility-on-demand systems. In 2021 IEEE International Conference on Robotics and Automation (ICRA) (pp. 779-785). IEEE.
[21] Lokhandwala, M., & Cai, H. (2018). Dynamic ride sharing using traditional taxis and shared autonomous taxis: A case study of NYC. Transportation Research Part C: Emerging Technologies, 97, 45-60.
[22] Lotfi, S., Abdelghany, K., & Hashemi, H. (2019). Modeling framework and decomposition scheme for on‐demand mobility services with ridesharing and transfer. Computer‐Aided Civil and Infrastructure Engineering, 34(1), 21-37.
[23] Luo, H., Bao, Z., Choudhury, F. M., & Culpepper, J. S. (2019). Dynamic ridesharing in peak travel periods. IEEE Transactions on Knowledge and Data Engineering, 33(7), 2888-2902.
[24] Lyu, Y., Lee, V. C., Ng, J. K. Y., Lim, B. Y., Liu, K., & Chen, C. (2019). Flexi-sharing: a flexible and personalized taxi-sharing system. IEEE Transactions on Vehicular Technology, 68(10), 9399-9413.
[25] Ma, Q., Cao, Z., Liu, K., & Miao, X. (2020). QA-Share: Toward an efficient QoS-aware dispatching approach for urban taxi-sharing. ACM Transactions on Sensor Networks (TOSN), 16(2), 1-21.
[26] Ma, S., Zheng, Y., & Wolfson, O. (2014). Real-time city-scale taxi ridesharing. IEEE Transactions on Knowledge and Data Engineering, 27(7), 1782-1795.
[27] Mahmoudi, M., Chen, J., Shi, T., Zhang, Y., & Zhou, X. (2019). A cumulative service state representation for the pickup and delivery problem with transfers. Transportation Research Part B: Methodological, 129, 351-380.
[28] Manjunath, A., Raychoudhury, V., Saha, S., Kar, S., & Kamath, A. (2021). CARE-share: A cooperative and adaptive strategy for distributed taxi ride sharing. IEEE Transactions on Intelligent Transportation Systems, 23(7), 7028-7044.
[29] Masson, R., Lehuédé, F., & Péton, O. (2014). The dial-a-ride problem with transfers. Computers & Operations Research, 41, 12-23.
[30] Ota, M., Vo, H., Silva, C., & Freire, J. (2016). Stars: Simulating taxi ride sharing at scale. IEEE Transactions on Big Data, 3(3), 349-361.
[31] Pfeiffer, C., & Schulz, A. (2022). An ALNS algorithm for the static dial-a-ride problem with ride and waiting time minimization. Or Spectrum, 44(1), 87-119.
[32] Posada, M., Andersson, H., & Häll, C. H. (2017). The integrated dial-a-ride problem with timetabled fixed route service. Public Transport, 9(1), 217-241.
[33] Pouls, M., Meyer, A., & Ahuja, N. (2020, September). Idle vehicle repositioning for dynamic ride-sharing. In International Conference on Computational Logistics (pp. 507-521). Cham: Springer International Publishing.
[34] Santi, P., Resta, G., Szell, M., Sobolevsky, S., Strogatz, S. H., & Ratti, C. (2014). Quantifying the benefits of vehicle pooling with shareability networks. Proceedings of the National Academy of Sciences, 111(37), 13290-13294.
[35] Schulz, A., & Pfeiffer, C. (2024). A Branch-and-Cut algorithm for the dial-a-ride problem with incompatible customer types. Transportation Research Part E: Logistics and Transportation Review, 181, 103394.
[36] Simonetto, A., Monteil, J., & Gambella, C. (2019). Real-time city-scale ridesharing via linear assignment problems. Transportation Research Part C: Emerging Technologies, 101, 208-232.
[37] Singh, A., Al-Abbasi, A. O., & Aggarwal, V. (2021). A distributed model-free algorithm for multi-hop ride-sharing using deep reinforcement learning. IEEE Transactions on Intelligent Transportation Systems, 23(7), 8595-8605.
[38] Stumpe, M., Dieter, P., Schryen, G., Müller, O., & Beverungen, D. (2024). Designing taxi ridesharing systems with shared pick-up and drop-off locations: Insights from a computational study. Transportation Research Part A: Policy and Practice, 183, 104063.
[39] Sun, Y., & Zhang, L. (2018). Potential of taxi-pooling to reduce vehicle miles traveled in Washington, DC. Transportation Research Record, 2672(8), 775-784.
[40] Taxi and Limousine Commission, TLC.(2024) https://www.nyc.gov/site/tlc/about/tlc-trip-record-data.page
[41] Van Engelen, M., Cats, O., Post, H., & Aardal, K. (2018). Enhancing flexible transport services with demand-anticipatory insertion heuristics. Transportation Research Part E: Logistics and Transportation Review, 110, 110-121.
[42] Wang, D., Wang, Q., Yin, Y., & Cheng, T. C. E. (2023). Optimization of ride-sharing with passenger transfer via deep reinforcement learning. Transportation Research Part E: Logistics and Transportation Review, 172, 103080.
[43] Wang, Y., Zheng, B., & Lim, E. P. (2018). Understanding the effects of taxi ride-sharing—A case study of Singapore. Computers, Environment and Urban Systems, 69, 124-132.
[44] Xu, Z., Li, Z., Guan, Q., Zhang, D., Li, Q., Nan, J., ... & Ye, J. (2018, July). Large-scale order dispatch in on-demand ride-hailing platforms: A learning and planning approach. In Proceedings of the 24th ACM SIGKDD international conference on knowledge discovery & data mining (pp. 905-913).
[45] Yao, R., & Bekhor, S. (2020). A Dynamic Tree Algorithm for On-demand Peer-to-peer Ride-sharing Matching. arXiv preprint arXiv:2005.11195.
[46] Yu, H., Raychoudhury, V., & Silwal, S. (2020, January). Dynamic taxi ride sharing using localized communication. In Proceedings of the 21st International Conference on Distributed Computing and Networking (pp. 1-10).
[47] Zhao, M., Yin, J., An, S., Wang, J., & Feng, D. (2018). Ridesharing Problem with Flexible Pickup and Delivery Locations for App‐Based Transportation Service: Mathematical Modeling and Decomposition Methods. Journal of Advanced Transportation, 2018(1), 6430950.
[48] Zhan, X., Szeto, W. Y., & Chen, X. M. (2022). The dynamic ride-hailing sharing problem with multiple vehicle types and user classes. Transportation Research Part E: Logistics and Transportation Review, 168, 102891.
[49] Zhu, M., Liu, X. Y., & Wang, X. (2018). An online ride-sharing path-planning strategy for public vehicle systems. IEEE Transactions on Intelligent Transportation Systems, 20(2), 616-627.
[50] Xie, Z., & Yan, J. (2008). Kernel density estimation of traffic accidents in a network space. Computers, environment and urban systems, 32(5), 396-406.