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

李珍萍， 趙 菲， 劉洪偉

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

?

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

李珍萍， 趙 菲， 劉洪偉

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

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

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

0 引言

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

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

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

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

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

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

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

為了建立模型方便，定義如下符號：

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

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

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

tij：表示車輛從第i個點到第j個點的行駛時間，i,j=0,1,2,…n,n+1；k=1,2,…,m；

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

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

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

qi：表示第i個需求點的需求量，i=1,2,…,n；

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

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

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

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

(1)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2 智能水滴算法

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

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

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

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

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

如某個水滴的完整流動路徑為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。

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

2.2 智能水滴算法的計算步驟

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

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

需求點個數(shù)n;

配送中心及各個需求點之間的距離矩陣D；

車輛的單位行駛成本h;

動用每輛車的固定成本g;

車輛的行駛速度v;

每輛車的最大裝載量Qmax;

車輛在配送中心及各個需求點之間行駛的時間矩陣T；

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

水滴個數(shù)M；

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

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

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

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

任意兩點間的初始泥土量Initsoil;

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

每個水滴的初始速度Initvel。

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

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

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

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

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

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

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

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

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

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

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

(4)計算集合FV中每一個可訪問節(jié)點對應(yīng)的訪問概率。

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

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

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

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

更新水滴的流速：

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

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

Q(j)=Q(i)+qj

計算水滴從節(jié)點i流到節(jié)點j時攜帶泥土的增量

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

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

更新水滴攜帶的泥土量

soilIWD=soilIWD+Δsoil(i,j)

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

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

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

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

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

Itercount=Itercount+1

如果Itercount

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

3 仿真實驗與結(jié)果分析

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

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

表2 各需求點的需求量(單位：噸)，服務(wù)時間(單位：小時)和2個時間窗

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

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

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

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

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

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

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

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

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

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

利用智能水滴算法求解，采用以下運行參數(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；需求點之間邊上的初始泥土量InitSoil=2000；水滴從配送中心出發(fā)的初始速度InitVel=100；最大迭代次數(shù)Itermax=800。

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

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

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

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

4 結(jié)論

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

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

本文僅考慮了具有多個硬時間窗約束的車輛路徑問題，即必須在客戶的某個時間窗內(nèi)為其提供服務(wù)，既不能早到，也不能晚離開。對于具有多個軟時間窗的車輛路徑問題，也可以利用智能水滴算法的原理設(shè)計相應(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é)資助項目(11131009,71540028)；北京市屬高等學(xué)校長城學(xué)者培養(yǎng)計劃項目(CIT&TCD20130327)；北京市科委項目《用于電子商務(wù)物流的搬運機器人與多機器人現(xiàn)場控制系統(tǒng)研制及應(yīng)用驗證》；北京物資學(xué)院重大科研項目《基于可移動貨架的訂單揀選優(yōu)化問題研究》。

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

O226

A

1007-3221(2015)06- 0001-10

10.12005/orms.2015.189