[發明專利]一種面向大規模純電動公交車輛調度問題的自適應大型鄰域搜索方法

有效

• 申請號: 202011080309.8
• 申請日: 2020-10-10
• 公開（公告）號: CN112257999B
• 公開（公告）日: 2022-11-01
• 發明（設計）人: 李鐵柱;張愛佳
• 申請（專利權）人: 東南大學
• 主分類號: G06Q10/06
• 分類號: G06Q10/06;G06Q50/26
• 代理公司: 南京眾聯專利代理有限公司 32206
• 代理人: 杜靜靜

1.一種面向大規模純電動公交車輛調度問題的自適應大型鄰域搜索方法，其特征在于，所述方法包括以下步驟：

步驟1：通過啟發式構造方法生成初始解s₀，初始化所有的刪除和插入算法權重為ω₀；初始化模擬退火的初始溫度T₀；

步驟2：從所有刪除算法中按照輪盤法選擇一個，對當前解s執行刪除操作，并記錄所有刪除的行程；

步驟3：從所有插入算法中按照輪盤法選擇一個，將步驟2中所有刪除的行程重新插入至當前解s中，生成新解s'；

步驟4：通過局部搜索算法對新解s'的局部鄰域進行搜索，若實現了優化則保留優化后的解；

步驟5：判斷新解s'是否優于當前最優解s*，若是則將當前最優解替換為新解s*←s'，并記錄此次迭代的序號i^lastimprove；

步驟6：根據接受準則判斷是否接受新解s'，若滿足接受條件則將當前解替換為新解s←s'；

步驟7：根據評分機制對此次迭代中選擇的刪除和插入算法進行評分，若此次迭代中生成的解s'優于當前最優解s*，則選擇的刪除和插入算法加ω₁分；

若此次迭代生成的解s'優于當前解s，則選擇的刪除和插入算法加ω₂分；否則不對所選擇的算法評分進行調整；

步驟8：根據冷卻率α對模擬退火溫度進行調整，具體過程為：每一次迭代后T′＝αT，其中T為當前的溫度，T′為下一次迭代的溫度；

步驟9：判斷是否滿足算法的終止條件，若滿足則轉到步驟10；否則轉到步驟2，算法的終止條件設為滿足預設的最大迭代次數η_max或經過η_maxNoimprove次連續迭代后當前解s沒有得到優化；

步驟10：輸出最優解s*。

2.根據權利要求1所述的面向大規模純電動公交車輛調度問題的自適應大型鄰域搜索方法，其特征在于，上述步驟1的具體過程為：

1.1將所有的行車任務依據其發車時刻的先后排列；

1.2依次選擇行車任務，根據行車任務所屬的公交線路找出該線路中的所有的車輛，依次計算插入成本，當車輛因電量不足而無法完成該任務時，嘗試在車輛的任務鏈中插入充電行程，車輛的充電過程在其所屬的停車場完成，每次充電的時間為兩個行程之間的最大空閑時間，如果當前車輛在插入充電行程后仍電量不足或該車輛無法插入充電行程，則改變當前車輛的車型然后檢查車輛是否會因電量不足無法完成任務鏈，若能夠完成則保留此種方案，若不能完成則繼續嘗試插入充電行程，若插入充電行程后仍不能完成任務鏈，則舍棄此種方案；在此過程中，將會依次更換可用的車型直到全部車型都被檢查一遍，待全部車型都被檢查完畢后，對每一種方案計算行程的插入成本，令插入行程之前的解為s₁，插入行程后的解為s₂，插入成本c可通過以下式子計算：

c＝f(s₁)-f(s₂)

式中f(s₁)和f(s₂)為將解代入目標函數得到的值，最終選擇插入成本最小的一輛車將行程插入；若當前所有車輛都不能執行此任務，將生成新的車輛執行該任務，在添加新的車輛時，計算不同車型在不同車場執行此任務的車輛購買及調度成本(包括電量消耗成本與時間成本)，并選擇成本最小的方案，

1.3重復步驟1.1和1.2，直到所有行程都插入至調度計劃中。

3.根據權利要求1所述的面向大規模純電動公交車輛調度問題的自適應大型鄰域搜索方法，其特征在于，上述步驟2所述的刪除算法包括隨機刪除(RandomRemoval)，時間相關刪除(Time-RelatedRemoval)以及鄰居刪除(NeighborRemoval)；每種刪除算法會根據算例中公交線路的數量決定刪除的行程數量，對于n條線路混合調度的情況，算法將會刪除這些線路中n*q個行程，q的取值范圍為[ξ_min,ξ_max]，刪除算法執行完畢后，算法將搜索執行行程任務少于p個的車輛，并刪除這些車輛執行的行程任務。