王淑霞，葛金輝，熊 穎

(通化師范學(xué)院 計(jì)算機(jī)科學(xué)系，吉林 通化134001)

1 引言

車(chē)輛路徑問(wèn)題(Vehicle Routing Problem,VRP)是物流管理研究中的一項(xiàng)重要內(nèi)容.車(chē)輛路徑問(wèn)題是由G.Dantzig[1]于1959年首先提出,它是指對(duì)一系列發(fā)貨點(diǎn)或收貨點(diǎn),組織適當(dāng)?shù)男熊?chē)路線,使車(chē)輛有序地通過(guò)它們,在滿足一定的約束條件下(如貨物需求量、發(fā)送量、交發(fā)貨時(shí)間、車(chē)輛容量限制、行駛里程限制、時(shí)間限制等),達(dá)到一定的目標(biāo)(如路程最短、費(fèi)用最小、時(shí)間盡量少、使用車(chē)輛盡量少等).

對(duì)于有時(shí)間窗車(chē)輛路徑問(wèn)題(VRPTW)，一般采用啟發(fā)式算法求解，Gendreau[2]等人最先將禁忌搜索方法應(yīng)用于VRP.禁忌搜索算法就是一種智能啟發(fā)式算法，首先構(gòu)造一系列的解,然后對(duì)所得解不斷地進(jìn)行改進(jìn).該算法所得到的解不一定是可行解,它們對(duì)可行性的偏離程度是通過(guò)目標(biāo)函數(shù)里的懲罰函數(shù)來(lái)體現(xiàn)的.該算法求解過(guò)程中的鄰域,是通過(guò)GENI過(guò)程得到的.禁忌搜索算法成功地應(yīng)用于許多經(jīng)典的VRP，它的優(yōu)點(diǎn)是運(yùn)用Taboo List這種記憶結(jié)構(gòu)表，來(lái)避免搜索過(guò)程的重復(fù)，跳出局部最優(yōu)解，尋找近似全局最優(yōu)解.

2 問(wèn)題描述

有時(shí)間窗約束的多車(chē)輛路徑問(wèn)題描述為:某一物流中心具有q臺(tái)配送車(chē)為它的客戶服務(wù)，客戶的數(shù)量為N，位置及貨物需求量一定，并且給定特定的時(shí)間窗，配送車(chē)具有最大載重限制，服務(wù)完最后一個(gè)客戶后需要返回物流中心.用戶i的貨物需求為gi(i=1,2,…,N),且必須在時(shí)間窗口要求一個(gè)合適的車(chē)輛調(diào)度方案,使各車(chē)場(chǎng)的車(chē)輛能滿足所有用戶的需求,并使車(chē)輛總的運(yùn)輸成本最低.

在整個(gè)配送過(guò)程中有如下約束條件：

(1)一個(gè)客戶只能被服務(wù)一次而且必須被服務(wù)一次.

(2)每輛配送車(chē)的配送路徑上客戶的貨物重量的總和不能超過(guò)它的最大載重量.

(3)假設(shè)客戶的時(shí)間窗是[ETi,LTi]完成,若車(chē)輛在ETi之前到達(dá)用戶i處,則在此等待;如果車(chē)輛到達(dá)時(shí)間晚于LTi,用戶i的需求將被延遲滿足.

(4)如果配送車(chē)為客戶服務(wù)的時(shí)間不在時(shí)間窗之內(nèi)，可以允許它為該客戶服務(wù)，但是必須施以懲罰權(quán)重，例如當(dāng)車(chē)輛提前到達(dá)時(shí)，車(chē)輛到達(dá)時(shí)刻與時(shí)間窗開(kāi)始時(shí)刻這段等待時(shí)間就算做時(shí)間損耗；車(chē)輛離開(kāi)客戶的時(shí)間如果超過(guò)了時(shí)間窗關(guān)閉時(shí)間也是一種時(shí)間損耗.dij表示從用戶i到用戶j的運(yùn)輸成本,它的含義可以是距離、費(fèi)用、時(shí)間等,si表示車(chē)輛到達(dá)用戶i的時(shí)間,pE表示在ETi之前到達(dá)用戶i等待的單位時(shí)間成本,pL表示在LTi之后到達(dá)用戶i的單位時(shí)間成本.若車(chē)輛在ETi之前到達(dá)用戶i,則增加機(jī)會(huì)成本pE×(si-ETi);若車(chē)輛在ETi之后到達(dá)用戶i,則增加罰金成本pL×(LTi-si)[3].

3 算法設(shè)計(jì)

3.1 數(shù)據(jù)結(jié)構(gòu)

struct Roadinfo

