李珍萍， 趙 菲， 劉洪偉

(北京物資學(xué)院 信息學(xué)院， 北京 101149)

?

多時(shí)間窗車輛路徑問題的智能水滴算法

李珍萍， 趙 菲， 劉洪偉

(北京物資學(xué)院 信息學(xué)院， 北京 101149)

研究了多時(shí)間窗車輛路徑問題，考慮了車容量、多個(gè)硬時(shí)間窗限制等約束條件，以動(dòng)用車輛的固定成本和車輛運(yùn)行成本之和最小為目標(biāo)，建立了整數(shù)線性規(guī)劃模型。根據(jù)智能水滴算法的基本原理，設(shè)計(jì)了求解多時(shí)間窗車輛路徑問題的快速算法，利用具體實(shí)例進(jìn)行了模擬計(jì)算，并與遺傳算法的計(jì)算結(jié)果進(jìn)行了對(duì)比分析，結(jié)果顯示，利用智能水滴算法求解多時(shí)間窗車輛路徑問題，能夠以很高的概率得到全局最優(yōu)解，是求解多時(shí)間窗車輛路徑問題的有效算法。

車輛路徑問題；多時(shí)間窗；數(shù)學(xué)模型；智能水滴算法

0 引言

由Dantzig和Ramser于1959年提出的車輛路徑問題(vehicle routing problem，簡稱VRP)[1]是組合優(yōu)化中一類NP難問題。該問題自提出以來，引起了運(yùn)籌學(xué)和管理科學(xué)工作者的廣泛關(guān)注。車輛路徑問題的擴(kuò)展問題也不斷得到廣大學(xué)者的關(guān)注。車輛路徑問題的擴(kuò)展情況有：需求不確定的車輛路徑問題、道路信息不確定的車輛路徑問題。實(shí)際物流配送中的很多問題，如連鎖經(jīng)營超市的商品配送問題、連鎖經(jīng)營餐飲門店的原料配送問題[2]、快遞企業(yè)的快件收取及配送問題等，都可以歸結(jié)為經(jīng)典的車輛路徑問題或車輛路徑問題的擴(kuò)展情況，因此，該問題有著廣泛的應(yīng)用背景。其中，帶時(shí)間窗的車輛路徑問題(VRPTW)是在經(jīng)典車輛路徑問題(VRP)的基礎(chǔ)上加上了時(shí)間窗限制、車容量限制等約束條件，該問題屬于強(qiáng)NP難問題。由于車輛路徑問題是NP難問題，實(shí)際工作中遇到的車輛路徑問題規(guī)模都比較大，因此，尋求解決車輛路徑問題的快速有效算法成了解決實(shí)際問題的關(guān)鍵。近年來，對(duì)帶時(shí)間窗的車輛路徑問題(VRPTW)的研究成果主要集中在尋找?guī)в袉我粫r(shí)間窗問題的快速有效算法方面。

多時(shí)間窗的車輛路徑問題(VRPMTW)指每個(gè)需求點(diǎn)都存在多個(gè)互不相交的時(shí)間窗，配送車輛必須在各個(gè)需求點(diǎn)對(duì)應(yīng)的某一個(gè)時(shí)間窗內(nèi)為其提供服務(wù)(這類時(shí)間窗稱為硬時(shí)間窗，本文僅考慮具有多個(gè)硬時(shí)間窗約束的問題)。這類問題在實(shí)際中有著廣泛的應(yīng)用。這類問題是VRPTW問題的擴(kuò)展情況，文獻(xiàn)[3]中研究了多時(shí)間窗車輛路徑問題，建立了數(shù)學(xué)模型，文獻(xiàn)[4]提出了求解多時(shí)間窗車輛路徑問題的混合蟻群算法，文獻(xiàn)[5]設(shè)計(jì)了求解多時(shí)間窗車輛路徑問題的遺傳算法。

智能水滴算法(Intelligent Water Drops, IWD)是Hamed Shah-Hosseini于2007年首次提出的一種新型群智能算法。該算法通過模擬自然界水系統(tǒng)和其周圍環(huán)境的相互作用而形成河流水道的過程進(jìn)行迭代運(yùn)算，最終獲得優(yōu)化結(jié)果。智能水滴算法最先被用于解決旅行商問題[6]。隨后，Shah-Hosseini又將智能水滴算法用于解決多維背包問題、N皇后和灰度閾值問題等[7～9]。ImanKamkar等人運(yùn)用智能水滴算法求解了一般車輛路徑問題[10]，并將智能水滴算法的運(yùn)行結(jié)果與模擬退火算法[11～13]、拓?fù)渌阉鱗14]、改進(jìn)蟻群算法[15～17]等的運(yùn)行結(jié)果進(jìn)行對(duì)比，發(fā)現(xiàn)用智能水滴算法可以得到更好的解。為了進(jìn)一步提高智能水滴算法的求解效率，部分學(xué)者還針對(duì)具體的實(shí)際問題，提出了改進(jìn)的智能水滴算法[18～23]。

