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

白士宇殷雪峰

(1.沈陽(yáng)工學(xué)院 遼寧省數(shù)控機(jī)床信息物理融合與智能制造重點(diǎn)實(shí)驗(yàn)室, 遼寧 撫順 113122；2.沈陽(yáng)工學(xué)院 信息與控制學(xué)院，遼寧 撫順 113122)

0 引言

物流配送在消費(fèi)活動(dòng)過(guò)程中與消費(fèi)者有密不可分的關(guān)系，在整個(gè)物流過(guò)程當(dāng)中，高效配送一直是物流行業(yè)的核心問(wèn)題之一，配送調(diào)度是否高效合理對(duì)于公司成本、收益都有至關(guān)重要的影響。由此可見(jiàn)，車輛調(diào)度優(yōu)化是物流的關(guān)鍵一環(huán)，對(duì)車輛進(jìn)行調(diào)度優(yōu)化的理論進(jìn)行分析和研究是當(dāng)代物流集約化、發(fā)展職能交通運(yùn)輸系統(tǒng)、建立新時(shí)代智能電子商務(wù)體系的重要基礎(chǔ)。

配送中心作為當(dāng)代整個(gè)物流系統(tǒng)的中樞系統(tǒng)，其配送調(diào)度的智能越來(lái)越多樣化，但是其根本工作職能依舊是對(duì)大批訂單多調(diào)度和控制[1]，其中主要包含生成合理、高效的調(diào)度方案，發(fā)送調(diào)度的執(zhí)行命令以及能夠向供應(yīng)商發(fā)送自動(dòng)補(bǔ)充貨源的指令，因此，作為現(xiàn)代物流體系核心之一的配送中心，其面臨的最困難的任務(wù)就是提交高效配送方案。

在1959年，Dantzig和Ramser首次提出了物流配送以及車輛優(yōu)化調(diào)度的相關(guān)問(wèn)題，問(wèn)題提出后，運(yùn)籌學(xué)、管理學(xué)、應(yīng)用數(shù)學(xué)、圖與網(wǎng)絡(luò)、計(jì)算機(jī)應(yīng)用科學(xué)等一系列相關(guān)學(xué)科的領(lǐng)域內(nèi)的專家和管理者對(duì)該問(wèn)題產(chǎn)生了極大的重視[2]，車輛調(diào)度優(yōu)化一時(shí)間成為了一個(gè)研究熱點(diǎn)問(wèn)題，在眾多科研人員努力之后，取得了一系列該課題的進(jìn)展和成果。而對(duì)于這個(gè)難點(diǎn)，研究學(xué)者經(jīng)常采用的方案有遺傳算法、職能優(yōu)化算法以及啟發(fā)式算法等一系列解決方法[3]。

本文嘗試采用混合量子遺傳算法求解該問(wèn)題，實(shí)驗(yàn)結(jié)果證明，混合量子遺傳算法是解決該問(wèn)題的一種有效的方案。

1 量子遺傳算法概述

1.1 量子計(jì)算及遺傳算法

1.1.1 量子計(jì)算

量子信息處理以及其計(jì)算過(guò)程是建立在量子比特基礎(chǔ)上的一種新型概念，量子比特常常被作為一種非常抽象的數(shù)學(xué)對(duì)象被科研學(xué)者進(jìn)行對(duì)待，文章通過(guò)介紹編碼的基本概念以及相關(guān)的特性，將車輛調(diào)度和配送量之間進(jìn)行關(guān)聯(lián)，從而將抽象的物理學(xué)概念和現(xiàn)實(shí)中的應(yīng)用工程建立起聯(lián)系[4]。

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

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

其中:α和β分別是左失和右矢的幅度，在實(shí)際操作量子比特的過(guò)程當(dāng)中，應(yīng)當(dāng)有以下的約束。

|α|2+|β|2=1

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

傳統(tǒng)QGA中，量子門(mén)的作用是使種群產(chǎn)生變異，其更新過(guò)程如下:

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

其中旋轉(zhuǎn)量子門(mén)U為：

根據(jù)設(shè)計(jì)的調(diào)整策略來(lái)給定旋轉(zhuǎn)角的大小和符號(hào)。

1.1.2 遺傳算法

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

遺傳算法的主要步驟為：首先構(gòu)造滿足一定約束條件的染色體，對(duì)數(shù)據(jù)進(jìn)行編碼，這個(gè)過(guò)程的目的主要是使優(yōu)化問(wèn)題的解形式與遺傳算法的運(yùn)算相適應(yīng)。在實(shí)際編碼過(guò)程中， 應(yīng)該盡可能的選取符合問(wèn)題的約束，否則將會(huì)對(duì)遺傳算法的計(jì)算效率產(chǎn)生較大的影響。編碼過(guò)程如下：

