王淑霞，葛金輝，熊 穎

(通化師范學院 計算機科學系，吉林 通化134001)

1 引言

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

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

2 問題描述

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

在整個配送過程中有如下約束條件：

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

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

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

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

3 算法設計

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

struct Roadinfo

{int carnum;//車輛的序號

double arrivetime;//車輛到達的時間

double leavetime;//車輛離開的時間

double early;//提前時間

double late;//遲到時間

double losttime;//浪費的時間};

struct Neigbour

{ char road[N];

char comproad[N];

int car;

double length;

double time;

double value;

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

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

struct Listoftabu

{ char road[N];

struct Listoftabu *next;

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

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

3.2 算法步驟

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

圖1 求解VRP的算法流程圖

4 計算實例與結(jié)果分析

4.1 實例

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

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

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

表1 實例1的已知條件

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

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

從表2可以看出：用禁忌搜索算法對實例1的10次求解中，都得到了質(zhì)量很高的解，其解的平均值為107.36km，平均使用的車輛數(shù)為3.2輛.其中第3次計算得到的解的質(zhì)量最高，其配送總里程為105.8km，對應的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.

通過以上實驗計算，可以總結(jié)出本文構造的車輛路徑問題的禁忌搜索算法的以下特點：(1)算法求得的解的質(zhì)量較高；(2)算法的收斂速度較快，計算效率較高；(3)算法的穩(wě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]楊元峰，崔志明，等.有時間窗約束的多車場車輛路徑問題的改進遺傳算法[J].蘇州大學學報(工科版),2006(4).

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