由于帶時(shí)間窗的車輛路徑問題比一般車輛路徑問題考慮的因素更多，問題更復(fù)雜，文獻(xiàn)[10]中提出的求解一般車輛路徑問題的智能水滴算法并不能直接推廣用于解決帶時(shí)間窗的車輛路徑問題。到目前為止，尚沒有文獻(xiàn)研究求解多時(shí)間窗的車輛路徑問題的智能水滴算法。

本文將針對(duì)具有硬時(shí)間窗約束的多時(shí)間窗車輛路徑問題的特點(diǎn)，建立多時(shí)間窗車輛路徑問題的數(shù)學(xué)模型。進(jìn)一步利用智能水滴算法的原理，設(shè)計(jì)求解多時(shí)間窗的車輛路徑問題快速有效算法，以總成本最低為目標(biāo)，尋找車輛的最優(yōu)行駛路徑。

1 多時(shí)間窗車輛路徑問題的數(shù)學(xué)模型

多時(shí)間窗車輛路徑問題VRPMTW可描述為：一個(gè)配送中心擁有若干輛車，為n個(gè)需求點(diǎn)提供配送服務(wù)，已知每個(gè)需求點(diǎn)的需求量、每輛車的最大裝載量及任意兩個(gè)需求點(diǎn)和配送中心之間的距離，每個(gè)需求點(diǎn)均有多個(gè)互不相交的服務(wù)時(shí)間窗。每輛車均從配送中心出發(fā)，為若干個(gè)需求點(diǎn)提供配送服務(wù)，最后再回到配送中心。假設(shè)每個(gè)需求點(diǎn)只能由一輛車提供配送服務(wù)，并且車輛必須在需求點(diǎn)的某一個(gè)給定時(shí)間窗內(nèi)到達(dá)并完成配送服務(wù)；每輛車為每個(gè)需求點(diǎn)提供配送服務(wù)的時(shí)間(裝卸貨時(shí)間)已知；動(dòng)用每輛車的固定成本及每輛車行駛單位距離的成本均已知；每輛車的總行駛距離(時(shí)間)不能超過給定的最長行駛距離(時(shí)間)。問應(yīng)該動(dòng)用幾輛車以及如何安排每輛車的配送路徑才能使總配送成本最低？

為了建立模型方便，定義如下符號(hào)：

K={1,2,…,m}：表示可使用的車輛集合；

D={0,1,2,…,n,n+1}：表示配送中心及客戶集，其中1,2,…,n表示需求點(diǎn)，0和n+1表示配送中心(為了建立模型方便，本文把配送中心表示成兩個(gè)點(diǎn)，0點(diǎn)表示配送車輛的出發(fā)點(diǎn)，n+1點(diǎn)表示配送車輛完成配送任務(wù)后的返回點(diǎn))；為了方便，本文把D中的每個(gè)元素(配送中心或需求點(diǎn))簡稱為一個(gè)點(diǎn)，即第0個(gè)點(diǎn)和第n+1個(gè)點(diǎn)表示配送中心，第1,2,…,n個(gè)點(diǎn)表示需求點(diǎn)。

dij：表示從第i個(gè)點(diǎn)到第j個(gè)點(diǎn)的距離，i,j=0,1,2,…,n,n+1；k=1,2,…,m；

tij：表示車輛從第i個(gè)點(diǎn)到第j個(gè)點(diǎn)的行駛時(shí)間，i,j=0,1,2,…n,n+1；k=1,2,…,m；

sik：表示車輛k為第i個(gè)需求點(diǎn)提供服務(wù)(裝卸貨物)所需要的時(shí)間，k=1,2…,m;i=1,2,…,n；

Qk：表示車輛k的最大裝載量，k=1,2,…,m；

Dk：表示車輛k的最長總行駛距離(時(shí)間)，k=1,2,…,m；

qi：表示第i個(gè)需求點(diǎn)的需求量，i=1,2,…,n；

gk：表示動(dòng)用車輛k的固定成本，k=1,2,…,m；

ck：表示車輛k行駛單位距離(時(shí)間)的成本，k=1,2,…m；

定義模型的決策變量如下：

多時(shí)間窗車輛路徑問題可以表示成如下整數(shù)線性規(guī)劃模型

(1)

上述整數(shù)線性規(guī)劃模型的含義如下：

目標(biāo)函數(shù)(1)表示最小化總成本；

約束條件(2)表示每一輛車都必須從配送中心出發(fā)；

約束條件(3)表示每一輛車完成配送任務(wù)后都必須返回配送中心；

約束條件(4)表示點(diǎn)0為車輛的出發(fā)點(diǎn)，而不是車輛返回點(diǎn)；

約束條件(5)表示n+1點(diǎn)為車輛最終返回點(diǎn)，而不是車輛的出發(fā)點(diǎn)；