ouuty= Encoding(inputx)

其中：x為所輸入的數(shù)據(jù)，進(jìn)行一定方式的編碼后得到編碼輸出y。

第二步為產(chǎn)生初始化種群，選擇初始化種群的數(shù)量，其次是根據(jù)實(shí)際問(wèn)題的目標(biāo)函數(shù)進(jìn)行適應(yīng)度函數(shù)的選擇或構(gòu)造，通過(guò)計(jì)算每個(gè)染色體的適應(yīng)度反映出染色體的優(yōu)劣程度。假設(shè)f為目標(biāo)函數(shù)，F(xiàn)是相對(duì)適應(yīng)度，則若目標(biāo)函數(shù)為最大化問(wèn)題，則有：

F(x)=f(x)

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

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

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

1.2 混合量子遺傳算法的實(shí)現(xiàn)過(guò)程

在應(yīng)用當(dāng)中，量子算法和遺傳算法都是針對(duì)量子位進(jìn)行實(shí)現(xiàn)的，因此轉(zhuǎn)化到二進(jìn)制串僅僅是為了計(jì)算個(gè)體適配值，但是在函數(shù)優(yōu)化中存在大量針對(duì)二進(jìn)制直接編碼的操作，因此考慮傳統(tǒng)遺傳算法和量子算法進(jìn)行混合[10]，考慮采用如圖1所示的混合量子遺傳算法。

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

考慮將傳統(tǒng)二進(jìn)制編碼的BGA和實(shí)數(shù)編碼的RGA進(jìn)行混合，得到BQGA編碼方式。進(jìn)行隨機(jī)初始化第一代種群:

Gi(0)=randominit()

混合算法在縱向不斷將Gi(0)進(jìn)行迭代QGA搜索，采用單點(diǎn)交叉和算數(shù)交叉的方法，保留優(yōu)勢(shì)種群:

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

橫向?qū)γ恳淮M(jìn)行一定種群變換

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

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

2 車輛調(diào)度優(yōu)化問(wèn)題建模

對(duì)于最優(yōu)物流路徑的優(yōu)化問(wèn)題，我們可以將其用模型進(jìn)行概括。圖2是傳統(tǒng)的物流配送模式示意圖,而新型的物流調(diào)度模型為圖3所示。

圖2 傳統(tǒng)物流配送模式

首先從物流中心調(diào)度多輛汽車派往不同的客戶進(jìn)行送貨，此時(shí)每輛車的載重量是一定的，而每個(gè)客戶的位置以及需求也是確定的，因此問(wèn)題即為高效規(guī)劃一條車輛配送的路線，使得目標(biāo)函數(shù)得到優(yōu)化，此時(shí)每條路徑上的汽車總承載量要大于客戶的需求總量、每條路徑上的長(zhǎng)度要小于汽車配送的最大行駛距離，最關(guān)鍵的一點(diǎn)是所有客戶的需要要得到滿足，在送貨過(guò)程中只有一兩車進(jìn)行配送[11]。

圖3 新型物流配送模式

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

目標(biāo)函數(shù)可以表示為:

規(guī)定了每條路徑的總長(zhǎng)度不會(huì)大于貨車一次行駛的最遠(yuǎn)距離，約束了每條行駛路徑上的客戶總數(shù)小于等于總客戶的數(shù)量。

表明每個(gè)站點(diǎn)都會(huì)得到貨物的配送。限制單個(gè)客戶僅可有一輛貨車進(jìn)行送貨，而不能多個(gè)貨車進(jìn)行送貨。

上式說(shuō)明當(dāng)某貨車服務(wù)的站點(diǎn)數(shù)目大于等于1，則該貨車已經(jīng)作出了配送的行為。

3 基于路徑優(yōu)化的混合量子遺傳算法

3.1 編碼方法和適應(yīng)度研究

3.1.1 編碼方式研究

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

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

公式中的N代表了種群的大小，m為種群進(jìn)化的代的次數(shù)，對(duì)于所有的i值，均有：

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

量子遺傳算法采用了量子比特的形式來(lái)代表染色體，因此一個(gè)染色體可以同時(shí)用多個(gè)狀態(tài)信息來(lái)進(jìn)行表示，當(dāng)位數(shù)為M時(shí)，量子染色體即可以表示2^M個(gè)能夠發(fā)生的狀態(tài)，因此可以有效地保持種群的多樣性，在應(yīng)用中即表現(xiàn)為車輛調(diào)度優(yōu)化的更多可能性，能夠克服陷入局部收斂的結(jié)果。

