現今因為預約計程車App的盛行，使人們可以更方便去提前預訂計程車。關於計程車路線推薦的研究有很多，對司機而言，一個好的乘車路線規劃可以提高計程車的載客率並提高收入，並且減少讓乘客的等待時間的可能性。在本論文中，不同於一般單一目標的路線推薦，例如，在最短的時間或最短的距離內找到下一個乘客，我們的研究情況是當計程車已被乘客事先預訂時，如何讓計程車有效利用預約時間之前的空閒時段去尋找其他乘客維持穩定的載客率提高收入，同時必須讓計程車可以準時到達預約地點。因此，我們提出了一種稱為 Search Pair Algorithm（SPA）的啟發式演算法，該演算法考慮了計程車動態路線推薦的多準則因素，以實現赴約預定成功率和載客率之間的權衡。SPA 結合了路網資訊、深度學習預測模型、即時反饋讓計程車可以及時修改路線，以及預約限制條件的考量。在實驗中，我們利用紐約計程車的上下車時空大數據，建立了一個多代理模擬 (multi-agent simulation) 實驗來驗證計程車與乘客之間的真實互動。與缺乏交互性和隨機性的一般歷史數據驗證方法相比，我們的模擬實驗更貼近真實世界的情況。我們的 SPA 演算法在此模擬中，相較於其他方法有達到柏拉圖最優 (Pareto-optimal)，並且擁有 89% 較高的成功率，可以在極小風險失約的情況下，達到最高的綜合分數。

Nowadays, the prevalence of taxi-hailing apps allows people to book taxis in advance. Therefore, much research focuses on taxi route recommendations. An ideal route can increase the taxi occupancy rate and reduce the probability of missing the appointment for taxi drivers. Unlike the current route recommendation that optimizes a single goal, such as finding the next customer in the shortest time or the shortest distance, this paper focuses on making use of the free time to seek customers before reservation time when the taxi has been booked in the future. Precisely, the goal is that maintain the occupancy rate to bring the income and need to arrive at the reservation location on time successfully. Therefore, we propose a heuristic algorithm called Search Pair Algorithm (SPA), considering multiple factors for taxi dynamic route recommendation to achieve a trade-off between the success rate and occupancy rate. SPA combines the road information, the prediction of the deep learning model, the timely feedback, and the constraints of reservation time and location. Our experiments use New York taxi trip data and establish a multi-agent simulation testbed to simulate the real interaction between the taxis and the customers. Compared with the general verification based on historical data, which lacks interaction and stochasticity, our simulation experiment is highly closer to the real-world situation. In this simulation, our SPA algorithm has achieved Pareto-optimal compared to other baselines, and has a higher success rate of 89%, which can achieve the highest comprehensive score with a very small risk of missing appointments.