約束條件(6)表示恰好有一輛車為每個(gè)需求點(diǎn)提供服務(wù)；

約束條件(7)表示如果第k輛車到達(dá)第j個(gè)點(diǎn)，則必為第j個(gè)需求點(diǎn)提供服務(wù)；

約束條件(8)表示如果第k輛車為第i個(gè)點(diǎn)提供服務(wù)，則服務(wù)完必須從第i個(gè)點(diǎn)離開；

約束條件(9)表示任何一輛車所服務(wù)的需求點(diǎn)的總需求量不超過其最大裝載量；

約束條件(10)表示任何一輛車的總行駛距離(時(shí)間)不超過其最大行駛距離(時(shí)間)；

約束條件(11)表示每一輛車從配送中心0出發(fā)的時(shí)刻均為0；

約束條件(12)表示任何一輛車在其配送路徑上相繼到達(dá)兩個(gè)需求點(diǎn)的時(shí)刻之間的關(guān)系；

約束條件(13)(14)表示如果第k輛車在第i個(gè)需求點(diǎn)的第a個(gè)時(shí)間窗內(nèi)為其提供服務(wù)，則其到達(dá)第i個(gè)需求點(diǎn)的時(shí)刻必須滿足第i個(gè)需求點(diǎn)的第a個(gè)時(shí)間窗約束；

約束條件(15)表示如果第k輛車為第i個(gè)需求點(diǎn)提供服務(wù)，則必須在第i個(gè)需求點(diǎn)的某一個(gè)時(shí)間窗內(nèi)完成服務(wù)；

約束條件(16)表示如果第k輛車沒有為第i個(gè)需求點(diǎn)提供服務(wù)，則其不會(huì)到達(dá)第i個(gè)需求點(diǎn)處；

約束條件(17)(18)(19)(20)表示變量取值限制。

2 智能水滴算法

2.1 智能水滴算法的基本原理

智能水滴算法是一種群智能算法，它通過模擬自然界水系統(tǒng)和其周圍環(huán)境的相互作用而形成河道的過程進(jìn)行迭代運(yùn)算，最終獲得優(yōu)化結(jié)果。在自然界的河道中有無數(shù)流動(dòng)著的水滴，這些流動(dòng)的水滴與河道具有作用與反作用的關(guān)系。一方面，無數(shù)流動(dòng)的水滴形成巨大的移動(dòng)群體，這個(gè)巨大的水滴群體創(chuàng)造了河流流經(jīng)的河道；另一方面河道本身也在影響著水滴的流向。如果河道中沒有障礙物，那么水滴會(huì)以直線路徑到達(dá)目的地，形成水滴流動(dòng)的最短路徑。如果有障礙物存在，水滴就會(huì)改變流動(dòng)路徑，形成彎曲的河道。經(jīng)過科學(xué)家的研究發(fā)現(xiàn)，在考慮河流從源點(diǎn)到目的地的距離和中間障礙物存在的情況下，水滴建立起來的河道往往是最優(yōu)的。

流動(dòng)中水滴具有一定的速度和攜帶一定量的泥土，水滴能夠?qū)⒛嗤翉囊粋€(gè)地方搬運(yùn)到另一個(gè)地方。由于水滴速度越快其動(dòng)能越大，因此泥土?xí)牧魉佥^高的地方被搬運(yùn)到流速較低的地方；當(dāng)流速減緩時(shí)，泥土在地球重力作用下會(huì)沉積下來。水滴流速快的地方隨著時(shí)間推移會(huì)變得越來越深，同時(shí)越來越深的河道又會(huì)吸引后續(xù)更多的水滴。因此，自然界中水滴與泥土的關(guān)系滿足三個(gè)規(guī)則：(1)流速快的水滴比流速慢的水滴攜帶更多的泥土；(2)水滴在泥土較少的路徑比泥土較多的路徑獲得更多的速度增量；(3)水滴會(huì)以更大的概率選擇泥土較少的路徑前進(jìn)。

在智能水滴算法中，水滴具有兩個(gè)屬性：水滴前進(jìn)的速度和水滴攜帶的泥土量。這兩個(gè)屬性在水滴的流動(dòng)過程中不斷變化，目的是尋找一條最優(yōu)路徑。由于智能水滴有有效匯聚的能力，所以，隨著迭代次數(shù)的增大，該算法找到最優(yōu)解的概率也隨之增大。為了簡化問題，在智能水滴算法迭代過程中，假設(shè)水滴是按照離散步驟運(yùn)動(dòng)的。

多時(shí)間窗車輛路徑問題可以用圖G=(V，E)表示其中，V={0,1,2,…,n}表示節(jié)點(diǎn)集合(包括配送中心0和需求點(diǎn)1,2,…,n)，E表示節(jié)點(diǎn)之間的邊集合。一個(gè)水滴從配送中心0出發(fā)，沿著不同的路徑，遍歷各個(gè)需求點(diǎn)，最后回到配送中心，形成水滴的完整流動(dòng)路徑(路徑中水滴可以多次經(jīng)過配送中心0，但每個(gè)需求點(diǎn)只能經(jīng)過一次)，每一個(gè)水滴的完整流動(dòng)路徑恰好對(duì)應(yīng)了VRPMTW的一個(gè)解。

