進階搜尋


   電子論文尚未授權公開,紙本請查館藏目錄
(※如查詢不到或館藏狀況顯示「閉架不公開」,表示該本論文不在書庫,無法取用。)
系統識別號 U0026-0907202021442300
論文名稱(中文) 基於預約應用深度學習之計程車載客路徑推薦系統
論文名稱(英文) How to Optimize the Profit of Taxi Routes with an Advance Reservation? J*: A Multi-Criteria Approach Using Spatial-Temporal Predictions
校院名稱 成功大學
系所名稱(中) 電腦與通信工程研究所
系所名稱(英) Institute of Computer & Communication
學年度 108
學期 2
出版年 109
研究生(中文) 方婕瑀
研究生(英文) Jie-Yu Fang
學號 Q36074170
學位類別 碩士
語文別 英文
論文頁數 41頁
口試委員 指導教授-解巽評
口試委員-帥宏翰
口試委員-駱弘毅
口試委員-李家岩
中文關鍵字 路徑規劃  計程車服務  啟發式搜尋  多面向路徑規劃  深度學習應用  時空間分析與預測 
英文關鍵字 Route Recommendation  Taxi Service  Heuristic Search  Multi-criteria Search  Deep Learning  Spatial-Temporal Prediction 
學科別分類
中文摘要 隨著城市的開發與進步,計程車服務也變得越來越多元化以滿足使用者們的需求。計程車預約的需求不斷增長,如何在有預約的情形下,設計一條載客路徑來提升計程車司機的利潤已經引起關注。然而在過去的情形下,計程車司機在面對預約需求時往往需要提前空車一段時間來避免錯失預約客人,因此變相的提高預約服務價格,造成供需不平衡的狀況。因此,我們提出一個路徑規劃框架,內容包含了深度學習模型的應用、路網資訊的建置以及多面向路徑規劃演算法,目的是在有預約客人的情形下,規劃一條載客路徑來提升載客率並且同時讓司機準時抵達預約終點。此路徑規劃框架包含了四大模組,首先我們建立一個以網格為基底的搜尋網路,他能降低搜尋量,並且提供在做路徑規劃時必要的資訊例如地區之間的通勤距離以及通勤時間。再來是兩個預測模型的應用,我們採用兩個深度學習方法來預測載客需求,一個是載客機率預測模型,能預測城市中的載客機率,另一個則是目的地機率預測模型,目的是預測乘客的目的地。最後是集大成之路徑規劃演算法(J* 演算法),此演算法應用了前三大模組提供的資訊來做路徑規劃,並且以一個啟發式函式來計算候選網格的分數。結果顯示,我們提出的方法與傳統路徑規劃方法比較起來更加地有效率且穩健,並且我們提出的方法能有效地降低搜尋運算量。在我們的認知之下,這是第一份針對在有預約客人的情形下,關於提升載客利潤的載客路徑規劃研究。
英文摘要 The diversity of taxi services has grown with the development of cities. As the demand of taxi reservation services has increased, the strategies of how to increase the income of taxi drivers with advanced service have attracted attention. However, the demand is usually unmet due to the imbalance of profit. In this paper, we propose a multi-criteria route recommendation approach that considers real-time spatial-temporal predictions and traffic network information, aiming to optimize a taxi driver’s profit when the driver has an advance reservation. Our framework consists of four components. First, we build a grid-based road network graph for modeling traffic network information during the search routes process. Next, we conduct two prediction modules that adopt advanced deep learning techniques to a proper search direction in the final planning stage. One module, taxi demand prediction, is used to estimate the pick-up probabilities of passengers in the city. Another one is destination prediction, which can predict the distribution of drop-off probabilities and capture the flow of potential passengers. Finally, we propose our J* (J-star) algorithm, which jointly considers pick-up probability, drop-off distribution, road network, distance, and time factors based on the attentive heuristic function. Compared with existing route planning methods, the experimental results on real-world datasets (NYC taxi datasets) have shown our proposed approach is more effective and robust. Moreover, our designed search scheme can decrease the computing time and make the search process more efficient. To the best of our knowledge, this is the first work that focuses on designing a guiding route, which can increase the income of taxi drivers when they have an advance reservation.
論文目次 Abstract IV
List of Tables IX
List of Figures X
Chapter 1 Introduction 1
Chapter 2 Related Work 4
Chapter 3 Preliminaries 6
Chapter 4 Methodology 7
4.1 Traffic Network Construction 8
4.2 Pick-up Probability Prediction 9
4.3 Drop-off Probability Prediction 11
4.4 Multi-Criteria Route Planning (J* algorithm) 14
Chapter 5 Experiments 19
5.1 Evaluation of taxi prediction sections 19
5.2 Evaluation of route planning approach (J*) 21
Chapter 6 Case Studies 32
Chapter 7 Conclusion 35
References 37
參考文獻 [1] J.A.Alvarez-Garcia, J.A.Ortega, L.Gonzalez-Abril, F.Velasco.(2010). Trip destination prediction based on past GPS log using a Hidden Markov Model. Expert Systems with Applications. Volume 37, Issue 12, Pages 8166-8171.
[2] H. Bast, D. Delling, A. Goldberg, M. Müller-Hannemann, T. Pajor, P. Sanders, D. Wagner and R. F. Werneck. (2016). Route planning in transportation networks. In Algorithm engineering (pp. 19-80). Springer, Cham.
[3] A. D. Brébisson, É. Simon, A. Auvolat, P. Vincent, Y. Bengio. Artificial neural networks applied to taxi destination prediction. Proceedings of the 2015th International Conference on ECML PKDD Discovery Challenge.
[4] C. Chen, D. Zhang, Z. H. Zhou, N. Li, T. Atmaca, and S. Li. (2013, March). B-Planner: Night bus route planning using large-scale taxi GPS traces. In 2013 IEEE international conference on pervasive computing and communications (PerCom) (pp. 225-233). IEEE.
[5] E. W. Dijkstra. (1959). A note on two problems in connexion with graphs. Numerische mathematik, 1(1), 269-271.
[6] Y. Endo, K. Nishida, H. Toda, H. Sawada. (2017). Predicting Destinations from Partial Trajectories Using Recurrent Neural Network. In PAKDD 2017.
[7] P. E. Hart, N. J. Nilsson and B. Raphael. (1968). A formal basis for the heuristic determination of minimum cost paths. IEEE transactions on Systems Science and Cybernetics, 4(2), 100-107.
[8] Y. Lassoued, J. Monteil, Y. Gu, G. Russo, R. Shorten, M. Mevissen. (2017) A hidden Markov model for route and destination prediction. IEEE 20th International Conference on Intelligent Transportation Systems (ITSC).
[9] L. Liu, Z. Qiu, G. Li, Q. Wang, W. Ouyang, L. Lin. (2019). Contextualized Spatial–Temporal Network for Taxi Origin-Destination Demand Prediction. IEEE Transactions on Intelligent Transportation Systems, Vol. 20, Issue: 10.
[10] M.-M. Luis, G. João, F. Michel, M.-M. João, D. Luis. (2013). Predicting Taxi–Passenger Demand Using Streaming Data. IEEE Transactions on Intelligent Transportation Systems. Vol. 14 , Issue. 3, 2013.
[11] X. Li, M. Li, Y.-j. Gong, X. Zhang, J. Yin. (2016) T-DesP: Destination Prediction Based on Big Trajectory Data. IEEE Transactions on Intelligent Transportation Systems. Vol. 17 , Issue.8 , Aug. 2016.
[12] Y. Li, J. Lu, L. Zhang, Y. Zhao. (2017). Taxi Booking Mobile App Order Demand Prediction Based on Short-Term Traffic Forecasting. Transportation Research Record: Journal of the Transportation Research Board. Vol. 2634, issue. 1, page(s): 57-68
[13] S. Liao, L. Zhou, X. Di, B. Yuan, J. Xiong. (2018). Large-scale short-term urban taxi demand forecasting using deep learning. In 23rd Asia and South Pacific Design Automation Conference (ASP-DAC).
[14] Y. Lu, J. Gu, D. Xie, and Y. Li. (2019). Integrated Route Planning Algorithm Based on Spot Price and Classified Travel Objectives for EV Users. IEEE Access, 7, 122238-122250.
[15] J. Lv, Q. Li, Q. Sun, X. Wang. (2018). T-CONV: A Convolutional Neural Network for Multi-scale Taxi Trajectory Prediction. 2018 IEEE International Conference on Big Data and Smart Computing (BigComp).
[16] C. Manasseh, R. Sengupta. (2013). Predicting driver destination using machine learning techniques. 16th International IEEE Conference on Intelligent Transportation Systems.
[17] Y. Qiu, and X. 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) (pp. 121-126). IEEE.
[18] F. Rodrigues, L. Markou, F. C. Pereira. (2019). Combining time-series and textual data for taxi demand prediction in event areas: A deep learning approach. Journal of Information Fusion. Volume 49, September 2019, Pages 120-129.
[19] A. Rossi, G. Barlacchi, M. Bianchini, B. Lepri.(2019). Modelling Taxi Drivers' Behaviour for the Next Destination Prediction. IEEE Transactions on Intelligent Transportation Systems(early access).
[20] P. Sanders, and D. Schultes. (2007, June). Engineering fast route planning algorithms. In International Workshop on Experimental and Efficient Algorithms (pp. 23-36). Springer, Berlin, Heidelberg.
[21] D. Schultes. (2008, February). Route Planning in Road Networks. In Ausgezeichnete Informatikdissertationen (pp. 271-280).
[22] R. Simmons, B. Browning, Y. Zhang, V. Sadekar. (2006). Learning to Predict Driver Route and Destination Intent. 2006 IEEE Intelligent Transportation Systems Conference.
[23] R. J. Szczerba, P. Galkowski, I. S. Glicktein, and N. Ternullo. (2000). Robust algorithm for real-time route planning. IEEE Transactions on Aerospace and Electronic Systems, 36(3), 869-878.
[24] H. Wang, R. L. Cheu, and D. H. Lee. (2014). Intelligent taxi dispatch system for advance reservations. Journal of Public Transportation, 17(3), 8.
[25] S. H. I. Xingjian, Z. Chen, H. Wang, D. Y. Yeung, W. K. Wong and W. C. Woo. (2015). Convolutional LSTM network: A machine learning approach for precipitation nowcasting. In Advances in neural information processing systems (pp. 802-810).
[26] J. Xu, R. Rahmatizadeh, L. Bölöni, D. Turgut. (2018). Real-Time Prediction of Taxi Demand Using Recurrent Neural Networks. IEEE Transactions on Intelligent Transportation Systems, Vol. 19 , Issue. 8. 2018.
[27] H. Yao, X. Tang, H. Wei, G. Zheng and Z. Li. (2019). Revisiting spatial-temporal similarity: A deep learning framework for traffic prediction. In AAAI Conference on Artificial Intelligence.
[28] H. Yao, F. Wu, J. Ke, X. Tang, Yi. Jia, S. Lu, P. Gong, J. Ye, Z. Li. (2018). Deep Multi-View Spatial-Temporal Network for Taxi Demand Prediction. In AAAI Conference on Artificial Intelligence.
[29] H. M. Zhang, M. L. Li, and L. Yang. (2018). Safe Path Planning of Mobile Robot Based on Improved A* Algorithm in Complex Terrains. Algorithms, 11(4), 44.
[30] L. Zhang, G. Zhang, Z. Liang, E. F. Ozioko. (2018). Multi-features taxi destination prediction with frequency domain processing. PLoS One. 2018; 13(3).
[31] K. Zhang, Z. Feng, S. Chen, K. Huang, G. Wang. (2016). A Framework for Passengers Demand Prediction and Recommendation. In 2016 IEEE International Conference on Services Computing (SCC).
[32] K. Zhao, D. Khryashchev, J. Freire, C. Silva, H. Vo. (2016). Predicting taxi demand at high spatial resolution: Approaching the limit of predictability. 2016 IEEE International Conference on Big Data (Big Data).
[33] F. Zong, Y. Tian, Y. He, J. Tang, J. Lv.(2019).Trip destination prediction based on multi-day GPS data. Physica A: Statistical Mechanics and its Applications,Volume 515, 2019, Pages 258-269.
[34] Michael R. Garey and David S. Johnson. 1979. Computers and intractability: a guide to the theory of NP-completeness. W. H. Freeman and Company. Appendix B, pp. 208.
[35] Michael R. Garey, David S. Johnson, and Larry J. Stockmeyer. 1976. Some simplified NP-complete graph problems. Theoretical Computer Science 1(3): 237-267.
[36] Michael R. Garey, David S. Johnson, and Robert E. Tarjan. 1976. The Planar Hamiltonian Circuit Problem is NP-Complete. SIAM Journal on Computing 5(4), 704–714.
[37] Refael Hassin and Asaf Levin. 2004. An efficient polynomial time approximation scheme for the constrained minimum spanning tree problem using matroid intersection. SIAM Journal on Computing 33(2): 261–268.
論文全文使用權限
  • 同意授權校內瀏覽/列印電子全文服務,於2025-07-09起公開。
  • 同意授權校外瀏覽/列印電子全文服務,於2025-07-09起公開。


  • 如您有疑問,請聯絡圖書館
    聯絡電話:(06)2757575#65773
    聯絡E-mail:etds@email.ncku.edu.tw