[1] Kevin Buchin, Irina Kostitsyna, Bram Custers, and Martijn Struijs, 2019. A Sampling-based Strategy for Distributing Taxis in a Road Network for Occupancy Maximization (GIS Cup). In Proceedings of the Proceedings of the 27th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (Chicago, IL, USA2019), Association for Computing Machinery, 616–619.
[2] Shih-Fen Cheng and Thi Duong Nguyen, 2011. Taxisim: A multiagent simulation platform for evaluating taxi fleet operations. In 2011 IEEE/WIC/ACM International Conferences on Web Intelligence and Intelligent Agent Technology IEEE, 14-21.
[3] OpenStreetMap Contributors, 2017. Planet Dump Retrieved from https://planet.osm.org. URL: https://planet.openstreetmap.org.
[4] Edsger W Dijkstra, 1959. A note on two problems in connexion with graphs. Numerische mathematik 1, 1, 269-271.
[5] Jie-Yu Fang, F. Lin, and Hsun-Ping Hsieh, 2020. A Multi-criteria System for Recommending Taxi Routes with an Advance Reservation. In ECML/PKDD.
[6] Nandani Garg and Sayan Ranu, 2018. Route recommendations for idle taxi drivers: Find me the shortest route to a customer! In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, 1425-1434.
[7] Qian Ge and Daisuke Fukuda, 2016. Updating origin–destination matrices with aggregated data of GPS traces. Transportation Research Part C: Emerging Technologies 69, 291-312.
[8] Josep Maria Salanova Grau and Miquel Angel Estrada Romeu, 2015. Agent based modelling for simulating taxi services. Procedia Computer Science 52, 902-907.
[9] Peter E Hart, Nils J Nilsson, and Bertram Raphael, 1968. A formal basis for the heuristic determination of minimum cost paths. IEEE transactions on Systems Science and Cybernetics 4, 2, 100-107.
[10] Shenggong Ji, Zhaoyuan Wang, Tianrui Li, and Yu Zheng, 2020. Spatio-temporal feature fusion for dynamic taxi route recommendation via deep reinforcement learning. Knowledge-Based Systems 205, 106302.
[11] Fandel Lin, Hsun Ping Hsieh, and Jie Yu Fang, 2021. A Route-Affecting Region Based Approach for Feature Extraction in Transportation Route Planning. In European Conference on Machine Learning and Knowledge Discovery in Databases, ECML PKDD 2020 Springer Science and Business Media Deutschland GmbH, 275-290.
[12] Junfeng Ma, James D Harstvedt, Raed Jaradat, and Brian Smith, 2020. Sustainability driven multi-criteria project portfolio selection under uncertain decision-making environment. Computers & Industrial Engineering 140, 106236.
[13] Luis Moreira-Matias, Joao Gama, Michel Ferreira, Joao Mendes-Moreira, and Luis Damas, 2013. Predicting taxi–passenger demand using streaming data. IEEE Transactions on Intelligent Transportation Systems 14, 3, 1393-1402.
[14] Luís Moreira-Matias, João Gama, Michel Ferreira, João Mendes-Moreira, and Luis Damas, 2016. Time-evolving OD matrix estimation using high-speed GPS data streams. Expert systems with Applications 44, 275-288.
[15] Yuhua Qiu and Xiaolong Xu, 2018. RPSBPT: A Route Planning Scheme with Best Profit for Taxi. In 2018 14th International Conference on Mobile Ad-Hoc and Sensor Networks (MSN) IEEE, 121-126.
[16] Saurav Ranjit, Apichon Witayangkurn, Masahiko Nagai, and Ryosuke Shibasaki, 2018. Agent-based modeling of taxi behavior simulation with probe vehicle data. ISPRS International Journal of Geo-Information 7, 5, 177.
[17] Xingjian Shi, Zhourong Chen, Hao Wang, Dit-Yan Yeung, Wai-kin Wong, and Wang-chun Woo, 2015. Convolutional LSTM Network: a machine learning approach for precipitation nowcasting. In Proceedings of the Proceedings of the 28th International Conference on Neural Information Processing Systems - Volume 1 (Montreal, Canada2015), MIT Press, 802–810.
[18] Peer-Olaf Siebers and Uwe Aickelin, 2008. Introduction to multi-agent simulation. In Encyclopedia of decision making and decision support technologies IGI Global, 554-564.
[19] Robert J Szczerba, Peggy Galkowski, Ira S Glicktein, and Noah Ternullo, 2000. Robust algorithm for real-time route planning. IEEE Transactions on Aerospace and Electronic Systems 36, 3, 869-878.
[20] Hao Wang, Ruey Long Cheu, and Der-Horng Lee, 2014. Intelligent taxi dispatch system for advance reservations. Journal of Public Transportation 17, 3, 8.
[21] Huaxiu Yao, Xianfeng Tang, Hua Wei, Guanjie Zheng, and Zhenhui Li, 2019. Revisiting spatial-temporal similarity: A deep learning framework for traffic prediction. In Proceedings of the AAAI conference on artificial intelligence, 5668-5675.
[22] Huaxiu Yao, Fei Wu, Jintao Ke, Xianfeng Tang, Yitian Jia, Siyu Lu, Pinghua Gong, Jieping Ye, and Zhenhui Li, 2018. Deep multi-view spatial-temporal network for taxi demand prediction. In Proceedings of the AAAI Conference on Artificial Intelligence.
[23] Xinlian Yu, Song Gao, Xianbiao Hu, and Hyoshin Park, 2019. A Markov decision process approach to vacant taxi routing with e-hailing. Transportation Research Part B: Methodological 121, 114-134.
[24] Jing Yuan, Yu Zheng, Liuhang Zhang, XIng Xie, and Guangzhong Sun, 2011. Where to find my next passenger. In Proceedings of the 13th international conference on Ubiquitous computing, 109-118.
[25] Chizhan Zhang, Fenghua Zhu, Xiao Wang, Leilei Sun, Haina Tang, and Yisheng Lv, 2020. Taxi Demand Prediction Using Parallel Multi-Task Learning Model. IEEE Transactions on Intelligent Transportation Systems.
[26] Junbo Zhang, Yu Zheng, and Dekang Qi, 2017. Deep spatio-temporal residual networks for citywide crowd flows prediction. In Proceedings of the AAAI Conference on Artificial Intelligence.
[27] Kai Zhao, Denis Khryashchev, Juliana Freire, Claudio Silva, and Huy Vo, 2016. Predicting taxi demand at high spatial resolution: Approaching the limit of predictability. In 2016 ieee international conference on Big data (big data) IEEE, 833-842.
[28] Yirong Zhou, Jun Li, Hao Chen, Ye Wu, Jiangjiang Wu, and Luo Chen, 2020. A spatiotemporal attention mechanism-based model for multi-step citywide passenger demand prediction. Information Sciences 513, 372-385.
[29] Hongzi Zhu, Minglu Li, Luoyi Fu, Guangtao Xue, Yanmin Zhu, and Lionel M Ni, 2010. Impact of traffic influxes: Revealing exponential intercontact time in urban vanets. IEEE Transactions on Parallel and Distributed Systems 22, 8, 1258-1266.