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

有效

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

本發明公開了一種面向大規模純電動公交車輛調度問題的自適應大型鄰域搜索方法，純電動公交車輛調度問題是含有多約束的復雜問題，求解過程的計算量隨著問題的規模呈指數增長。本發明采用自適應大型鄰域搜索算法，通過改良刪除和插入算法并增加局部搜索步驟，使得此方法能夠求解考慮多車場多車型的復雜公交車輛調度問題，彌補了這一問題求解方法的空缺，并能夠以較高的效率為電動公交車輛的選購和排班問題提供解決方案，能夠用于大規模的公交車輛調度問題求解。

技術領域

本發明涉及一種面向大規模純電動公交車輛調度問題的自適應大型鄰域搜索方法，屬于公交車輛調度技術領域。

背景技術

公交車輛調度問題是一種典型的車輛調度問題，一般定義為：在給定的停車場，給定的行程時間表和給定的車型下，找到在所有行程都能夠被執行的條件下，使得總運營成本最低時每輛車的任務鏈。對于純電動公交車輛的調度問題，還需要考慮車輛續航里程限制以及補充電量的約束。同時，考慮到目前公交系統的規模較大，以及純電動公交車型的多樣化，往往涉及多個車場、多個車型情況下的車輛調度問題。另外，為了更貼近實際的公交調度過程，在給出純電動公交車輛調度問題的解決方案時，還需要考慮各條線路之間的車輛是否共用，以及在運營過程中允許車輛部分補充電量的行為。這些因素不僅增加了問題的復雜程度，更為問題的求解造成了相當大的困難。

本發明面向的大規模純電動公交車輛調度問題可定義為：在給定的數個公交停車場、給定的數個純電動公交車型以及數條給定的公交線路下，決定公交車隊的車輛配置方案，并求出在所有公交線路的行程都能夠被執行的條件下，使得總運營成本(包括車輛購買成本與調度成本)最低時每輛車的調度和充電計劃，車輛在每次充電過程中，須返回所屬的停車場充電，充電時的電量是任意的。

純電動公交車輛調度問題的數學模型如下所示：對于一個有向圖G＝(V,A)，V代表有向圖中所有的節點，A代表有向圖中所有的連接。定義S為所有行車任務的集合，對于每個行車任務i∈S，其開始時間為z_i，持續時間為t_i。用表示k車型執行任務i的耗電量，在執行i任務之前的電量定義為對于每一個公交線路組合g，g∈G，都包含一條或幾條公交線路的行車任務，定義n為公交線路組合的數量，則S＝{S₁,S₂,…,S_n}。定義D為停車場的集合，對于每一個停車場β∈D，有o_β和d_β兩個節點分別表示起始點和終點，q^β為停車場的最大停車數。最后，定義f∈F為所有充電事件的集合，對于每一個充電事件f，其開始時間記為z_f，充電電量記為為了保證在運營過程中充電設備不出現擁擠的情況，規定車輛只能返回其所屬的停車場充電。定義K為車輛類型的集合，對于每一個車型k∈K，都有其最大電池電量E^k，耗電速度τ_k，充電速度u_k和購買成本c_k。令σ代表安全電量水平占最大電池電量的百分比。對于調度計劃中的成本計算，c_t代表執行行程任務和空駛行程的單位時間成本，代表車輛的單位電量成本。

定義為0-1變量來表示有向圖中的連接，其中a＝(i,j)是圖中任意兩個節點的連接弧，當時，表示屬于β車場的k型車輛經過了圖中a弧上的i,j兩點。為了簡化描述，定義Δ⁺(i)/Δ^-(i)代表從節點i出發/到達的連接弧。