徐廷學，張海軍，付霖宇，劉崇屹

（海軍航空大學，山東 煙臺 264001）

0 引言

配送車輛的路徑問題（Vehicle Routing Problem，VRP）是Dantzig 和Ramser［1］在1959 年提出來的。所謂VRP，一般指的是：調(diào)用多輛車輛，從車場出發(fā)，對客戶組織適當?shù)男熊嚶肪€，有序地訪問所有客戶并且只訪問一次，在滿足所有設(shè)定的約束條件下，力爭實現(xiàn)所設(shè)定的目標。

帶時間窗約束的車輛路徑問題（VRPTW）是車輛路徑問題（VRP）的基拓展與延伸，廣泛應(yīng)用于資源配置和物流運輸?shù)确矫?。求解VRPTW 的算法大致可以分為精確算法和啟發(fā)式算法兩類［2-3］。精確算法（Accurately Arithmetic）在求解規(guī)模較小的路徑優(yōu)化問題時，能夠在可承受的空間與時間消耗下得到精確解。但是配送路徑優(yōu)化問題屬于NP 問題，實際求解過程中問題的規(guī)模較大，使用精確算法所消耗的空間和時間成本都是比較大的。而啟發(fā)式算法（Heuristics）不管是求解小規(guī)模的問題還是大規(guī)模的問題，都能夠在一定的范圍和較短的時間內(nèi)給出滿意解或最優(yōu)解。因此，目前相關(guān)領(lǐng)域的專家以及研究人員，對于求解算法的主要研究方向是啟發(fā)式算法，特別是對現(xiàn)代啟發(fā)式算法的研究。

蟻群算法作為現(xiàn)代啟發(fā)式算法之一，自從被提出之后就受到了廣泛的關(guān)注，該算法具有正反饋性、并行性和魯棒性等優(yōu)點，在解決任務(wù)分配、路徑優(yōu)化等問題時表現(xiàn)出了良好的性能，但同時蟻群算法也存在一定的缺陷，如在解決大規(guī)模的問題時，會出現(xiàn)運算時間長、收斂速度慢、容易陷入局部最優(yōu)解等問題［4］。本文在基本蟻群算法的基礎(chǔ)上進行合理改進，將量子計算的理念與方法融入蟻群算法，提高了算法的性能，首先，改進后的算法更加科學地初始化螞蟻的位置，使螞蟻有更大可能性地尋找到最優(yōu)路徑。然后，在搜索的過程中添加量子比特啟發(fā)式因子，同時，使用局部信息素更新和全局信息素更新相結(jié)合的信息素更新方式，并且全局信息素更新添加了量子旋轉(zhuǎn)門的新模式。最后使用2-opt 搜索對結(jié)果進行進一步地探索，擴大搜索的范圍，增加了得到最優(yōu)解的概率。使新建立的量子蟻群算法能夠?qū)崿F(xiàn)對模型更加高效的求解。

1 問題描述及數(shù)學建模

1.1 偏離時間約束時的懲罰函數(shù)

在VRPTW 中目標函數(shù)注重的成分，除了行駛路程的長短以及消耗時間的多少之外，更為注重限定時間的約束，前者帶來的是配送車輛行進產(chǎn)生的成本消耗，而后者帶來的是違反限定時間之后造成的懲罰花費，通常來講，后者尤為重要。當從配送中心出發(fā)的配送車輛沒有按照限定時間將物資送達客戶手中時，就會產(chǎn)生懲罰花費，而車輛抵達的時間和限定時間相差越大，那么產(chǎn)生的代價就越大。懲罰的代價會隨著時間差的增大而呈現(xiàn)線性或者是指數(shù)等變化［5］，這種變化是由現(xiàn)實中的狀態(tài)而決定的。

在VRPTW 的模型建立中，會將懲罰函數(shù)作為其中的約束之一，這里要對模型中的懲罰函數(shù)作出合理規(guī)化。作出的懲罰函數(shù)如下：

式（1）懲罰函數(shù)如圖1 所示。

圖1 VRPTW 模型中懲罰函數(shù)

1.2 VRPTW 模型的建立

VRPTW 是從同一車場出發(fā)的多輛車輛按照約定好的時間訪問多個客戶進行運送貨物的問題。已知出發(fā)車場的位置以及需要訪問的客戶的位置，客戶的數(shù)量以及需求數(shù)量，客戶約定好的時間段，車輛的數(shù)量以及負載數(shù)量，對客戶組織適當?shù)男熊嚶肪€，有序地訪問所有客戶并且只訪問一次，在滿足所有設(shè)定的約束條件下，力爭實現(xiàn)所設(shè)定的目標（車輛所走的路徑最短或者花費最少）。