{int carnum;//車(chē)輛的序號(hào)

double arrivetime;//車(chē)輛到達(dá)的時(shí)間

double leavetime;//車(chē)輛離開(kāi)的時(shí)間

double early;//提前時(shí)間

double late;//遲到時(shí)間

double losttime;//浪費(fèi)的時(shí)間};

struct Neigbour

{ char road[N];

char comproad[N];

int car;

double length;

double time;

double value;

Roadinfo rinfo[N];};//定義鄰域的結(jié)構(gòu)信息

Neigbour nei[NEIGBOUR_NUM+1];//定義鄰域數(shù)組

struct Listoftabu

{ char road[N];

struct Listoftabu *next;

};//定義一個(gè)禁忌表的結(jié)構(gòu)

Listoftabu *listhead,*listend;//禁忌表的頭指針和尾指針

3.2 算法步驟

最初的研究文獻(xiàn)中使用的解的表示采用的是有向邊排列的方法，這種方法效率并不高，因此在本算法中采用了優(yōu)化改進(jìn)的直接排列法.客戶直接排列法即對(duì)n個(gè)客戶隨機(jī)產(chǎn)生一個(gè)1～n的不重復(fù)序列來(lái)表示客戶的服務(wù)順序，數(shù)字i(1≤i≤n)表示客戶i.為了將物流中心與客戶更好的連接起來(lái)，先設(shè)定物流中心的節(jié)點(diǎn)號(hào)為0，因此在算法中解的完整表示為由0～n組成的序列，表示配送車(chē)從物流中心出發(fā)然后服務(wù)各個(gè)客戶，按照配送過(guò)程的約束條件依次將客戶劃分到各個(gè)配送路徑，每輛配送車(chē)負(fù)責(zé)一個(gè)配送路徑，因此當(dāng)劃分配送路徑時(shí)路徑個(gè)數(shù)超過(guò)物流中心所有的配送車(chē)數(shù)量時(shí)，該解為不可行解.為了更好的增加算法的性能，本算法采用動(dòng)態(tài)禁忌表長(zhǎng)度，在搜索過(guò)程中根據(jù)情況調(diào)整禁忌表長(zhǎng)度.解的評(píng)價(jià)方法：本文采用行駛距離+時(shí)間損耗的總代價(jià)作為評(píng)價(jià)值，設(shè)路徑總路程為S，總時(shí)間損耗為T(mén)，則解的評(píng)價(jià)為V=S+T.求解VRP流程如圖1所示.

圖1 求解VRP的算法流程圖

4 計(jì)算實(shí)例與結(jié)果分析

4.1 實(shí)例

筆者用C語(yǔ)言程序?qū)崿F(xiàn)了上述車(chē)輛路徑問(wèn)題的禁忌搜索算法，并對(duì)一個(gè)由計(jì)算機(jī)隨機(jī)生成的[初始解]進(jìn)行了實(shí)驗(yàn)計(jì)算.

實(shí)例1：設(shè)在某物流中心有5臺(tái)配送車(chē)輛，車(chē)輛的最大載重量均為8t，車(chē)輛一次配送的最大行駛距離都為50km，需要向20個(gè)客戶送貨.筆者利用計(jì)算機(jī)隨機(jī)產(chǎn)生了物流中心和20個(gè)客戶的位置坐標(biāo)以及各客戶的貨物需求量，其中物流中心的坐標(biāo)為(14.5km，13.0km)，20個(gè)客戶的坐標(biāo)及其貨物需求量見(jiàn)表1.要求合理安排配送車(chē)輛的行車(chē)路線，使配送總里程最短.為簡(jiǎn)便起見(jiàn)，本文設(shè)各客戶相互之間及物流中心與客戶之間的距離均采用直線距離，該距離可根據(jù)客戶和物流中心的坐標(biāo)計(jì)算得到[4].

該實(shí)例包括20個(gè)客戶，客戶的全排列數(shù)多達(dá)2.433×1018個(gè)，受計(jì)算時(shí)間的限制，用窮舉法根本無(wú)法求解.根據(jù)該問(wèn)題的特點(diǎn)，在用禁忌搜索算法對(duì)其求解時(shí)采用了以下參數(shù)：對(duì)不可行路徑的懲罰權(quán)重取500，迭代步數(shù)取400，每次迭代共搜索當(dāng)前解的40個(gè)鄰居，最小禁忌長(zhǎng)度為10，最大禁忌長(zhǎng)度為25.用禁忌搜索算法對(duì)實(shí)例1隨機(jī)求解10次，得到的計(jì)算結(jié)果見(jiàn)表2[4].使用的機(jī)器配置是CPU：Celeron D 2.80GHZ，內(nèi)存：1G，系統(tǒng)：windows xp sp2，編譯環(huán)境：Code::Blocks 8.02.

表1 實(shí)例1的已知條件

4.2 結(jié)果和結(jié)論

表2 實(shí)例1的禁忌搜索算法計(jì)算結(jié)果

從表2可以看出：用禁忌搜索算法對(duì)實(shí)例1的10次求解中，都得到了質(zhì)量很高的解，其解的平均值為107.36km，平均使用的車(chē)輛數(shù)為3.2輛.其中第3次計(jì)算得到的解的質(zhì)量最高，其配送總里程為105.8km，對(duì)應(yīng)的3條配送路徑分別為：路徑1：0-12-8-6-1-20-7-0；路徑2：0-9-18-10-3-16-17-19-0；路徑3：0-11-2-4-5-13-15-14-0.

通過(guò)以上實(shí)驗(yàn)計(jì)算，可以總結(jié)出本文構(gòu)造的車(chē)輛路徑問(wèn)題的禁忌搜索算法的以下特點(diǎn)：(1)算法求得的解的質(zhì)量較高；(2)算法的收斂速度較快，計(jì)算效率較高；(3)算法的穩(wěn)健性較強(qiáng).

參考文獻(xiàn)：

[1]DANTZIG G,RAMSER J.The truck dispatching problem[J].Man2agement Science,1959,(6):80-91.

[2]Gendreau M.laporte G and Potvin J-Y.Metaheuristics for the Capacitated VRP[M].In:P.Toth and D.Vigo(eds).The Vehicle Routing Problem.Philadelphia,PA:SLSM Monographs on Discrete Mathematics and Applications. 2002.129-154.

[3]楊元峰，崔志明，等.有時(shí)間窗約束的多車(chē)場(chǎng)車(chē)輛路徑問(wèn)題的改進(jìn)遺傳算法[J].蘇州大學(xué)學(xué)報(bào)(工科版),2006(4).

[4]張炯，郎茂祥.有時(shí)間窗配送車(chē)輛調(diào)度問(wèn)題的禁忌搜索算法[J].北方交通大學(xué)學(xué)報(bào)，2004(2).