[發明專利]面向多載客里程的出租車運行線路優化方法

有效

• 申請號: 201711103910.2
• 申請日: 2017-11-10
• 公開（公告）號: CN107919014B
• 公開（公告）日: 2020-10-30
• 發明（設計）人: 榮輝桂;張群;楊昌;張旭東;潘夢穎
• 申請（專利權）人: 湖南大學
• 主分類號: G08G1/00
• 分類號: G08G1/00;G06Q10/04
• 代理公司: 北京睿智保誠專利代理事務所(普通合伙) 11732
• 代理人: 周新楣

1.面向多載客里程的出租車運行線路優化方法，包括如下步驟：

S1.將出租車的運營區域劃分為若干個網格，同時獲取運營區域內的歷史運營數據；劃分的網格區域的大小能夠與出租車的運營區域內的路段信息進行匹配；所述歷史運營數據，包括時刻t時從網格i到網格j的平均時間，時刻t時將乘客從網格i運輸至網格j的平均收入，時刻t時巡游完網格i的時間，時刻t時在網格i中找到乘客的出租車數量，時刻t時經過網格i的出租車數量，時刻t時以區域j為目的地的乘客數量，其中t為正實數，i和j均為自然數；

S2.定位出租車當前的位置和運營狀態；

S3.根據步驟S2獲取的出租車當前的位置和運營狀態，對出租車的下一步運行路線進行優化，從而完成出租車的收入效率優化；所述對出租車的下一步運行路線進行優化包括：

A.獲取當前出租車的運營狀態；

B.根據步驟A獲取的出租車的運營狀態，采用馬爾科夫決策過程方法對出租車的下一步運行路線進行優化；

所述對出租車的下一步運行路線進行優化具體為采用如下規則進行優化：

R1.若出租車處于運輸乘客的狀態，則采用路徑優化算法對出租車的下一步運行路線進行優化；

R2.若出租車處于未載客狀態且未載客狀態的持續時間大于或等于設定的閾值，則認定出租車處于未營運狀態，停止對出租車的下一步運行路線進行優化；

R3.若出租車處于未載客狀態且未載客狀態的持續時間小于設定的閾值，則認定出租車處于尋找乘客狀態，此時以如下函數為目標函數，對出租車的下一步運行路線進行優化：

式中max為求最大值函數，V*(s,a)為出租車在當前時間段下，在狀態s時的行動a能夠帶來的期望收益；P_find(l)為出租車在網格l中能夠找到乘客的概率，V(l_a,t+t_seek(l_a),10-a)為出租車已經花費了t+t_seek(l_a)時間，并且在當前網格區域l_a中沒有找到乘客的情況下，以(10-a)為行駛方向的推薦期望值；V(k,t+t_seek(j)+t_drive(j,k),0)表示在j區域找到乘客的期望值，其中，t+t_seek(j)+t_drive(j,k)表示在j區域找到了要去往k區域的乘客，此時已經花費了的尋找時間和即將花費的從j路段到k路段的耗時時間；t為當前的時間，t_seek(l_a)為巡游目標網格區域l_a所需要的時間，P_dest(j,k)為從網格區域j到網格區域k的可能性，r(j,k)為出租車從網格區域j到網格區域k的期望收益，t_drive(j,k)為出租車從網格區域j到網格區域k所花費的時間；a為空出租車所采取的行動，且a∈A，A為空出租車能夠采取的行動集合；A取值為1～9的自然數，且1表示出租車的下一個行動為從當前位置向西南方向行駛，2表示出租車的下一個行動為從當前位置向正南方向行駛，3表示出租車的下一個行動為從當前位置向東南方向行駛，4表示出租車的下一個行動為從當前位置向正西方向行駛，5表示出租車的下一個行動為在當前位置停留，6表示出租車的下一個行動為從當前位置向正棟方向行駛，7表示出租車的下一個行動為從當前位置向西北方向行駛，8表示出租車的下一個行動為從當前位置向正北方向行駛，9表示出租車的下一個行動為從當前位置向東北方向行駛。

2.根據權利要求1所述的面向多載客里程的出租車運行線路優化方法，其特征在于規則R3所述的對出租車的下一步運行路線進行優化，具體為采用動態規劃方法對目前函數進行求解，從而對出租車的下一步運行路線進行優化。