[發(fā)明專利]一種基于滾動時域調度算法的公共慢行系統動態(tài)調度方法

無效

• 申請?zhí)枺?/td>: 200910155566.0
• 申請日: 2009-12-17
• 公開（公告）號: CN101739655A
• 公開（公告）日: 2010-06-16
• 發(fā)明（設計）人: 董紅召;趙敬洋;郭明飛;郭海鋒;陳寧
• 申請（專利權）人: 浙江工業(yè)大學
• 主分類號: G06Q50/00
• 分類號: G06Q50/00
• 代理公司: 杭州天正專利事務所有限公司 33201
• 代理人: 王兵;王利強

1.一種基于滾動時域調度算法的公共慢行系統動態(tài)調度方法，其特征在于：所述公共慢行系統動態(tài)調度方法包括以下步驟：

1)、設定時間軸表示一個工作日的整個調度周期，在時間軸上，每一個時刻對應一個場景，關鍵點是指正在接受服務或者有運輸車輛正在前往該點的路上的租賃點，關鍵點的任務是不能更改；

時間窗是公共自行車租賃點允許服務的時間范圍，用模糊時間窗來描述租賃點對服務時間的約束范圍，[WA_i，WB_i]表示租賃點i可容忍的服務時間范圍，[WC_i，WD_i]表示租賃點i期望的服務時間范圍，t_i表示車輛到達點i的時間；租賃點i的滿意度表示為：

2)、建立調度模型：停車場P0有T輛運輸車，運輸車輛k最大載重量為Q_k，從停車場P0派遣若干運輸車輛向n個公共自行車租賃點提供服務，每一個租賃點的容量為E_i(i＝1，2…n)，在t時刻，每個租賃點的自行車的數量為q_i(t)(i＝1，2……n)；q_i(t)與E_i之比為H_i(t)，正常狀態(tài)下租賃點i的H_i的范圍是[C_min，C_max]，租賃點的服務請求有兩種情況：①當H_i(t)＞C_max時，表示租賃點在t時刻需要運出自行車；②當H_i(t)＜C_min時，表示租賃點在t時刻需要運入自行車；租賃點i可容忍的服務時間范圍是[WA_i，WB_i]，期望的服務時間范圍是[WC_i，WD_i]；租賃點i的服務時間為s_i，t_i表示運輸車輛到達租賃點i開始服務的時間，f_i(t_i)表示租賃點i的滿意度；

租賃點的需求量為租賃點需要運入或運出的自行車的數量，當H_i(t)＞C_max時，租賃點需運出自行車，設租賃點此時的需求量為d_i(t)，當租賃點接受服務后，其H_i應該在區(qū)間[C_min，C_max]內，則必須滿足Cmin≤qi(t)-di(t)Ei≤Cmax,]]>即q_i(t)-C_maxE_i≤d_i(t)≤q_i(t)-C_minE_i，此時，d_i(t)取其下限q_i(t)-C_maxE_i即可滿足要求；同理，當H_i(t)＜C_min時，d_i(t)＝C_minE_i-q_i(t)；

N(t)：t時刻，所有未完成任務租賃點，新的有服務請求的租賃點和停車場的集合；

M(t)：t時刻，所有關鍵點、未完成任務租賃點，新的有服務請求的租賃點和停車場的集合；

K：運輸車輛的集合；

TS：時間軸；

Q_ki：運輸車輛K在租賃點i服務后裝載的自行車的數量；

以租賃點總的滿意度最大化為目標建立公共慢行系統調度的模型，目標函數如下：

maxZ=Σt∈TSΣi∈N(t)[fi(ti)]---(1)]]>

約束條件為：

Q_ki＜Q_k∀i∈M(t),k∈K---(2)]]>

3)、將整個調度周期劃分為若干個子調度周期，將每一個子調度周期看作是靜態(tài)的調度問題，通過求解若干個靜態(tài)的調度問題和不斷滾動更新調度計劃的方法實現動態(tài)的車輛調度；

在求解每子調度周期對應的靜態(tài)調度問題時，采用基于變鄰域的禁忌搜索算法獲取調度計劃；在變鄰域的搜索過程中存在以下概念：

(a)變鄰域搜索條件：當搜索過程中連續(xù)若干次迭代后解的適配值沒有提高時，滿足變鄰域搜索條件，否則，不滿足變鄰域搜索跳條件；

(b)原鄰域解：禁忌搜索過程中不滿足變鄰域搜索條件時的鄰域解；

(c)變鄰域解：禁忌搜索過程中滿足變鄰域搜索條件時的鄰域解，變鄰域解與原鄰域解相比具有不同的鄰域結構。

變鄰域的禁忌搜索算法步驟如下所示，包括：

(3.1)產生初始解，初始化參數和禁忌表；

(3.2)判斷是否滿足終止條件，如果滿足則介紹并輸出結果，否則，轉至步驟(3.3)；

(3.3)判斷是否滿足變鄰域條件，如果滿足生成當前解的變鄰域解，反之，生成當前解的原鄰域解；

(3.4)確定候選解；

(3.5)判斷是否滿足藐視準則，如果是，則用特赦解替換當前解，轉至步驟(3.2)并更新禁忌表，否則，則轉至步驟(3.6)；

(3.6)在候選解中用最優(yōu)的非禁忌解替換當前解，并更新禁忌表，轉至步驟(3.2)。

2.如權利要求1所述的基于滾動時域調度算法的公共慢行系統動態(tài)調度方法，其特征在于：在所述步驟3)中，當經過連續(xù)若干次迭代后解的適配值沒有提高時，則改變鄰域結構，即在當前解的新的鄰域解中進行搜索。