如某個(gè)水滴的完整流動(dòng)路徑為0→4→2→0→3→6→7→0→8→5→1→0，則表示需要用3輛車完成配送任務(wù)，3輛車的配送路徑分別為：0→4→2→0，0→3→6→7→0，0→8→5→1→0。

如果所有的水滴都形成了各自的完整流動(dòng)路徑，則一次迭代結(jié)束。每次迭代結(jié)束后，在各個(gè)水滴的完整流動(dòng)路徑中找出最優(yōu)的路徑TIB，利用這條最優(yōu)路徑更新各個(gè)節(jié)點(diǎn)之間的泥土量及全局最優(yōu)路徑TTB；然后進(jìn)入下一次迭代。不斷重復(fù)這種迭代過程，直到達(dá)到最大迭代次數(shù)Itermax或者得到期望的最優(yōu)路徑TTB。

2.2 智能水滴算法的計(jì)算步驟

第1步 輸入初始靜態(tài)變量：

配送中心及需求點(diǎn)集合，0表示配送中心，1,2, 3,…,n表示需求點(diǎn)；

需求點(diǎn)個(gè)數(shù)n;

配送中心及各個(gè)需求點(diǎn)之間的距離矩陣D；

車輛的單位行駛成本h;

動(dòng)用每輛車的固定成本g;

車輛的行駛速度v;

每輛車的最大裝載量Qmax;

車輛在配送中心及各個(gè)需求點(diǎn)之間行駛的時(shí)間矩陣T；

最大迭代次數(shù)Iter;

水滴個(gè)數(shù)M；

速度更新參數(shù)：av,bv,cv;

泥土量更新參數(shù)：as,bs,cs;

局部泥土更新權(quán)系數(shù)α；

全局泥土更新權(quán)系數(shù)β;

任意兩點(diǎn)間的初始泥土量Initsoil;

初始泥土量矩陣W=(wij)(n+1)×(n+1)，其中w(i,j)=Initsoil;

每個(gè)水滴的初始速度Initvel。

第2步 輸入初始動(dòng)態(tài)變量

每個(gè)水滴已訪問過的節(jié)點(diǎn)集合Visitnode，初始狀態(tài)為空集；

每個(gè)水滴未訪問過的節(jié)點(diǎn)集合Novisitnode，初始狀態(tài)為Novisitnode= {0,1,2,…,n}；

每個(gè)水滴從配送中心出發(fā)時(shí)攜帶的初始泥土量Soil=0；

每個(gè)水滴從配送中心出發(fā)時(shí)的初始速度Vel=InitVel;

每個(gè)水滴從配送中心出發(fā)時(shí)的初始裝載量Q(0)=0；

每個(gè)水滴從配送中心出發(fā)的時(shí)刻r(0)=0。

第3步 按照下列步驟(1)--(6)求出每個(gè)水滴對(duì)應(yīng)的訪問路徑(每個(gè)水滴的訪問路徑對(duì)應(yīng)VRPMTW的一個(gè)可行解)

(1) 根據(jù)時(shí)間窗限制，從符合約束條件的需求點(diǎn)中隨機(jī)選擇一個(gè)需求點(diǎn)作為水滴訪問的第一個(gè)節(jié)點(diǎn)，記錄水滴到達(dá)該節(jié)點(diǎn)的時(shí)刻。

(2)更新水滴已經(jīng)訪問過的節(jié)點(diǎn)集合Visitnode及未訪問節(jié)點(diǎn)集合Novisitnode，并記錄水滴已訪問節(jié)點(diǎn)的訪問順序。

(3) 根據(jù)每個(gè)水滴的未訪問節(jié)點(diǎn)對(duì)應(yīng)的時(shí)間窗及未訪問節(jié)點(diǎn)的需求量，確定水滴從當(dāng)前節(jié)點(diǎn)出發(fā)下一個(gè)可訪問的節(jié)點(diǎn)集合FV(如果水滴從當(dāng)前節(jié)點(diǎn)去某一個(gè)未訪問節(jié)點(diǎn)，到達(dá)未訪問節(jié)點(diǎn)時(shí)的容量約束和時(shí)間窗限制均滿足，則將該未訪問節(jié)點(diǎn)加入下一個(gè)可訪問節(jié)點(diǎn)集合FV)；如果所有的未訪問節(jié)點(diǎn)都不滿足容量約束和時(shí)間窗限制，則水滴返回配送中心，將該水滴對(duì)應(yīng)的動(dòng)態(tài)變量恢復(fù)初始值(表示一輛車的配送路徑已經(jīng)形成)；如果未訪問節(jié)點(diǎn)集合為空集，則水滴返回配送中心，該水滴的完整訪問路徑已經(jīng)形成，水滴的完整訪問路徑對(duì)應(yīng)VRPMTW問題的一個(gè)可行解TIWD。

