How to Optimize the Profit of Taxi Routes with an Advance Reservation? J*: A Multi-Criteria Approach Using Spatial-Temporal Predictions

摘要

隨著城市的開發與進步，計程車服務也變得越來越多元化以滿足使用者們的需求。計程車預約的需求不斷增長，如何在有預約的情形下，設計一條載客路徑來提升計程車司機的利潤已經引起關注。然而在過去的情形下，計程車司機在面對預約需求時往往需要提前空車一段時間來避免錯失預約客人，因此變相的提高預約服務價格，造成供需不平衡的狀況。因此，我們提出一個路徑規劃框架，內容包含了深度學習模型的應用、路網資訊的建置以及多面向路徑規劃演算法，目的是在有預約客人的情形下，規劃一條載客路徑來提升載客率並且同時讓司機準時抵達預約終點。此路徑規劃框架包含了四大模組，首先我們建立一個以網格為基底的搜尋網路，他能降低搜尋量，並且提供在做路徑規劃時必要的資訊例如地區之間的通勤距離以及通勤時間。再來是兩個預測模型的應用，我們採用兩個深度學習方法來預測載客需求，一個是載客機率預測模型，能預測城市中的載客機率，另一個則是目的地機率預測模型，目的是預測乘客的目的地。最後是集大成之路徑規劃演算法(J* 演算法)，此演算法應用了前三大模組提供的資訊來做路徑規劃，並且以一個啟發式函式來計算候選網格的分數。結果顯示，我們提出的方法與傳統路徑規劃方法比較起來更加地有效率且穩健，並且我們提出的方法能有效地降低搜尋運算量。在我們的認知之下，這是第一份針對在有預約客人的情形下，關於提升載客利潤的載客路徑規劃研究。

獎項日期	2020
原文	English
監督員	Hsun-Ping Hsieh (Supervisor)