多方有益的計程車拼車調度方法
2023-04-25 21:45:11
多方有益的計程車拼車調度方法
【專利摘要】本發明提供一種多方有益的計程車拼車調度方法，其包括：對於乘客發送的乘車請求，調度中心分析其中包含的信息：乘客數目、上車位置和上車位置時間範圍、下車位置和下車位置時間範圍、願意支付的小費；調度中心跟蹤各計程車的狀態，包括計程車位置和車上乘客數目，根據乘車請求中的信息和計程車狀態設定整數線性規劃的目標函數，計算得到最優解，將求解整數線性規劃得到的調度作為當前計程車拼車調度方案。該方法還包括一個動態的規劃更新機制，只有當新調度對於目標函數的提升能夠達到或超過一個閾值，才對當前的計程車調度進行更新。本發明可以降低乘客打車的花費，增加計程車司機的收益，使得多方受益。
【專利說明】多方有益的計程車拼車調度方法
【技術領域】
[0001] 本發明涉及城市交通計算領域，尤其是一種計程車的拼車調度方法。
【背景技術】
[0002] 在現代化的城市中，計程車正在人們的交通出行中起到越來越重要的作用。一項 在紐約的調查顯示，超過100家計程車公司正運營著超過一萬三千輛計程車，每天的載客 量有66萬。佔到所有流量的百分之25。計程車上面的交通花費佔其他公交花費的百分之 45。
[0003] 經管計程車正變得越來越重要，如今的計程車系統卻十分低效。在交通繁忙時期， 人們往往很難打到車。而正在載客的計程車上，往往也有很多空位。這樣一種低效對於那 些人口的增加速度快於城市化進程的城市來說，能帶來更多的不便。
[0004] 在計程車系統中引入拼車的概念可以很好的緩解公交系統的低效。當乘客們有一 些相似的行程時，他們就可以選擇共享一輛計程車。如今已經有一些拼車方案被提出，然 而，他們大多無法處理實時的大規模乘車要求。而可以實時做調度的系統，也只是採取了一 個最簡單的方法：對於一個新來的乘車請求，系統調度一輛繞路最少的計程車去服務這個 新的請求。他們不會考慮乘客的體驗。
[0005] 現有的計程車拼車調度系統較難權衡乘客的乘車體驗（包括乘車時間，以及拼車 的陌生人的數目等）與計程車司機的利益。比如在傳統的計程車系統中，貪婪的計程車司 機會選擇去開一條較長的路徑，從而增加計程器的裡程數，這樣也會增加用戶的乘車時間。 在拼車系統中，用戶的體驗有可能會被更大程度的影響。人們選擇坐計程車往往是為了一 個比較舒適的，不用多走路的服務。如果與陌生人拼車，乘客們往往會感受到隱私的洩露， 更長的旅程。這樣的擔憂會大大打擊乘客們想要拼車的願望。另外一方面，為了達到最優 的調度策略，計程車系統往往要時時地對調度進行更新。
【發明內容】
[0006] 本發明的目的在於克服現有技術中存在的不足，提供一種多方有益的計程車拼車 調度方法，能夠解決乘客體驗與司機收益之間的矛盾，同時也能時時對調度策略進行更新， 可以減緩城市交通堵塞問題，節約能源，也可以降低乘客打車的花費，增加計程車司機的收 益，實現多方有益。本發明採用的技術方案是：
[0007] -種多方有益的計程車拼車調度方法，其包括：
[0008] 對於乘客發送的乘車請求，調度中心分析其中包含的信息：乘客數目、上車位置和 上車位置時間範圍、下車位置和下車位置時間範圍、願意支付的小費；
[0009] 調度中心跟蹤各計程車的狀態，包括計程車位置和車上乘客數目，根據乘車請求 中的信息和計程車狀態設定整數線性規劃的目標函數，計算得到最優解，將求解整數線性 規劃得到的調度作為當前計程車拼車調度方案。
[0010] 進一步地，所述整數線性規划具體包括：
[0011] 刻畫計程車拼車調度：
[0012] 首先，使用戈=...，尺^}較表示當前正要處理的乘車請求集合，n表示乘車請 求數，使用V= {K, 來表示道路上計程車的集合，m表示計程車數；
[0013] 接著，將計程車拼車調度問題刻畫在一個有向圖G(N，A)中，N用來表示有向圖G中 節點的集合，A用來表示有向圖G中有向邊的集合，其中N= 0UPUD，0 = {1，…，m}，P ={m+l，*"，m+n}，D= {m+n+l，*"，m+2n};集合P和D用來表示上車位置和下車位置，集合 〇用來表示計程車當前的位置；
[0014] 用c來表示每輛計程車的最大載客數目；每一個有向圖G中的節點i都賦予一個 負載Qi;對於i屬於〇或P，負載Qi彡1，對於i屬於D，負載qi= -qi_n ;負載qi用來表不一 個乘車請求中乘客的人數；
[0015] 對於每一個P和D中的節點，設定一個時間窗口[ep 1J來表不最早和最晚到達這 個節點i的時間限制；對於每一個節點i屬於D，使用0i來表示對於乘車請求的線性 遞減係數；
[0016] 對於有向圖G中每一條有向邊（i,j)和每一輛計程車，如果車輛k被調度去通行 (i，j)這條道路，則將設置為1，否則設置為0 ;
[0017] 使用來表示計程車k到達節點i時的時間，使用來表示計程車到達節點i 時，車上的乘客數目；
[0018] 設定整數線性規劃的限制條件：
[0019] 1)從計程車位置出來的流最多為一：
【權利要求】
1. 一種多方有益的計程車拼車調度方法，其特徵在於： 對於乘客發送的乘車請求，調度中心分析其中包含的信息：乘客數目、上車位置和上車 位置時間範圍、下車位置和下車位置時間範圍、願意支付的小費； 調度中心跟蹤各計程車的狀態，包括計程車位置和車上乘客數目，根據乘車請求中的 信息和計程車狀態設定整數線性規劃的目標函數，計算得到最優解，將求解整數線性規劃 得到的調度作為當前計程車拼車調度方案。
2. 如權利要求1所述的多方有益的計程車拼車調度方法，其特徵在於，所述整數線性 規划具體包括： 刻畫計程車拼車調度： 首先，使用
來表示當前正要處理的乘車請求集合，n表示乘車請求 數，使用v= {^^，…，VJ來表示道路上計程車的集合，m表示計程車數； 接著，將計程車拼車調度問題刻畫在一個有向圖G(N，A)中，N用來表示有向圖G中節 點的集合，A用來表示有向圖G中有向邊的集合，其中N= 0UPUD，0= {1，…，m}，P= {m+l，*"，m+n}，D= {m+n+l，"*，m+2n};集合P和D用來表示上車位置和下車位置，集合0 用來表示計程車當前的位置； 用c來表示每輛計程車的最大載客數目；每一個有向圖G中的節點i都賦予一個負載Qi;對於i屬於〇或P，負載1彡1，對於i屬於D，負載qi= _qi_n ;負載qi用來表示一個乘 車請求中乘客的人數； 對於每一個P和D中的節點，設定一個時間窗口 [ei，1J來表示最早和最晚到達這個節 點i的時間限制；對於每一個節點i屬於D，使用0i來表示對於乘車請求的線性遞減 係數； 對於有向圖G中每一條有向邊（i，j)和每一輛計程車，如果車輛k被調度去通行（i，j) 這條道路，則將?設置為1，否則設置為0 ; 使用7f來表示計程車k到達節點i時的時間，使用來表示計程車到達節點i時，車 上的乘客數目； 設定整數線性規劃的限制條件： 1) 從計程車位置出來的流最多為一：
2) 所有進入上車位置（接客位置）的流都會離開這個位置：
3) 限制所有計程車從上車位置出來的流最多為一，用公式（3-1)表示；限制經過上車 位置的計程車，最終會到達下車位置，用公式（3-2)表示；
4) 到達終點的流的總數目大於等於進入終點的流的總數目：
5) 刻畫計程車到達每一個位置的時間關聯性，用公式（5-1)表示；限制計程車到達每 一個位置的時間處於規定範圍內，用公式（5-2)表示；限制計程車會先到達上車位置，再達 到下車位置，用公式（5-3)表示；
其中，表示從有向圖G中節點i到節點j所需要的時間； 6) 刻畫計程車達到每一個位置時，車上乘客的數量，用公式（6-1)表示；限制乘客數量 小於車的容量c，用公式（6-2)表不：
設定整數線性規劃的目標函數；有兩個目標函數， 第一個目標函數用於優化司機賺到的小費的數目，用公式（9)表示：
其中，ai為每位發送乘車請求的乘客願意最多支付的消費； 第二個目標函數用於最小化所有乘客送達延時的加權和，用公式（10)表示：
求得公式（9)或（10)中的一個最優解，然後即可將求解整數線性規劃得到的調度作為 當前計程車拼車調度方案。 3如權利要求1或2所述的多方有益的計程車拼車調度方法，其特徵在於： 該方法還包括一個動態的規劃更新機制，只有當新調度對於目標函數的提升能夠達到 或超過一個閾值，才對當前的計程車調度進行更新，否則保持原計程車調度。
【文檔編號】G08G1/00GK104408910SQ201410683491
【公開日】2015年3月11日 申請日期:2014年11月24日 優先權日:2014年11月24日
【發明者】張善豐, 馬強, 朱彤, 劉克彬, 毛續飛, 劉雲浩 申請人:無錫清華信息科學與技術國家實驗室物聯網技術中心