[發明專利]一種基于需求預測的城市出租車調度方法

有效

• 申請號: 201911214182.1
• 申請日: 2019-12-02
• 公開（公告）號: CN110796317B
• 公開（公告）日: 2022-11-01
• 發明（設計）人: 熊盛武;程浩;段鵬飛;陸麗萍;路雄博;曹丹鳳
• 申請（專利權）人: 武漢理工大學;武漢水象電子科技有限公司
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06Q10/06;G06Q30/06;G06Q50/30
• 代理公司: 武漢科皓知識產權代理事務所(特殊普通合伙) 42222
• 代理人: 許蓮英

1.一種基于需求預測的城市出租車調度方法，其特征在于，包括如下步驟：

步驟1，對載客軌跡數據通過濾噪聲數據進行數據預處理；

步驟1中所述載客軌跡數據為：

城市中所有出租車載客過程中的軌跡點組成的軌跡序列；不同出租車沒有明顯的軌跡區分度，所以在此不區分不同出租車產生的軌跡；

tra表示載客軌跡的一條完整軌跡，由n個軌跡點p_i組成；

p_i是一個三元組(lat_i，lng_i，t_i)，其中lat_i表示軌跡點的經度，lng_i表示軌跡點的緯度，t_i表示軌跡點的時間；

載客軌跡的一條完整軌跡可表示為：

tra＝{p₁，p₂，p₃，…，p_n}；

其中，n為軌跡點的數量；

步驟1中所述過濾噪聲數據的具體方法是：

步驟1.1，檢查數據完整性；

數據完整性是指檢查tra＝{p₁，p₂，p₃，...，p_n}的所有軌跡點是否都有橫縱坐標以及時間，如果軌跡點三元組都存在且是有效表示則表示該條軌跡完整；否則不完整，對于不完整的軌跡數據應舍棄整條軌跡；

步驟1.2，判斷軌跡點是否在城市區域內；

根據城市行政劃分范圍，確定城市的最大坐標范圍：

(lat_min，lat_max，lng_min，lng_max)

其中，lat_min表示軌跡點的經度最小值，lat_max表示軌跡點的經度最大值，lng_min表示軌跡點的緯度最小值，lng_max表示軌跡點的緯度最大值；

判斷軌跡點是否在這個范圍內：

若lat_min≤lat_i≤lat_max且lng_min≤lng_i≤lng_max則是有效軌跡點；

否則是無效軌跡點，對無效軌跡點所在的整條軌跡數據進行舍棄；

判斷軌跡中相鄰兩個點是否發生漂移情況：判斷兩個點之間的速度，發生漂移的點會在常規時間內發生躍遷現象，如果兩點之間的距離除以時間不在常規范圍內則認為發生了數據漂移現象；

如果haversine((lat_i，lng_i)-(lat_i-1，lng_i-1))/(t_i-t_i-1)大于車輛常規速度，則說明軌跡點發生漂移，過濾掉該軌跡點所在的整條軌跡數據，其中haversine是地理球面計算公式；

步驟2：通過二維卷積神經網絡進行時間周期規律和空間關聯特征的城市區域需求特征提取；

步驟2中所述通過二維卷積神經網絡進行空間關聯特征和時間周期規律的城市區域需求特征提取為：

步驟2.1，通過二維卷積神經網絡進行空間關聯特征的城市區域需求特征提取為：

將城市區域范圍劃分為I×J個網格區域，使用二維數組下標的方式定位每個區域，下標為(i,j)的區域r_i,j在時刻t的出租車需求定義為

城市的所有區域在時刻t的出租車需求則定義為：

對于區域r_i,j，提取其出租車需求數值以及以(i，j)為中心點、大小為L×L的范圍區域作為該區域的出租車需求特征數據；

提取的區域出租車需求特征數據可以看作是只有一個通道的L×L圖像，區域出租車需求表示為

將輸入到S層卷積網絡中，第s層的輸入是

每層卷積網絡數據轉換定義為：

其中，*表示卷積操作，f(·)是激活函數，使用ReLU激活函數，w^s和b^s是第s卷積層的參數集合；

經過卷積操作之后，將多個卷積核得到的輸出進行拉伸操作得到區域r_i,j在t時特征向量最后使用全連接層對特征向量進行降維：

其中，W^fc和b^fc是全連接層的學習參數，是區域r_i,j出租車需求數據經過卷積處理得到長度為convLen的空間特征向量；

步驟2.2，通過二維卷積神經網絡進行時間周期規律的城市區域需求特征提取為：

城市區域需求數據來自出租車軌跡數據，而出租車軌跡數據呈現出明顯的時間連續特性，每天不同時間有不同的需求；

所以出租車需求數據的時間特性提取結合空間特性更能反映出出租車需求的時空特性；

需求數據時間特征提取，使用長短期記憶神經網絡提取數據時序依賴特征，并將時間周期信息作為輔助信息嵌入到網絡架構中，具體流程為：