(4)計(jì)算集合FV中每一個(gè)可訪問節(jié)點(diǎn)對(duì)應(yīng)的訪問概率。

水滴從當(dāng)前節(jié)點(diǎn)i出發(fā)，到FV中每一個(gè)可訪問節(jié)點(diǎn)j的概率可以按照以下的公式計(jì)算：

此處，當(dāng)j=0時(shí)的計(jì)算公式與其它情況下不同，主要目的是盡可能減少不滿載車輛直接返回配送中心的概率。

(5)根據(jù)集合FV中每個(gè)節(jié)點(diǎn)對(duì)應(yīng)的概率，用賭輪法選擇下一個(gè)訪問點(diǎn)。如果水滴選擇的下一個(gè)訪問節(jié)點(diǎn)為j，則將節(jié)點(diǎn)j加入到已訪問節(jié)點(diǎn)集合中，并修改當(dāng)前水滴對(duì)應(yīng)的已訪問節(jié)點(diǎn)集合、訪問順序和未訪問節(jié)點(diǎn)集合。

(6)更新水滴對(duì)應(yīng)的動(dòng)態(tài)變量

更新水滴的流速：

計(jì)算水滴到達(dá)節(jié)點(diǎn)j的時(shí)間r(j)及裝載量Q(j)：

r(j)=r(i)+s(i)+tij

Q(j)=Q(i)+qj

計(jì)算水滴從節(jié)點(diǎn)i流到節(jié)點(diǎn)j時(shí)攜帶泥土的增量

更新水滴流過的路徑(i,j)上的泥土量w(i,j)：

w(i,j)=w(i,j)-α·Δsoil(i,j)

更新水滴攜帶的泥土量

soilIWD=soilIWD+Δsoil(i,j)

水滴攜帶的泥土增量取決于水滴流動(dòng)的速度，在VRPMTW中，水滴攜帶的泥土增量與水滴流過該段路徑所用的時(shí)間有關(guān)。流速較快的水滴會(huì)比流速較慢的水滴攜帶更多的泥土量。

第4步 在第三步求出的所有水滴的完整訪問路徑TIWD中，尋找最優(yōu)解TIB

每個(gè)水滴的完整訪問路徑對(duì)應(yīng)VRPMTW問題的一個(gè)可行解，計(jì)算其目標(biāo)函數(shù)值(總配送成本)，通過比較確定出目標(biāo)函數(shù)值最小的一個(gè)可行解TIWD，作為本次迭代的最優(yōu)解TIB。

第5步 利用本次迭代得到的最優(yōu)解TIB，更新其對(duì)應(yīng)的最優(yōu)路徑上的泥土量，并把更新以后的泥土量矩陣作為下一次迭代的初始泥土量矩陣。

第7步 更新迭代計(jì)數(shù)

Itercount=Itercount+1

如果Itercount

如果Itercount=Itermax，則將最后得到的解TTB作為VRPMTW問題的最優(yōu)解輸出，計(jì)算結(jié)束。

3 仿真實(shí)驗(yàn)與結(jié)果分析

首先我們選取文獻(xiàn)[5]中的實(shí)例，利用智能水滴算法進(jìn)行計(jì)算，并與文獻(xiàn)[5]中的計(jì)算結(jié)果進(jìn)行對(duì)比。

表1 配送中心與各需求點(diǎn)之間的距離(單位：公里)

表2 各需求點(diǎn)的需求量(單位：噸)，服務(wù)時(shí)間(單位：小時(shí))和2個(gè)時(shí)間窗

圖1 智能水滴算法的收斂過程，橫坐標(biāo)表示迭代次數(shù)，縱坐標(biāo)表示目標(biāo)函數(shù)最優(yōu)值

利用Lingo軟件編寫程序，直接求解整數(shù)規(guī)劃模型，可以得到本例的精確最優(yōu)解，共需要?jiǎng)佑?輛配送車，配送路徑分別為：0→2→9→7→8→4→0，0→1→6→10→5→0，0→3→0?？偱渌途嚯x為328公里，總配送成本為6710元。

由于直接求解整數(shù)規(guī)劃模型時(shí)間太長，本文同時(shí)利用智能水滴算法求解，采用以下運(yùn)行參數(shù)：水滴數(shù)NIWD=100；水滴流速更新參數(shù)av=1，bv=0.1，cv=1；水滴攜帶泥土量更新參數(shù)as=1，bs=0.1，cs=1；局部泥土量更新參數(shù)α=1；全局泥土量更新參數(shù)β=1；需求點(diǎn)之間邊上的初始泥土量InitSoil=2000；水滴從配送中心出發(fā)的初始速度InitVel=100；最大迭代次數(shù)Itermax=100。利用這組參數(shù)一共進(jìn)行了100次運(yùn)算，其中96次得到了問題的精確最優(yōu)解。最快的一次僅迭代3次就得到了全局最優(yōu)解，最慢的一次迭代了35次得到全局最優(yōu)解，平均迭代次數(shù)為14次。圖1描述了其中一次運(yùn)算的收斂過程。

