基于量子蟻群算法的隨機需求的動態車輛路徑問題

寧濤,焦璇,魏瑛琦,梁旭

(1.大連交通大學 軟件學院，遼寧 大連 116054; 2.大連東軟信息學院 會計學院,遼寧 大連 116023)*

0 引言

車輛路徑問題(Vehicle Routing Problem，VRP)自1959年Dantzig和Ramser[1]提出以來，受到研究者們廣泛關注.在物流配送中可能出現新增客戶點、原客戶點的需求發生改變、交通堵塞或天氣狀況等問題而重新調整配送路線，這類問題即為動態車輛路徑問題(Dynamic Vehicle Routing Problem,DVRP).近年來國內外學者在該問題上進行了相關研究，Zhiwei Yang[2]等針對車輛配送過程中需求變更或時間窗變更的情況提出了一種多重蟻群算法，該算法具有強大的局部搜索能力.Briseida Sarasola[3]等研究了隨機需求或需求動態變更的車輛路徑問題，提出了可擴展的變鄰域搜索算法.Yinan Guo[4]等針對帶有硬時間窗口和隨機需求的車輛路徑問題，提出了局部優化策略的魯棒動態車輛路徑方案.Nicolas Zufferey[5]等研究了擴展環境下的動態車輛路徑問題.寧濤[6]針對動態車輛問題提出了車輛鏈和貨物鏈的雙鏈量子編碼方法和改進的多向量子粒群算法.Michalis Mavrovouniotis[7]針對用蟻群算法求解動態車輛路徑問題提出了新的方案，該方案能夠保證種群的多樣性，避免過早收斂.Tao Ning 等[8]針對需求變更的動態車輛路徑問題，提出了一種基于可變鄰域搜索的元啟發式來求解.M. Schyns[9]等提出一種基于蟻群系統的算法來處理動態時間窗口，分離交付和異構車隊的車輛路徑問題.Jalel Euchi[10]等提出了一種基于2_Opt本地搜索的人造蟻群來解決動態車輛路徑問題.S. Masrom[11]等提出將動態參數化突變和交叉算子與粒子群算法相結合.

本文提出了用量子蟻群算法來求解隨機需求的動態車輛路徑問題，建立了兩階段模型，將DVRP轉化成了靜態VRP，考慮到客戶對物流配送的滿意程度，本文引入了模糊隸屬度函數.

1 問題描述

隨機需求的DVRP階段的數學模型可被描述為由1個配送中心和L個已知客戶點組成，派出K輛車對L個客戶點進行服務，K輛車從配送中心出發，完成配送任務后再返回配送中心，K輛車均為同一車型，具有相同的車載量Q.

具體定義如下：

L:初始階段客戶總數，i={0，1，2，…，L} ；其中i=0表示配送中心，i=1，2，…，L表示客戶點；K表示配送中心車輛數，K={1，2，…，K}；F表示派出一輛車的固定成本；Q表示車輛最大容載量；qi表示每個客戶的需求；dij表示從i到j距離；cij表示從i到j的單位運輸費用；ωijk表示車輛K從i到j的運輸量.

決策變量定義如下：

目標函數如下：

(1)

其中,Z為衡量客戶滿意度的度量，取值范圍為0～1，本文將最小化車輛費用與最小化客戶不滿意度相加求和，但Z的數量級與車輛配送成本的數量級相差甚遠，所以本文采用公式α=F×β將客戶滿意度與車輛配送費用變為同一數量級別，本文β取0.5.

約束條件：

含義如下：式(1)為目標函數，式(2)為車輛能力約束，式(3)表示每個客戶都被服務一次，式(4)、(5)表示客戶被且僅被一輛車服務，式(6)表示車輛從i到j的運輸量大于客戶j的需求量.

2 改進量子蟻群算法

蟻群算法是一種具有較強尋優能力且魯棒性強的算法，但當種群規模較大時，容易陷入局部最優，許多研究者將蟻群算法與其他算法結合，量子算法是近年來研究的熱點，該算法因其優越的編碼方式能夠同時表達多個態的疊加，事實證明，該算法在求解組合優化問題上具有明顯的優勢，本文將量子算法與蟻群算法結合并，用改進的量子蟻群算法(QACO)來求解隨機需求的DVRP.