將現(xiàn)實問題轉(zhuǎn)化為數(shù)學模型，可以將VRPTW表述為m 輛車，從車場0 啟程按照設(shè)定好的實踐訪問n 個客戶進行運送貨物的問題。設(shè)di（i=1，2，…，n）為客戶i 的需求數(shù)量；cij（i，j=1，2，…，n）為車輛從顧客i 到顧客j 的運送花費，如果i=0 或是j=0，那么就表示從配送中心到某部隊或是從某部隊到配送中心；bk為車輛k 的裝載數(shù)量；設(shè)定的時間窗為［ei，li］；si代表配送車輛抵達客戶i 的時間；ti為配送車輛在卸載物資之前的停留時間；tij為配送車輛從客戶i 行進到客戶j 的消耗時間；μi為卸載物資所消耗的時間；第k 輛車對nk個客戶實行了服務(wù)，Rk為它的行進線路，rki表示Rk其中的一個客戶，在其行進線路里排位為i，rk0和rk（nk+1）都代表配送中心；這里將所有車輛的速度統(tǒng)一為v。

根據(jù)相關(guān)的設(shè)定以及相應(yīng)問題的描述，可以建立數(shù)學模型如下：

其中：式（2）是目標函數(shù)；式（3）表示每個配送車輛服務(wù)的所有客戶的總的需求量不大于車輛的額定運載量；式（4）代表行進的每一個線路上的客戶數(shù)量不大于總的客戶數(shù)量；式（5）表示每一個客戶都要被訪問到；式（6）代表配送車輛行進線路上服務(wù)到的客戶；式（7）表示每個客戶只能被一個配送車輛服務(wù)；式（8）代表配送車輛抵達客戶i 的時間點加上車輛在客戶i 的卸載前的停留時間，加上其卸載的時間，加上從客戶i 到客戶i+1 的行進時間，即為抵達客戶i+1 的時間點；式（9）表示車輛在客戶i 的卸載前的停留時間為正數(shù)；式（10）表示配送車輛k必須要在最遲限定時間抵達；式（11）表示在第k 輛車服務(wù)的客戶不小于1 時，該車參與了任務(wù)，這個時候sign（nk-1）=1，而在第k 輛車服務(wù)的客戶小于1時，代表該車沒有參與任務(wù)，這個時候sign（nk-1）=0。式（12）代表懲罰函數(shù)，代表配送車輛要在限定時間抵達，這個已經(jīng)在前節(jié)詳細說明了，在此不多贅述。

2 基于量子計算的蟻群算法設(shè)計

2.1 量子計算原理及運用

一個量子比特能夠同時儲存0 與1，那么擁有m 個量子比特的量子位就能夠儲存2m種可能的數(shù)據(jù)，擁有m 個量子比特的個體j 的概率幅度能夠表達為

2.2 算法設(shè)計

針對在求解VRPTW 時蟻群算法存在的缺陷，本文改善蟻群算法以提高其求解VRPTW 的性能。

2.2.1 轉(zhuǎn)移概率的改進

螞蟻k 依據(jù)轉(zhuǎn)移概率pijk隨機選擇的節(jié)點，這里將pijk設(shè)定為：

其中，dij代表節(jié)點i 與j 節(jié)點之間的距離；β（β≥0）是吸引度因子，代表吸引度的重要程度，β 的值越大，螞蟻就會更傾向于沿著路程較短的線路前進；μj是客戶點上量子信息的強度，它的表達式為

2.2.2 信息素更新方式

針對蟻群算法在信息素更新過程中存在的問題，這里依然使用局部信息素更新和全局信息素更新相結(jié)合的信息素更新方式，并且，全局信息素更新添加了量子計算的新模式。

1）局部更新

在構(gòu)筑最優(yōu)路徑的過程中，螞蟻每經(jīng)過邊（i，j）都會依照下面的信息素更新公式來更新這條邊上的信息素：

2）全局動態(tài)更新

當?shù)淮瓮瓿珊?，按下式對此次迭代得到的最?yōu)路徑上的信息素實行全局更新：

式中，Q 是一個（1≤Q≤10 000）的常數(shù)。

2.2.3 局部搜索策略

為了能夠增加算法的開拓性，本文在所有車輛對路徑選擇完成之后選用2-opt 搜索作為局部搜索的策略，而2-opt 搜索只用于一輛車所選擇的路徑之中。

2.3 算法運行步驟

Step 4：信息素的局部更新。每當車輛實行一次選擇，就依據(jù)式（19）對之前行駛的路徑（i，j）實行信息素的局部更新。

Step 6：對所有螞蟻的目標函數(shù)值Zk（k=1，2，…，m）實行計算，記錄當前最優(yōu)化的解；

Step 7：依據(jù)式（20）對各個邊的實行信息素的全局更新；

Step 8：運用式（21）更新節(jié)點上的量子信息；

