[發明專利]基于混合量子算法的智慧車輛調度管理系統及其工作方法

在審

• 申請號: 201710809954.0
• 申請日: 2017-09-11
• 公開（公告）號: CN107609816A
• 公開（公告）日: 2018-01-19
• 發明（設計）人: 寧濤;房麗華;黃明;梁旭;焦璇
• 申請（專利權）人: 大連交通大學
• 主分類號: G06Q10/08
• 分類號: G06Q10/08;G06N3/00
• 代理公司: 大連東方專利代理有限責任公司21212
• 代理人: 李洪福

1.基于混合量子算法的智慧車輛調度管理系統，其特征在于：包括帶時間窗不確定車輛調度模塊、同時集送貨車輛調度模塊和動態車輛重調度模塊；

所述的帶時間窗不確定車輛調度模塊包括用戶時間窗設置模塊和不確定需求變化設置模塊，用戶時間窗設置模塊針對用戶提出的收貨時間區間以及用戶的重要等級來設置配送的優先級和設置初始方案；不確定需求變化設置模塊針對配送需求的模糊不確定問題設置不同的配送方案；

所述的同時集送貨車輛調度模塊包括送貨需求調度模塊和集貨需求調度模塊，送貨需求調度模塊對有同時集送貨的配送情況設置合理的送貨配送方案，集貨需求調度模塊對有同時集送貨的配送情況設置合理的集貨配送方案；

所述的動態車輛重調度模塊包括動態變化設置模塊和重調度操作模塊，動態變化設置模塊針對配送過程中可能出現的不同動態干擾因素進行分析以及設計相應的配送方案，調度操作模塊主要對配送過程必須修改初始調度方案的情況進行實時重調度方案的生成和更新。

2.基于混合量子算法的智慧車輛管理系統的工作方法，其特征在于：包括以下步驟：

A：求解帶時間窗不確定車輛調度問題

為了避免在搜尋過程中量子粒子群陷入局部最優解，在原有粒子群的基礎上創建兩個子相量子粒子群；兩個子相量子粒子群開始時在相反的方向以不同的速度進行局部尋優，而主相量子粒子群粒子速度的更新借助于當前被所有子相搜索到的全局最優點；實現的具體步驟如下：

A1：對粒子群的規模、慣性權值、加速系數、壓縮因子、所有粒子的初始位置和初始速度、允許的最大迭代次數、粒子群的子相數目以及每個子相的滾動優化結束指標和計數器進行初始化；所述的粒子群的規模為粒子群的粒子數目；

A2：根據目標函數對每個粒子的初始適應值進行評價、對每個粒子的初始個體歷史最優位置以及個體最優適應值進行保存，同時對初始全局歷史最優位置以及最優適應值進行保存；

A3：優化第i個子相粒子；

A4：判斷i是否超過粒子群相數，如果超過，則令i＝0，并轉到步驟A5；否則，令i＝i+1，然后轉到步驟A3；

A5：如果適應值的誤差已經達到設定的適應值誤差限或者執行的迭代次數超過允許的最大迭代次數，則優化終止，同時對全局歷史最優適應值和最優位置進行輸出；否則，轉到步驟A3，并繼續優化；

B：求解有同時集送貨需求的車輛調度問題

B1：生成初始解P(t)

基于混沌理論生成初始解，假設用Popu表示種群規模，用Sum表示客戶數量，用K表示配送車輛數目，則量子個體的編碼長度表示成n(Sum+K-1)，按如下步驟進行初始化：

B11：先生成Popu/10個初始解，然后根據二進制編碼方法將其映射為量子個體，從而產生種子量子個體；

B12：用混沌方法對剩余種群個體進行初始化；即初始化第i個量子個體具體的方法為：

λ₀＝1/Popu

并根據下式：

λ_i＝μλ_i-1(1-λ_i-1),λ₀∈[0,1],μ≥4.

計算λ_i，設α_ji＝λ_i，從而生成全部量子位的概率幅，并生成量子個體；

B13：令i＝i+1后，轉步驟B12，直至生成全部量子個體；

B2：由初始解P(t)生成二進制解R(t)

對初始解P(t)的每一個量子位的與[0，1]區間的隨機數r_j進行比較，如果那么該位的值為0，否則為1；

