基于越庫配送車輛調度的混合量子遺傳算法(QGA)研究

白士宇殷雪峰

(1.沈陽工學院 遼寧省數控機床信息物理融合與智能制造重點實驗室, 遼寧 撫順 113122；2.沈陽工學院 信息與控制學院，遼寧 撫順 113122)

0 引言

物流配送在消費活動過程中與消費者有密不可分的關系，在整個物流過程當中，高效配送一直是物流行業的核心問題之一，配送調度是否高效合理對于公司成本、收益都有至關重要的影響。由此可見，車輛調度優化是物流的關鍵一環，對車輛進行調度優化的理論進行分析和研究是當代物流集約化、發展職能交通運輸系統、建立新時代智能電子商務體系的重要基礎。

配送中心作為當代整個物流系統的中樞系統，其配送調度的智能越來越多樣化，但是其根本工作職能依舊是對大批訂單多調度和控制[1]，其中主要包含生成合理、高效的調度方案，發送調度的執行命令以及能夠向供應商發送自動補充貨源的指令，因此，作為現代物流體系核心之一的配送中心，其面臨的最困難的任務就是提交高效配送方案。

在1959年，Dantzig和Ramser首次提出了物流配送以及車輛優化調度的相關問題，問題提出后，運籌學、管理學、應用數學、圖與網絡、計算機應用科學等一系列相關學科的領域內的專家和管理者對該問題產生了極大的重視[2]，車輛調度優化一時間成為了一個研究熱點問題，在眾多科研人員努力之后，取得了一系列該課題的進展和成果。而對于這個難點，研究學者經常采用的方案有遺傳算法、職能優化算法以及啟發式算法等一系列解決方法[3]。

本文嘗試采用混合量子遺傳算法求解該問題，實驗結果證明，混合量子遺傳算法是解決該問題的一種有效的方案。

1 量子遺傳算法概述

1.1 量子計算及遺傳算法

1.1.1 量子計算

量子信息處理以及其計算過程是建立在量子比特基礎上的一種新型概念，量子比特常常被作為一種非常抽象的數學對象被科研學者進行對待，文章通過介紹編碼的基本概念以及相關的特性，將車輛調度和配送量之間進行關聯，從而將抽象的物理學概念和現實中的應用工程建立起聯系[4]。

在經典比特框架下，只有0和1兩種存在狀態，但是在量子學中，量子比特可以介于0和1兩種本征狀態之外的第三中疊加狀態，如下公式所示：

|ψ> =α|0>+β|1>

其中:α和β分別是左失和右矢的幅度，在實際操作量子比特的過程當中，應當有以下的約束。

|α|2+|β|2=1

量子態的相干性指的是兩種狀態的振幅相互可以干涉，如果將這種相干的特性應用在車輛配送的問題當中，則可以看作影響配送量的兩種不同的趨勢，一旦兩種α、β概率幅度改變，則量子比特|α|2和|β|2處于0和1的概率也會變化，映射到實際問題當中則是配送量發生變化，這樣就能夠表示出配送中心是否全額占有或者不完全占有，并且可以處于兩種狀態下的任意一個狀態，能夠極大地擴展信息搜索空間[5]。

傳統QGA中，量子門的作用是使種群產生變異，其更新過程如下:

[α'iβ'i]T=U·[αiβi]T

其中旋轉量子門U為：

根據設計的調整策略來給定旋轉角的大小和符號。

1.1.2 遺傳算法

遺傳算法是一種新型的并行計算尋優算法，它所基于的思想是達爾文進化論中的“適者生存”[6]，它利用這種思想將尋優問題的求解過程表示為不同“染色體”的適者生存的過程，通過“染色體”隨著迭代次數的增加不斷進化，在這個過程中產生復制、交叉、變異等一系列行為，最終收斂到問題的最優解或者滿意解的過程[7]。

遺傳算法的主要步驟為：首先構造滿足一定約束條件的染色體，對數據進行編碼，這個過程的目的主要是使優化問題的解形式與遺傳算法的運算相適應。在實際編碼過程中， 應該盡可能的選取符合問題的約束，否則將會對遺傳算法的計算效率產生較大的影響。編碼過程如下：

ouuty= Encoding(inputx)

其中：x為所輸入的數據，進行一定方式的編碼后得到編碼輸出y。

第二步為產生初始化種群，選擇初始化種群的數量，其次是根據實際問題的目標函數進行適應度函數的選擇或構造，通過計算每個染色體的適應度反映出染色體的優劣程度。假設f為目標函數，F是相對適應度，則若目標函數為最大化問題，則有：

F(x)=f(x)

其中:Cmin為f(x)的最小估計。

當適應度函數被確定下來后，今后的復制過程即為依據適應度大小的概率分布確定下一代中哪些染色體“適應生存”或者“不適者被淘汰”[8]。染色體的交叉同樣是進行遺傳的一個重要步驟，子代遺傳的基因是由父代染色體之間的交叉相互并入而產生的[9]。子代的產生不僅僅是一個生產過程，同樣是一個變異過程，在新的解產生后，隨著基因突變的發生，量子旋轉門U使得某些染色體的編碼發生了變化:

