[發明專利]一種基于混合啟發式算法的智能公交調度方法

有效

• 申請號: 201410481840.4
• 申請日: 2014-09-19
• 公開（公告）號: CN104504229B
• 公開（公告）日: 2018-02-16
• 發明（設計）人: 鄭寧;陳濤;徐海濤;林菲
• 申請（專利權）人: 杭州電子科技大學
• 主分類號: G06Q10/06
• 分類號: G06Q10/06;G06Q50/30
• 代理公司: 杭州君度專利代理事務所(特殊普通合伙)33240
• 代理人: 黃前澤

1.一種基于混合啟發式算法的智能公交調度方法，其特征在于包括如下步驟：

步驟(1)讀取乘客的刷卡記錄，統計每天乘車總人數和每個時間段I內的人數，獲取每天的歷史天氣狀況和節假日情況；使用層次聚類方法，對獲取的歷史數據進行聚類分析；即將一天當中的乘車總人數、不同時間段內的乘車人數、天氣情況和節假日情況組合成一個向量，然后對該向量進行歸一化操作，使用系統聚類算法中的Ward法進行聚類操作，根據聚類的結果提取每個類別的特征；

所述的刷卡記錄包括上車刷卡時間、上車站點、下車刷卡時間和下車站點；

所述的獲取的歷史數據包括乘客的刷卡記錄、歷史天氣狀況和節假日情況；

步驟(2)根據第二天的天氣預報信息和節假日情況，從步驟1的聚類結果中匹配到一個類，并從該類中抽取一個向量作為預測值；

步驟(3)根據預測值，結合公交企業期望的滿載率，兩者相除，得到第二天的總發車班次；

步驟(4)隨機生成N個向量，向量的維度與總發車班次相等；每個分量代表對應班次的發車時間，發車時間以分鐘為單位，設定第一個分量等于0，最后一個分量等于末班車發車時間與首班車發車時間之間的分鐘數；向量中的分量按從小到大的順序排列，這N個向量組成初始解的集合P₀，并設定迭代次數g為0；其中N為偶數；

步驟(5)建立公交調度的數學模型，以乘客的等待時間最短為目標設定適應度函數，計算每個初始解的適應度，然后通過混合啟發式算法進行求解；

5-1.使用適應度拉伸函數進行適應度拉伸操作，用拉伸后的值替換掉原來的適應度；

5-2.按照輪盤賭選擇策略從集合P_g中選擇任意兩個解，按照設定的交叉概率進行交叉操作，即隨機選擇一個交叉位置，交換兩個解交叉點后的部分，得到兩個交叉后的解；然后對兩個交叉后解進行模擬退火操作：計算交叉后的解的適應度，如果適應度增大，接受新的解，否則以當前的接受概率接受新的解；從而獲取兩個新的解；

5-3.按照設定的變異概率，對步驟5-2中獲取的兩個新解的每一個分量進行變異操作，即隨機生成一個大小位于前后兩個分量之間的自然數，替換掉原來的值，得到兩個變異后的解；然后進行模擬退火操作：計算變異后的解的適應度，如果適應度增大，接受新的解，否則以當前的接受概率接受新的解；從而獲取兩個新的解，并將獲取的兩個新的解放入解集P_g+1；

5-4.判斷解集P_g+1中解的個數是否與N相等；如果相等，則實施精英保留策略，即當P_g+1中的最優解的適應度比P_g中的最優解的適應度小時使用解集P_g中適應度最大的解替換掉P_g+1中適應度最小的解；否則，重復步驟5-2和5-3，直至解集P_g+1中解的個數與N相等；

步驟(6)更新迭代次數g＝g+1，若已經達到最大的迭代次數G_max，則輸出解集P_g中適應度最高的解，即為優化后的發車時刻表；否則，轉到步驟5-1；

所述的迭代次數G_max為正整數。