利用文獻(xiàn)[5]中遺傳算法求解本例， 選取種群規(guī)模為100，最大迭代次數(shù)為100，利用這組參數(shù)運(yùn)行算法100次，僅有30次得到問題精確最優(yōu)解，在得到精確最優(yōu)解的運(yùn)算中，最快的一次迭代次數(shù)為16次，最慢的一次迭代次數(shù)為86次，平均迭代次數(shù)為54次。

針對(duì)例1，分別利用遺傳算法(GA)和智能水滴算法(IDW)計(jì)算100次，統(tǒng)計(jì)100次計(jì)算中找到最優(yōu)解的次數(shù)，得到的目標(biāo)函數(shù)平均值，得到的最差解的目標(biāo)函數(shù)值，收斂到最優(yōu)解需要的最少迭代次數(shù)和最多迭代次數(shù)，以及平均迭代次數(shù)等，得到的統(tǒng)計(jì)結(jié)果見表3。

表3 分別利用遺傳算法和智能水滴算法運(yùn)行100次的結(jié)果統(tǒng)計(jì)表

通過以上分析及表3中統(tǒng)計(jì)結(jié)果的比較可以看出，智能水滴算法無論在得到最優(yōu)解的概率還是收斂到最優(yōu)解的迭代次數(shù)方面都明顯優(yōu)于遺傳算法。

文獻(xiàn)[4]中對(duì)于同樣規(guī)模的問題，利用元胞蟻群算法計(jì)算，100次運(yùn)算中平均僅有15次能得到最優(yōu)解?？梢娫伻核惴ㄔ谡业阶顑?yōu)解的概率方面更是遠(yuǎn)遠(yuǎn)不如智能水滴算法。

例2 某配送中心擁有若干輛型號(hào)相同配送車輛，每天為配送范圍內(nèi)的20個(gè)需求點(diǎn)提供配送服務(wù)。用序號(hào)0表示配送中心，序號(hào)1到20表示需求點(diǎn)，假設(shè)配送中心的位置坐標(biāo)為(0,0), 各個(gè)需求點(diǎn)的位置坐標(biāo)、需求量qj、配送車輛為各個(gè)需求點(diǎn)提供服務(wù)的時(shí)間ssj，各個(gè)需求點(diǎn)要求服務(wù)的2個(gè)時(shí)間窗等如表4所示。已知每輛配送車輛的最大裝載量為Q=40噸， 所有的配送車輛0時(shí)刻從配送中心出發(fā)，完成配送任務(wù)后必須在8小時(shí)之內(nèi)返回配送中心。假設(shè)配送車輛的行駛時(shí)間和距離成正比，平均行駛速度為30千米/小時(shí)，需求點(diǎn)i到需求點(diǎn)j的距離等于兩點(diǎn)間的直線距離，動(dòng)用一輛配送車輛的固定成本為100元，配送車輛行駛每公里的成本為5元。求使總成本最低的配送路徑。

表4 各需求點(diǎn)的位置坐標(biāo)(公里)、需求量(噸)、服務(wù)時(shí)間(小時(shí))、時(shí)間窗(小時(shí))

利用智能水滴算法求解，采用以下運(yùn)行參數(shù)：水滴數(shù)N=200；水滴流速更新參數(shù)av=1000，bv=0.1，cv=1；水滴攜帶泥土量更新參數(shù)as=1000，bs=0.1，cs=1；局部泥土量更新參數(shù)α=0.9；全局泥土量更新參數(shù)β=0.9；需求點(diǎn)之間邊上的初始泥土量InitSoil=2000；水滴從配送中心出發(fā)的初始速度InitVel=100；最大迭代次數(shù)Itermax=800。

經(jīng)過計(jì)算，得到VRPMTW問題的最優(yōu)解，如圖2所示。共需動(dòng)用4輛車完成配送任務(wù)，最小總費(fèi)用為2168.9元，其中第一輛車的配送路徑為0→5→2→3→6→4→1→0，實(shí)際最大裝載量為24噸，配送路徑長度為86.966公里；第二輛車的配送路徑為0→7→9→10→8→11→0，實(shí)際最大裝載量為29噸，配送路徑長度為86.073公里；第三輛車的配送路徑為0→17→16→13→14→12→0，實(shí)際最大裝載量為38噸，配送路徑長度為77.325公里；第四輛車的配送路徑為0→20→19→15→18→0，實(shí)際最大裝載量為38噸，配送路徑長度為103.44公里。

圖2 最優(yōu)配送路徑示意圖