將城市區域出租車需求數據的時序長度設為step，即將每個區域連續step個時間段的需求數據作為一條樣本數據進行特征提取；

對每個時序數據進行上步中空間特征提取得到步長為step的特征向量s^i,j∈R^{step×convlen}；

s^i,j是一個step×convlen的二維向量，每行表示一個時序下的空間特征向量；

將向量s^i,j作為長短期記憶神經網絡(LSTM)的輸入，借助LSTM提取時序數據依賴關系特征的能力，提取區域r_i,j出租車需求數據的時序依賴關系；

LSTM一共有輸入門、遺忘門、輸出門和記憶單元四個重要的概念；記憶單元C_t“記住”時間t之前的歷史序列，進而學習序列依賴關系；遺忘門f_t讀取上個時刻輸出的隱藏狀態h_t-1和當前時刻的輸入x_t，決定從記憶單元C_t-1中丟棄哪些信息；輸入門i_t則決定當前時間t有多少新的信息輸入到記憶單元中；輸出門o_t控制記憶單元的輸出；

輸入門為：

i_t＝σ(W_ix_t+U_ih_t-1+b_i)

遺忘門為：

f_t＝σ(W_fx_t+U_fh_t-1+b_f)

輸出門為：

θ_t＝tanh(W_gx_t+U_gh_t-1+b_g)

計算一個新的候選值向量為：

o_t＝σ(W_ox_t+U_oh_t-1+b_o)

新的候選值向量與輸入門共同用于更新記憶單元狀態為：

上述公式中，舊的記憶單元狀態與遺忘門相乘并加上新的候選值向量得到當前時間t下的記憶單元狀態；

定義輸出門與記憶單元狀態相乘得到當前時間t下的隱藏狀態為：

時序數據輸入到LSTM后，每個時序下輸出隱藏狀態h_t，最后時序的數據得到最終的輸出結果h_end，該輸出結果包含了時序數據的時間依賴特性；

將向量s^i,j輸入LSTM中，最終輸出結合區域r_i,j出租車需求分布空間關聯特征和時序依賴特征的向量，即城市區域出租車需求數據的時空特征向量ST^i,j；

除了區域出租車需求數據，預測模型還需要輸入額外信息：

區域標識信息即Region_ID：用于標識樣本數據所屬區域；

時間段信息即Time_Slot：表示樣本數據在一天中所屬的時間段；

交通工作日周期信息即Weekday：樣本數據在一周中所屬的天數；

通過在預測模型中加入時間信息可以根據時間變化規律對不同時間段的需求數據進行預測，為了更好地在神經網絡中表示上述三種信息，對三種信息分別進行下標表示：

由于這三種信息是以范圍下標的方式表示，如果直接將下標輸入到網絡中，下標的大小數學意義會影響神經網絡的特征提取；

將區域標識信息、時間段信息和交通工作日周期信息以嵌入向量的形式輸入神經網絡，這種信息嵌入向量表示消除了下標數值大小的數學意義；得到的嵌入向量與時空特征向量ST^i,j進行組合拼接輸入到全連接層中作為區域r_i,j的一條樣本向量，該區域在該時刻下的出租車需求數據作為預測結果；

該預測模型的損失函數為：

其中是預測模型輸出的預測結果，y_i是真實需求數據，n是訓練集樣本個數；該預測模型使用梯度反向傳播進行參數調優，最終的LSTM出租車需求預測模型；

步驟3：結合城市區域出租車需求數目預測和出租車軌跡目的地預測，使用NSGA-II算法對城市出租車進行調度；

根據步驟2，從城市區域需求的歷史數據訓練預測模型，并對未來一段時間內的需求進行預測，便可以得到未來一段時間內城市所有區域的出租車需求數量；

結合當前時間的城市出租車位置分布情況，對出租車進行調度，合理分配出租車運力資源；

從城市區域需求樣本數據和出租車軌跡中提取數據集中第weekday天中timeslot時段的區域需求預測分布D；

通過車載GPS系統和載客狀態傳感器，可以實時獲取出租車位置信息和載客狀態；

在第weekday天timeslot-1時間，獲取所有出租車的位置信息和載客狀態，過濾掉所有載客狀態的出租車，得到所有空載出租車的位置分布K；

最大化城市區域出租車需求的滿足度和最小化所有調度車輛行駛距離；

最大化城市區域出租車需求的滿足度平均值S：

其中，

式中M_i調度到區域i的出租車個數，D′_i是計算得到的區域需求數據；需求滿足度表示出租車調度系統的效率，滿足度越高表示出租車找到乘客的概率越大；

最小化所有調度車輛行駛距離之和DIS：

其中，

dis_ij是區域i和區域j之間的網格距離，通過將區域編號轉換為二維下標進行計算；調度車輛行駛距離越小表示出租車運營油耗越小，經濟損失越小。