2.1 狀態轉移規則

(7)

其中,l表示所有可能的取值;τij為邊弧(i,j)的軌跡強度;α(α>0)為信息啟發式因子，表示軌跡的相對重要性 ,其值越大,螞蟻越傾向于選擇有較多螞蟻經過的路徑;ηij為邊弧(i,j)的能見度，其表達式為：

(8)

其中,dij為相鄰兩個客戶間的距離;β(β>0)為期望的啟發式因子, 表示能見度的相對重要性, 其值越大螞蟻越傾向于選擇路徑較短的路徑;μj為客戶節點j的量子信息強度, 其表達式為：

(9)

2.2 信息素的更新

螞蟻在進行路徑搜索的過程中，之前路徑上的信息素會不斷的揮發，而螞蟻在走過的路徑上會釋放新的信息素，信息素的更新方程為：

τij=(1-ρ)τij+Δτij

(10)

(11)

(12)

Q為信息素量，是一個常值，Lk為第k只螞蟻已經構建路徑的長度，本文把量子概率幅引入，在進行信息素更新時，螞蟻經過的路徑上量子信息素會越來越多，而螞蟻未經過的路徑隨著量子信息素的揮發，該路徑上所剩的量子信息素會越來越少，這將導致不同的邊量子信息素相差越來越大，容易陷入局部最優.本文設計的量子信息素更新策略會隨著螞蟻構建的路徑的增加，量子信息素所增加的量將逐漸減少，從而避免某條邊上信息素積累過多導致陷入局部最優的問題.

2.3 算法步驟

(1)初始調度階段：

步驟3：如果螞蟻k=(k=1,2,…,n)走完全部客戶點即所有客戶點都在當前解集中，記下螞蟻個數Nk；

步驟4：計算各目標函數Wk(k=1,2,…,m)，得到當前最優解；

步驟5：對各邊信息素進行更新，用量子Hε門對量子蟻群進行更新；

步驟6：判斷當前迭代次數是否達到最大迭代次數，否則轉步驟2；

步驟7：輸出當前得到的最優解.

(2)動態優化階段：

步驟1：執行初始調度階段的配送方案并更新客戶信息；

步驟2：若有新的客戶請求出現，判斷新增客戶點數量是否達到上限，若達到上限，轉到步驟3，否則判斷是否到達下一重調度時間點，若到達下一重調度時間點，執行步驟3，否則轉到步驟1；

步驟3：根據模糊需求概率公式判斷是否將該客戶點插入到當前配送路徑中，如果S大于下一客戶點需求量的臨界值，則將該點插入到當前路徑中，用量子蟻群算法生成新路徑，否則轉到步驟4；

步驟4：新增車輛來完成新增客戶點的配送任務.

3 仿真實驗

仿真實驗借助Matlab7.0軟件來驗證改進的量子蟻群算法的可行性和有效性，本文以一個配送中心坐標為(300，270)、14個靜態客戶點、4個動態客戶點為例，配送區域為450 km×450 km的正方形區域，重調度周期為1 h，對隨機需求的動態車輛路徑問題進行仿真實驗，不同客戶的位置如表1和表2所示.

表1 14個靜態客戶的地理坐標

表2 4個動態客戶的地理坐標

圖1靜態階段配送路線圖2動態階段配送路線

(2)在某時間片內增加了a、b、c、d四個動態客戶點，根據動態階段重調度策略，將新增客戶點插入到當前配送路徑中，可得更新后的配送路徑如圖2所示.

(3)根據圖2的路線圖生成的動態階段重調度表如表3所示.

表3 動態重調度表

4 結論

本文提出將量子計算與蟻群算法相結合并加以改進，求解隨機需求的DVRP問題.對各路徑上的信息素進行量子比特編碼，采用Hε門對量子蟻群更新；為了避免搜索陷入局部最優，改進了信息素更新方程.采用重調度判斷公式來處理新增客戶點問題，最后進行Matlab仿真實驗，驗證了本算法在求解隨機需求的動態車輛路徑問題上的有效性.