3.1.2 適應(yīng)度研究

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

個(gè)體的適應(yīng)度就可以表示為：

F=1/(Z+K×Pw)

對(duì)于一個(gè)單獨(dú)的個(gè)體來(lái)說(shuō)，假設(shè)對(duì)應(yīng)的配送路徑的條數(shù)與送貨貨車的數(shù)量的差為K，目標(biāo)函數(shù)的數(shù)值為Z，K看作個(gè)體所對(duì)應(yīng)的送貨路徑中不可行的路線的數(shù)目，對(duì)于每一條不可行的路線存在一個(gè)懲罰因子Pw，懲罰因子的取值根據(jù)目標(biāo)函數(shù)來(lái)具體確定。

3.2 路徑優(yōu)化混合量子遺傳算法流程

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

圖4 混合量子遺傳算法圖

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

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

分別設(shè)定20個(gè)地區(qū)的坐標(biāo)如下：(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)，其客戶的需求依次設(shè)置如下：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 實(shí)驗(yàn)仿真及結(jié)果

4.1 實(shí)驗(yàn)描述

實(shí)際過(guò)程中，車輛調(diào)度的軟件環(huán)境如圖5所示。在本次實(shí)驗(yàn)過(guò)程中采用Matlab進(jìn)行仿真和測(cè)試，如圖6所示。

圖6 實(shí)驗(yàn)仿真環(huán)境

在具體實(shí)現(xiàn)過(guò)程中，為了進(jìn)行對(duì)比，傳統(tǒng)的量子遺傳算法的參數(shù)設(shè)置如下：設(shè)置初始種群的規(guī)模為50，每條染色體上的量子位數(shù)設(shè)置為2，種群最大迭代次數(shù)分別設(shè)置為1000次和2000次，懲罰權(quán)重為設(shè)置為100。

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

圖7 20個(gè)客戶的位置

4.2 實(shí)驗(yàn)結(jié)果

實(shí)驗(yàn)中將傳統(tǒng)的量子遺傳算法和混合量子遺傳算法相比較，得到結(jié)果如圖8所示，可以看出，在初始數(shù)據(jù)相同的情況下，同樣運(yùn)行5次取平均值，可以看出無(wú)論是1000次還是2000次迭代，混合量子遺傳算法的歸一化最佳適應(yīng)度的結(jié)果要明顯優(yōu)于傳統(tǒng)量子遺傳算法。

圖8 歸一化最佳適應(yīng)度曲線對(duì)比

其最佳的運(yùn)貨物流路徑為第一輛車為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；由于目標(biāo)函數(shù)經(jīng)過(guò)變換后得到的歸一化適應(yīng)度則可以反映出算法的優(yōu)劣。因此可以看出，混合量子遺傳算法得到的最優(yōu)解的效果要更好，在一定程度上優(yōu)化了車輛調(diào)度的問(wèn)題。圖9是車輛路線。

圖9 最佳路線

5 實(shí)驗(yàn)仿真及結(jié)果

對(duì)于車輛調(diào)度優(yōu)化的問(wèn)題，一般可以概括為:存在眾多的車輛卸貨點(diǎn)與車輛裝貨點(diǎn)，車輛調(diào)度中心選擇并組織高效的行車線路，使得運(yùn)貨車輛能夠成功依次通過(guò)不同節(jié)點(diǎn)，同時(shí)在滿足如貨物需求、交貨與發(fā)貨時(shí)間、車輛容量等一系列要求的情況下，達(dá)到如行車路程最短、花費(fèi)的成本最低、使用盡可能少的車輛等一系列目標(biāo)。

本文以車輛調(diào)度為模型，具體針對(duì)配送中心調(diào)度貨車進(jìn)行貨物配送進(jìn)行了分析和探討，通過(guò)建立簡(jiǎn)單明了的數(shù)學(xué)模型對(duì)復(fù)雜的問(wèn)題進(jìn)行簡(jiǎn)化和分析。通過(guò)本次實(shí)驗(yàn)，利用一個(gè)加入免疫算子的用于求解優(yōu)化車輛路徑的混合量子遺傳算法，對(duì)傳統(tǒng)的量子遺傳算法進(jìn)行優(yōu)化，通過(guò)實(shí)際實(shí)驗(yàn)對(duì)比，設(shè)置在相同的參數(shù)條件下， 改進(jìn)后的混合量子遺傳算法具有更好的性能表現(xiàn)，是一個(gè)能更有效地解決車輛調(diào)度路徑優(yōu)化問(wèn)題的算法。

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