Step 10：如果t＜tmax，那么轉(zhuǎn)Step 2；

Step 11：輸出當前的最優(yōu)解。

3 實例仿真

3.1 問題的提出

某公司周年慶典，其下屬實體店鋪都要承擔一定促銷活動，公司對下屬實體店統(tǒng)一進行貨物配送，配送中心根據(jù)各個店鋪申請的器械與物資，以及各店鋪擔負任務(wù)的重要程度，對其進行有力的配送保障，將店鋪所需器械、物資按照限定好的時間送到各個店鋪，為了簡化便于求解，這里設(shè)定配送中心僅有一個，而共有11 個店鋪參與任務(wù)，設(shè)定配送中心編號為0，11 個店鋪隨機編號1 到11，根據(jù)各店鋪需求配發(fā)至各店鋪的器械、物資重量以及設(shè)定時間窗如下頁表1 所示，重量單位為噸（t），配送中心與各店鋪的距離以及各店鋪相互之間的距離如表2 所示，單位為公里（km），車輛額定的載重量bk為10 t。根據(jù)配送的實際情況，結(jié)合各店鋪申請的信息，上級部門如何統(tǒng)規(guī)協(xié)調(diào)，才能使各配送車輛的線路與抵達店鋪的時間節(jié)點合理化，在滿足設(shè)定好的時間窗的情況下，運用最少的配送車輛，使車輛的總行程最短、成本花費最少，并且能夠保證任務(wù)的圓滿進行。

表1 各店鋪需求量

表2 配送中心與店鋪以及店鋪與店鋪之間的距離表

3.2 案例的概括歸納

為了使案例的研究能夠?qū)Ω喱F(xiàn)實問題的求解都有一定借鑒作用，可以將案例的問題條件歸納為一種帶時間窗的配送車輛路徑問題模型：

1）通常供應(yīng)保障的配送中心為一個，并且配送中心和各個店鋪的位置都是已知的，所有配送車輛從配送中心啟程，將貨物送達各店鋪之后，返回配送中心。

2）參與任務(wù)的全部店鋪都申請了器械和物資，它們的需求量不為0，車輛運載的物資是可以混裝的（為配送中心配發(fā)的不同類型的器械和裝備）；

3）配送中心按照各店鋪申請的物資數(shù)量以及要求時間統(tǒng)規(guī)協(xié)調(diào)，派遣車輛物資送到各個店鋪，根據(jù)各店鋪的需求，配送中心對各店鋪配送物資的數(shù)量是已知的；

4）不考慮車輛的運行狀態(tài)以及發(fā)生故障等情況，其種類、型號、速度都設(shè)為一致。車輛運載物資的最大載重量是已知的，并且車輛運載物資的數(shù)量都是按最大載重量裝載物資；

5）每個店鋪對于器械物資的申請都有著時間的限定，設(shè)定的時間由上級單位依據(jù)各店鋪的申請結(jié)合總體狀況進行決定，在設(shè)定的時間窗中，如果設(shè)定的為硬時間窗，有時候得不到一個可行解，因而，多數(shù)情況為了能夠得到可行的方案，都是設(shè)為軟時間窗。

6）器械物資供應(yīng)充足。首先在應(yīng)對一些緊急任務(wù)時，上級單位以及配送中心都有相應(yīng)準備，保證有著充足的器械物資可以保障各個店鋪，不會出現(xiàn)供應(yīng)量不足的狀況。

7）一個店鋪只能由一輛車且只能由一輛車完成配送任務(wù)，當車輛運載的物資剩余量滿足不了下一個店鋪的需求時，車輛返回配送中心。

8）當所有店鋪的需求都得到滿足，配送任務(wù)完成之后，所有的車輛全部返回配送中心。

3.3 對案例的求解

使用Matlab 進行編程，并在CPU 為Inte（lR）Core（TM）i5-4460 CPU@3.20 GHz 3.20 GHz，內(nèi)存8 G的計算機上運行。實驗參數(shù)設(shè)置為：ρ1=0.1，ρ=0.1，α=1，β=2，γ=1=1，θ=1，tmax=100。運行6 次，得出結(jié)果如表3 所示。

表3 多次實驗所得結(jié)果

多次對實例進行求解，第2 次得出的結(jié)果最為優(yōu)化，路程最短，其車輛的路線及各路線里程如表4所示。

表4 車輛路線及里程表

4 結(jié)論

本文首先對VRP 問題的理論進行了研究，引出VRPTW 問題，并且對其進行了數(shù)學模型的建立，然后在基本蟻群算法的基礎(chǔ)上，改進算法使其能更好地對所建模型進行求解，最后根據(jù)實際案例建立模型，運用改進后的算法進行求解，得出本文算法無論是運算結(jié)果還是花費的時間，都體現(xiàn)出了更佳優(yōu)越的性能。