從圖2中可以看出，為了滿足各個(gè)需求點(diǎn)的時(shí)間窗限制，有些配送車輛的配送路徑未必是最短的。如第一輛配送車輛的配送路徑為：0→5→2→3→6→4→1→0，實(shí)際上，如果第一輛車按照0→5→2→6→3→4→1→0或者0→5→2→3→4→6→1→0的順序配送，則總行駛距離均有所減少，但按照這兩種配送順序到達(dá)需求點(diǎn)4的時(shí)刻均不在需求點(diǎn)4的兩個(gè)時(shí)間窗內(nèi)，因此，這些行程較短的配送路徑并不可行。另外，在第四輛車的配送路徑0→20→19→15→18→0中，如果把需求點(diǎn)15和需求點(diǎn)18的順序交換，則路徑的長度將減少，但交換順序后的路徑無法滿足需求點(diǎn)15的時(shí)間窗限制。通過對(duì)其他例子的計(jì)算結(jié)果分析也可以發(fā)現(xiàn)類似的情況，這說明，智能水滴算法在求解的過程中已經(jīng)綜合考慮了各種約束條件，得到的解在實(shí)際中具有很好的可操作性。

本文還采用不同的參數(shù)進(jìn)行了模擬計(jì)算，從大量的計(jì)算結(jié)果中可以發(fā)現(xiàn)，智能水滴算法能夠有效跳出局部最優(yōu)解，快速地找到問題的近似最優(yōu)解，而且有較高的概率得到全局最優(yōu)解。如果增加水滴個(gè)數(shù)或迭代次數(shù)，可以提高找到全局最優(yōu)解的概率。

4 結(jié)論

多時(shí)間窗車輛路徑(VRPMTW)問題在實(shí)際中有著非常廣泛的應(yīng)用，由于該問題是典型的NP難題，精確求解非常困難，因此設(shè)計(jì)求解多時(shí)間窗車輛路徑問題的快速有效算法是解決實(shí)際物流配送問題的關(guān)鍵。智能水滴算法是一種新型的群體智能算法，本文利用智能水滴算法基本原理設(shè)計(jì)了求解多時(shí)間窗車輛路徑問題的快速有效算法，通過仿真實(shí)驗(yàn)證明了智能水滴算法的良好效果，智能水滴算法能夠以較大概率找到全局最優(yōu)解，是求解多時(shí)間窗的車輛路徑問題的一個(gè)很好的方法。

由于智能水滴算法能夠有效地跳出局部最優(yōu)解，在解決諸多組合優(yōu)化問題中均顯示了良好的效果，因此還可以利用智能水滴算法的基本原理設(shè)計(jì)求解其它組合優(yōu)化問題的快速有效算法。

本文僅考慮了具有多個(gè)硬時(shí)間窗約束的車輛路徑問題，即必須在客戶的某個(gè)時(shí)間窗內(nèi)為其提供服務(wù)，既不能早到，也不能晚離開。對(duì)于具有多個(gè)軟時(shí)間窗的車輛路徑問題，也可以利用智能水滴算法的原理設(shè)計(jì)相應(yīng)的快速求解算法。

[1] Dantzig G, Ramser J. The truck dispatching problem[J]. Management Science, 1959, 10 (6): 80-91.

[2] Shi Z, Fu Z. Research on two-phase chain store distribution vehicle routing problem with soft time windows[J]. Application Research of Computers, 2012, 29 (9): 94-99.

[3] Ma H, Zuo C, Yand S. Modeling and solving for vehicle routing problem with multiple time windows[J]. Journal of System Engineering, 2009,24, (05): 607- 613.

[4] Peng B, Zhou Y. Hybrid ant colony algorithm for vehicle routing problem with multiple time windows[J]. Computer Engineering and Applications, 2010, 46 (31): 28-31.

[5] Huang Q, Li Z. Mathematical model and algorithm for vehicle routing problem with multiple time windows[J]. Logistics Technology, 2012, 31(7): 194-196.

[6] Hamed Shah-Hosseini. (2007). Problem Solving by Intelligent Water Drops[A]. Proceedings of the IEEE Congress on Evolutionary Computation, Singapore, 2007. 3226-3231.

[7] Hamed Shah-Hosseini. The intelligent water drops algorithm: a nature-inspired swarm-based optimization algorithm[J]. Bio-Inspired Computation, 2009, Vol. 1, Nos. 1/2. 71-79.

[8] Hamed Shah-Hosseini. Optimization with the nature-inspired intelligent water drops[A]. In W. P. Dos Santos(Eds), Evolutionary computation, Austria: I-Tech, Vienna, 2009. 297-320.

[9] Hamed Shah-Hosseini. Intelligent water drops algorithm for automatic multilevel thresholding of gray-level images using a modified Otsu’s criterion[J]. International Journal of Modeling, Identification and Control(IJMIC), 2012, 15(4): 241-249.