因此新的解會有更多可能性和更大的遍歷性。

1.2 混合量子遺傳算法的實現過程

在應用當中，量子算法和遺傳算法都是針對量子位進行實現的，因此轉化到二進制串僅僅是為了計算個體適配值，但是在函數優化中存在大量針對二進制直接編碼的操作，因此考慮傳統遺傳算法和量子算法進行混合[10]，考慮采用如圖1所示的混合量子遺傳算法。

圖1 混合量子遺傳算法分析框架

考慮將傳統二進制編碼的BGA和實數編碼的RGA進行混合，得到BQGA編碼方式。進行隨機初始化第一代種群:

Gi(0)=randominit()

混合算法在縱向不斷將Gi(0)進行迭代QGA搜索，采用單點交叉和算數交叉的方法，保留優勢種群:

Gi(n+1)=QGAsearch(Gi(n))

橫向對每一代進行一定種群變換

G'i(n)=Transform(Gi(n))

G'i(n)為同代變換后的種群，將種群進行擇優后，獲得優勢種群，橫向同樣可以采用多代搜索的方法。

2 車輛調度優化問題建模

對于最優物流路徑的優化問題，我們可以將其用模型進行概括。圖2是傳統的物流配送模式示意圖,而新型的物流調度模型為圖3所示。

圖2 傳統物流配送模式

首先從物流中心調度多輛汽車派往不同的客戶進行送貨，此時每輛車的載重量是一定的，而每個客戶的位置以及需求也是確定的，因此問題即為高效規劃一條車輛配送的路線，使得目標函數得到優化，此時每條路徑上的汽車總承載量要大于客戶的需求總量、每條路徑上的長度要小于汽車配送的最大行駛距離，最關鍵的一點是所有客戶的需要要得到滿足，在送貨過程中只有一兩車進行配送[11]。

圖3 新型物流配送模式

將此過程用數學模型確立，假設總調度中心有量貨車，第k量火車的承重為Qk(1，2，3，…，C)，一次送貨的行駛距離最遠Dk，總共要求運往L個站點，其中每個站點需要qi(1，2，3，…，L)，兩個站點之間的間距可以表示為dij(i，j=1，2，3，…，L)，中心到各個站點的距離表示為d0j(i，j=1，2，3，…，L)。再設置為第輛貨車配送的需求點(nk=0表示未使用的第k輛汽車)，并且第輛汽車的行進路線表示Rk，Rk中的元素表示需求點rki在路徑Rk中的順序為i。物流中心則表示為rk0=0，目標函數取到最優時，配送距離可以達到最短，因此可以建立起車輛調度優化問題的基本數學模型。

目標函數可以表示為:

規定了每條路徑的總長度不會大于貨車一次行駛的最遠距離，約束了每條行駛路徑上的客戶總數小于等于總客戶的數量。

表明每個站點都會得到貨物的配送。限制單個客戶僅可有一輛貨車進行送貨，而不能多個貨車進行送貨。

上式說明當某貨車服務的站點數目大于等于1，則該貨車已經作出了配送的行為。

3 基于路徑優化的混合量子遺傳算法

3.1 編碼方法和適應度研究

3.1.1 編碼方式研究

如前所述，在量子計算中存儲信息的最小單元是量子位或量子比特，而量子位可能處于不同的狀態0或1，也可能是兩種狀態的線性疊加[12]。

在混合量子遺傳算法中，第m代種群Q(m)中的一個長度為M位的量子比特的個體可以用下式進行表示：

公式中的N代表了種群的大小，m為種群進化的代的次數，對于所有的i值，均有：

|αi|2+|βi|2=1

量子遺傳算法采用了量子比特的形式來代表染色體，因此一個染色體可以同時用多個狀態信息來進行表示，當位數為M時，量子染色體即可以表示2^M個能夠發生的狀態，因此可以有效地保持種群的多樣性，在應用中即表現為車輛調度優化的更多可能性，能夠克服陷入局部收斂的結果。

3.1.2 適應度研究

對于某一車輛的具體配送方案，如果需要判斷其是否優秀，首先要使其滿足一定的約束條件，其次要正確計算問題的目標函數[13]。本文嘗試采用的是將客戶進行直接排列的編碼方式，確定其配送方案，因此每個客戶都可以得到配送的服務，此外假定了每個客戶僅由一臺車輛進行配送的約束，該方案同時滿足了每條行車路徑上的各個站點的需求量會小于等于單個車輛進行一次送貨的最大運貨量的約束，但是其無法對配送路徑的數量小于送貨車數進行限制。

個體的適應度就可以表示為：

F=1/(Z+K×Pw)