B3：對R(t)進行解碼和修正

解碼和修正分為2個階段：檢查是否有重復編碼或越界編碼階段以及對解碼后的線路進行修正和改進的階段；在前一階段，如果發現有編碼重復或越界的情況，就對這一整數對應的二進制串每位的值進行重新確定，直至沒有重復或越界的編碼；后一階段針對解碼后出現的不可行解或弱可行解進行改進；在此階段，假設線路k上的集貨量和送貨量用P(k)和D(k)表示，待選擇客戶集合用Customlist表示，改進的步驟如下：

B31：對線路k上的D(k)和P(k)進行計算，并記錄結果；

B32：弱可行檢查線路k，如果線路k不可行，那么刪除線路k上的若干個客戶，使之滿足弱可行的條件，并且在Customlist中保存刪除的客戶；如果P(k)＜＜Q且D(k)＜＜Q，就刪除線路k，并保存線路上的所有客戶到Customlist中；

B33：已有線路在確保弱可行前提下，用最臨近法把Customlist中的客戶插入到已有線路，如果已有線路中沒有位置插入，就生成一條新的線路，直至Customlist中的客戶為空；

B34：強可行檢查弱可行線路，如果條件不滿足，就找出不可行客戶，并對客戶的順序進行交換，直至轉換成可行解；否則，轉至步驟B35；

B35：使用Relocate,Exchange線路間或線路內的交換算子，對強可行線路進行改進，從而減少線路的長度；

B36：對量子染色體編碼進行更新；

B4：進行量子更新

對量子個體的適應度進行計算，將計算結果與已存在的精英量子個體進行比較，選擇并保存適應度最高的K個量子個體；兩點間的距離按以下公式計算：

δ1=|F(x0+δ0)-F(x0)|=dF(x0)dx·δ0]]>

導數決定了初始點迭代后的狀態是靠近或分離；對量子個體量子位的旋轉角進行計算，生成新的初始解P(t+1)；同時判斷計算的終止條件是否滿足，若滿足則終止，否則轉至步驟B2，即由初始解P(t)生成二進制解R(t)；

式中：x₀表示初始點，x₀+δ₀表示x₀的鄰點；

C、求解動態車輛重調度問題

在量子優化算法的基礎上引入經典的模擬退火算法的方法解決動態車輛重調度問題，具體步驟如下：

C1：令t1＝0，隨機生成具有N個客戶的種群Q(t1)，退溫速率為υ，仿真次數為t以及最大迭代次數為n；

C2：進行客戶點編號操作，并按照如下步驟優化路徑：

C21：初始化種群，并生成粒子個體空間中的位置和速度；

C22:計算種群內所有粒子的目標函數值，pbest是自身位置，gbest是目標函數值最小的粒子位置；

C23：計算所有粒子位置矢量的全局平均最優值mbest，并更新粒子位置；

C24:計算所有粒子的目標函數如下，同時對pbest、gbest進行更新；

式中：表示所有客戶懲罰成本之和，其中DTi車輛在客戶點i的延誤時間；

C25:判斷是否滿足終止條件，若滿足，則轉到步驟C26，否則轉到步驟C23；

C26:輸出gbest及與之相應的目標函數值，并終止計算；

C3：判斷i是否超過最大迭代次數n，如果超過，則執行步驟C8，否則執行步驟C4；

C4：對種群的全部客戶個體執行定步長抽樣模擬退火計算；

C5：按下式進行退火操作：

T_t+1＝υ*T_t

式中，υ表示退火速率，T_t表示當前溫度，t表示當前迭代次數；

C6：監測是否有動態需求信息提交調度中心，如果沒有，就按照客戶點編號對優化后結果進行解碼，執行步驟C3；否則，執行步驟C7；

C7：對調度系統中未完成的客戶信息進行統計，并插入動態客戶需求信息，轉步驟C2；

C8：輸出本次優化結果，并判斷是否得到當前最優解，如果是，則執行步驟C9，否則，轉入步驟C10；

C9：進行旋轉門更新量子比特種群，得到新的下一代種群Q(t1+1)，轉入步驟C2；

C10：對多次優化結果進行統計，終止計算。