[10] Kamkar, Akbarzaden, Yaghoobi. Intelligent water drops a new optimization algorithm for solving the Vehicle Routing Problem[A]. IEEE International Conference on Systems Man and Cybernetics, 2010. 4142- 4146

[11] Tavakkoli-Moghaddam R, Safaei N, Ghlipour Y. A hybrid simulated annealing for capacitated vehicle routing problems with the independent route length[J]. Applied Mathematics and Computation, 2006, 176: 445- 454

[12] Prins C. A simple and effective evolutionary algorithm for the vehicle routing problem[J]. Computers & Operations Research, 2004, 31: 1985-2002.

[13] Geonwook Jeon, Herman R. Leep, Jae Young Shim. A vehicle routing problem solved by a hybrid genentic algorithm[J]. Journal of Computers and Industrial Engineering, 2007, 53(4): 680- 692.

[14] Renaud J, Laporte G, Boctor F F. A tabu search heuristic for the multi-depot vehicle routing problem[J]. Computers & Operations Research, 1996, 23 (3): 229-235.

[15] Doerner K F, Hartl R F, Kiechle G, Lucka M, Reimann M. Parallel ant systems for the capacitated vehicle routing problem[A]. Evolutionary Computation in Combinatorial Optimization: 4th European Conference, EvoCOP 2004, LNCS 3004, 72- 83.

[16] Reimann M, Stummer M, Doemer K. (2002).A savings based ant system for the vehicle routing problem. Langdon,W.B. et al.(Eds), GECCO 2002: Proceedings of the Genetic and Evolutionary Computation Conference, Morgan Kaufmann, San Francisco.

[17] Peng W, Tong R F, Tang M, Dong J X. (2005). Ant colony search algorithms for optimal packing problem. ICNC 2005, LNCS 3611, 1229-1238.

[18] Msallam M M, Hamdan M. Improved intelligent water drops algorithm using adaptive schema[J]. Bio-Inspired Computation, 2011, 3(2): 103-111.

[19] Hamed Shah-Hosseini. (2012). An approach to continuous optimization by the intelligent water drops algorithm. The 4th International Conference of Cognitive Science, 224-229.

[20] Niu S H, Ong S K, Nee A Y C. An improved intelligent water drops algorithm for achieving optimal job-shop scheduling solutions[J]. International Journal of Production Research, 2012, 50: 15, 4192- 4205

[21] Hamed Shah-Hosseini. Intelligent water drops algorithm: a new optimization method for solving the multiple knapsack problem[J]. International Journal of Intelligent Computing and Cybernetics, 2008, 1(2): 193-212.

[22] Duan H, Liu S, Lei X. (2008). Air robot path planning based on intelligent water drops optimization. IEEE International Joint Conference on Neural Networks(IJCNN2008), 1(8): 1397-1401.

[23] Duan H, Liu S, Wu J. Novel intelligent water drops optimization approach to single UCAV smooth path planning[J]. Aerospace Science and Technology, 2009, 13: 442- 449.

Intelligent Water Drops Algorithm for Vehicle Routing Problem with Multiple Time Windows

LI Zhen-ping, ZHAO Fei, LIU Hong-wei

(SchoolofInformation,BeijingWuziUniversity,Beijing101149,China)

The vehicle routing problem with multiple time windows is investigated in this paper. The constraints of vehicle’s capacity and the multiple hard time windows are considered. An integer linear programming model of VRPMTW is proposed, and the objective function is to minimize the total costs including the fixed costs of vehicles and the transportation costs of vehicles. Based on the principles of the intelligent water drops, an Intelligent Water Drops(IDW)algorithm for solving the VRPMTW is designed. We further do simulation on an example, and compare the results obtained by IDW algorithm and GA(genetic algorithm)algorithm. The results show that we can find the global optimal solution of VRPMTW with higher probability using Intelligent Water Drops algorithm than Genetic Algorithm. IDW algorithm is an efficient algorithm for solving VRPMTW. Key words:vehicle routing problem; multiple time windows; mathematical model; intelligent water drops algorithm

2014- 05-10

國家自然科學(xué)資助項(xiàng)目(11131009,71540028)；北京市屬高等學(xué)校長城學(xué)者培養(yǎng)計(jì)劃項(xiàng)目(CIT&TCD20130327)；北京市科委項(xiàng)目《用于電子商務(wù)物流的搬運(yùn)機(jī)器人與多機(jī)器人現(xiàn)場控制系統(tǒng)研制及應(yīng)用驗(yàn)證》；北京物資學(xué)院重大科研項(xiàng)目《基于可移動(dòng)貨架的訂單揀選優(yōu)化問題研究》。

李珍萍(1966-)，女，博士，教授，研究方向：智能算法，復(fù)雜網(wǎng)絡(luò)；趙菲(1991-)，女，碩士研究生，研究方向：物流工程；劉洪偉(1977-)，男，博士，講師，研究方向：最優(yōu)化理論。

O226

A

1007-3221(2015)06- 0001-10

10.12005/orms.2015.189