對于一個單獨的個體來說，假設對應的配送路徑的條數與送貨貨車的數量的差為K，目標函數的數值為Z，K看作個體所對應的送貨路徑中不可行的路線的數目，對于每一條不可行的路線存在一個懲罰因子Pw，懲罰因子的取值根據目標函數來具體確定。

3.2 路徑優化混合量子遺傳算法流程

整個混合量子遺傳算法如圖4所示。

圖4 混合量子遺傳算法圖

首先初始化量子比特種群，之后通過初始的量子比特種群產生二進制種群，對于不可行解，我們采用修復函數對其進行修正，使其可解，將得到的二進制數據進行解碼后，得到每個車輛生成的線路，得到線路后加入免疫因子使其再優化，篩選較好的路徑，之后對每條路徑進行評價，挑選出其中最佳的個體(行駛路徑)，之后進行量子旋轉門的更新，判斷是否滿足停止條件，從而進行算法的迭代或終止。

假定存在一個調度中心共有5輛貨車，每輛貨車的最大承重均為8噸，每輛車每次配送的最遠距離為50，需要向20個客商進行配送。調度中心的坐標設定為(14.5，13.0)，每個客戶的需求與其需求的關系如表所示，根據此選擇最佳的送貨路線，使得送貨距離的值最小。

分別設定20個地區的坐標如下：(12.8,8.5)，(18.4,3.4)，(15.4,16.6)，(18.9,15.2)，(15.5,11.6)，(3.9,10.6)，(10.6,7.6)，(8.6,8.4)，(12.5,2.1)，(13.8,5.2)，(6.7,16.9)，(14.8,2.6)，(1.8,8.7)，(17.1，11.0)，(7.4,1.0)，(0.2,2.8)，(11.9,19.8)，(13.2,15.1)，(6.4,5.6)，(9.6,14.8)，其客戶的需求依次設置如下：0.1，0.4，1.2，1.5，0.8，1.3，1.7，0.6，1.2，0.4，0.9，1.3，1.3，1.9，1.7，1.1，1.5，1.6，1.7，1.5。

4 實驗仿真及結果

4.1 實驗描述

實際過程中，車輛調度的軟件環境如圖5所示。在本次實驗過程中采用Matlab進行仿真和測試，如圖6所示。

圖6 實驗仿真環境

在具體實現過程中，為了進行對比，傳統的量子遺傳算法的參數設置如下：設置初始種群的規模為50，每條染色體上的量子位數設置為2，種群最大迭代次數分別設置為1000次和2000次，懲罰權重為設置為100。

在添加免疫算子參數后的混合量子遺傳算法中，將接種率設置為50%，其余基本參數設置與傳統量子遺傳算法相同。

圖7 20個客戶的位置

4.2 實驗結果

實驗中將傳統的量子遺傳算法和混合量子遺傳算法相比較，得到結果如圖8所示，可以看出，在初始數據相同的情況下，同樣運行5次取平均值，可以看出無論是1000次還是2000次迭代，混合量子遺傳算法的歸一化最佳適應度的結果要明顯優于傳統量子遺傳算法。

圖8 歸一化最佳適應度曲線對比

其最佳的運貨物流路徑為第一輛車為0—18—17—3—4—14—0；第二輛貨車的路徑為0—20—11—6—13—16—19—0；第三輛車的路徑為0—7—8—15—9—12—2—10—1—0；第四輛車的路徑為0—5—0；由于目標函數經過變換后得到的歸一化適應度則可以反映出算法的優劣。因此可以看出，混合量子遺傳算法得到的最優解的效果要更好，在一定程度上優化了車輛調度的問題。圖9是車輛路線。

圖9 最佳路線

5 實驗仿真及結果

對于車輛調度優化的問題，一般可以概括為:存在眾多的車輛卸貨點與車輛裝貨點，車輛調度中心選擇并組織高效的行車線路，使得運貨車輛能夠成功依次通過不同節點，同時在滿足如貨物需求、交貨與發貨時間、車輛容量等一系列要求的情況下，達到如行車路程最短、花費的成本最低、使用盡可能少的車輛等一系列目標。

本文以車輛調度為模型，具體針對配送中心調度貨車進行貨物配送進行了分析和探討，通過建立簡單明了的數學模型對復雜的問題進行簡化和分析。通過本次實驗，利用一個加入免疫算子的用于求解優化車輛路徑的混合量子遺傳算法，對傳統的量子遺傳算法進行優化，通過實際實驗對比，設置在相同的參數條件下， 改進后的混合量子遺傳算法具有更好的性能表現，是一個能更有效地解決車輛調度路徑優化問題的算法。

這種算法不僅僅能夠解決調度中心的貨物配送問題，同時也可以應用在其他背景下去解決相應的組合優化問題，對貨物的供應鏈管理以及調度有很大的借鑒和參考價值，本文中所展示的混合量子遺傳算法在求解優化問題上具有較為廣闊的發展前景，值得深入研究。