何小年

（湖南涉外經(jīng)濟(jì)學(xué)院信息與機(jī)電工程學(xué)院 湖南 長(zhǎng)沙 410205）

0 引言

車(chē)輛路徑優(yōu)化是物流配送中的核心問(wèn)題，對(duì)提高配送活動(dòng)的效率和效益至關(guān)重要。自DANTAIG等[1]于1959年首次提出車(chē)輛路徑問(wèn)題（vehicle routing problem，VRP）以來(lái)，對(duì)該問(wèn)題的研究不僅成果豐碩，而且熱度一直不減，究其原因，一是該問(wèn)題的NP-難性質(zhì)足以吸引科研人員，二是該問(wèn)題及其更復(fù)雜的各類延伸問(wèn)題的廣泛應(yīng)用性。多車(chē)場(chǎng)問(wèn)題即屬于這一類極為復(fù)雜的延伸問(wèn)題。本文研究一種VRP的復(fù)雜的延伸問(wèn)題——帶軟時(shí)間窗約束的多車(chē)場(chǎng)車(chē)輛路徑問(wèn)題（multi-depot VRP with soft time windows, MDVRPSTW）。MDVRPSTW研究的是有多個(gè)車(chē)場(chǎng)可以同時(shí)對(duì)若干個(gè)有一定貨物需求量的客戶進(jìn)行服務(wù)，要求在滿足各客戶貨物需求和時(shí)間約束的前提下，對(duì)各車(chē)場(chǎng)車(chē)輛和行駛路線進(jìn)行適當(dāng)安排，使總配送費(fèi)用最低。我國(guó)城市規(guī)模人口和面積一般都較大，交通擁擠，單車(chē)場(chǎng)很難實(shí)現(xiàn)配送的及時(shí)性并且可能會(huì)導(dǎo)致配送成本增大，多車(chē)場(chǎng)能有效解決此問(wèn)題，現(xiàn)實(shí)中也有許多物流企業(yè)采用多車(chē)場(chǎng)調(diào)度方案。

對(duì)于多車(chē)場(chǎng)車(chē)輛調(diào)度問(wèn)題的求解，從現(xiàn)有研究文獻(xiàn)來(lái)看，有的采用多車(chē)場(chǎng)整體優(yōu)化法還有的采用通用啟發(fā)式算法優(yōu)化算法。整體優(yōu)化法是設(shè)定一個(gè)虛擬車(chē)場(chǎng)，將所有車(chē)場(chǎng)假設(shè)成一個(gè)整體來(lái)求解路徑問(wèn)題，LI等[2]采用整體法法把各個(gè)車(chē)場(chǎng)都考慮進(jìn)來(lái)進(jìn)行整體優(yōu)化，得到最小的費(fèi)用。但這種方法把多個(gè)發(fā)車(chē)點(diǎn)統(tǒng)一到一個(gè)發(fā)車(chē)點(diǎn)，對(duì)于不同發(fā)車(chē)點(diǎn)的車(chē)輛數(shù)限制、發(fā)貨量限制、時(shí)間限制都比較難處理。徐東洋等[3]、胡蓉等[4]、周鮮成等[5]、王新玉等[6]在其著作中采用通用啟發(fā)式優(yōu)化算法的研究重點(diǎn)集中在如何合理地縮小搜索空間和簡(jiǎn)化求解步驟上，本文采用現(xiàn)代啟發(fā)式算法把多車(chē)場(chǎng)車(chē)輛路徑問(wèn)題看作一個(gè)復(fù)雜的組合優(yōu)化問(wèn)題進(jìn)行研究。

1 MDVRPSTW問(wèn)題描述與數(shù)學(xué)模型

MDVRPSTW可以描述為：有M個(gè)車(chē)場(chǎng)（編號(hào)分別為N+1,N+2,...,N+M），每個(gè)車(chē)場(chǎng)擁有容量為Q的車(chē)輛Km臺(tái)（m∈﹛N+1，N+2，…，N+M﹜），負(fù)責(zé)對(duì)N（客戶編號(hào)為1,2...,N）個(gè)客戶配送貨物，假設(shè)客戶點(diǎn)i的貨物需求量為di（i∈﹛1，2，…，N﹜）且di≤Q，每個(gè)客戶由任意一個(gè)車(chē)場(chǎng)的車(chē)輛服務(wù)但只能由一輛車(chē)服務(wù)一次。車(chē)輛早于客戶規(guī)定的時(shí)間窗到達(dá)則在此等待，需要支付一定的等待費(fèi)用，車(chē)輛晚于客戶規(guī)定的時(shí)間窗到達(dá)則需支付一定的懲罰費(fèi)用。完成任務(wù)后，各車(chē)輛直接返回各自原屬車(chē)場(chǎng)。為構(gòu)造數(shù)學(xué)模型，定義變量如下：

根據(jù)各客戶的需求量和車(chē)輛載重量可估計(jì)出所需車(chē)輛數(shù)的下限：

其中，[*]表示向下取整。

符號(hào)說(shuō)明：K—需要的車(chē)輛數(shù)；L—車(chē)輛最大行駛距離；Q—車(chē)輛最大載重量；i,j—待服務(wù)的客戶點(diǎn)和車(chē)場(chǎng)；dij—從客戶點(diǎn)i到客戶點(diǎn)j的直接的距離，距離矩陣視為對(duì)稱，即dij=dji；di—客戶點(diǎn)i的貨物需求量；l—每輛車(chē)每公里的配送費(fèi)用；c—車(chē)輛固定費(fèi)用；ai—客戶點(diǎn)i的最早服務(wù)時(shí)間；bi—客戶點(diǎn)i的最晚服務(wù)時(shí)間；ti—車(chē)輛到達(dá)客戶點(diǎn)i的時(shí)間；tij—從客戶點(diǎn)i到客戶點(diǎn)j所需要的時(shí)間；p1—早于ai到達(dá)客戶點(diǎn)i等待時(shí)每分鐘的損失費(fèi)用；v—平均車(chē)速；p2—晚于bi到達(dá)客戶點(diǎn)i并服務(wù)的延遲懲罰費(fèi)用?？蛻酎c(diǎn)i和客戶點(diǎn)j在同一路線且客戶點(diǎn)j恰好在客戶點(diǎn)i之后服務(wù)，則車(chē)輛到達(dá)客戶點(diǎn)j的時(shí)間為：tj=ti+tij。

因此，MDVRPSTW數(shù)學(xué)模型可以描述為：

滿足：

模型中，式（2）表示第一個(gè)優(yōu)化目標(biāo)，最小化所需車(chē)輛數(shù)；式（3）表示第二個(gè)優(yōu)化目標(biāo)，最小化總的配送費(fèi)用（包括車(chē)輛行駛費(fèi)用，車(chē)輛固定使用費(fèi)用以及時(shí)間窗偏離懲罰費(fèi)用；式（4）表示每條路線的行駛距離限制；式（5）表示車(chē)輛受到載重量的限制；式（6）表示每個(gè)客戶點(diǎn)只能由一輛車(chē)服務(wù)且所有客戶點(diǎn)都要得到服務(wù)；式（7）表示K條路線都從車(chē)場(chǎng)出發(fā)，最后又回到原車(chē)場(chǎng)；式（8）表示不能從車(chē)場(chǎng)到車(chē)場(chǎng)；式（9）表示車(chē)場(chǎng)m的車(chē)輛k是否從客戶點(diǎn)i到客戶點(diǎn)j；式（10）表示客戶點(diǎn)i的貨物運(yùn)輸任務(wù)是否由車(chē)場(chǎng)m的車(chē)輛k來(lái)完成的。

2 求解MDVRPSTW問(wèn)題的禁忌搜索算法

禁忌搜索（tabu search，TS）算法是一種全局性鄰域搜索算法，模擬人類具有記憶功能的逐步尋優(yōu)特征。它通過(guò)局部鄰域搜索機(jī)制和相應(yīng)的禁忌準(zhǔn)則來(lái)避免迂回搜索，并通過(guò)藐視準(zhǔn)則來(lái)赦免一些被禁忌的優(yōu)良狀態(tài)，進(jìn)而保證多樣化的有效搜索，最終實(shí)現(xiàn)全局優(yōu)化。

2.1 禁忌搜索算法初始解的產(chǎn)生

在算法中需要一個(gè)初始解開(kāi)始搜索過(guò)程。本文采用自然數(shù)編碼，以隨機(jī)方式產(chǎn)生初始解序列。

2.2 鄰域結(jié)構(gòu)

禁忌搜索算法優(yōu)化過(guò)程中一個(gè)很重要的組成部分就是鄰域結(jié)構(gòu)，其作用就是如何由一個(gè)解來(lái)產(chǎn)生一個(gè)新的解。本算法使用了四種鄰域結(jié)構(gòu)，即頂點(diǎn)重新指派、頂點(diǎn)交換“尾”交換和頂點(diǎn)2-Opt，以隨機(jī)的方式選擇其中一種領(lǐng)域結(jié)構(gòu)應(yīng)用于當(dāng)前解。

2.3 算法的禁忌對(duì)象和禁忌長(zhǎng)度

禁忌搜索算法的禁忌對(duì)象就是指禁忌表中被禁的那些局部最優(yōu)解。本文將每次迭代得到的最好解，作為禁忌對(duì)象放人禁忌表中。算法的禁忌長(zhǎng)度的長(zhǎng)短決定解的選取，禁忌長(zhǎng)度越短，獲得優(yōu)良解的可能性就相應(yīng)增大，但是同時(shí)增加了迂回搜索，難以探索其他有效的搜索途徑。本文的禁忌長(zhǎng)度是在5到10之間隨機(jī)選取。

2.4 特赦規(guī)則

本文采用基于適配值的藐視準(zhǔn)則，即如果候選集中所有的解都為禁忌解，則解禁候選集中的最好解。

2.5 終止準(zhǔn)則

本文采用事先限定算法的迭代次數(shù)為終止準(zhǔn)則，該準(zhǔn)則是指給定最大的迭代步數(shù)，使總的迭代步數(shù)不超過(guò)這個(gè)數(shù)，事先限定算法的迭代步數(shù)能有效控制算法的運(yùn)行時(shí)間。

2.6 多車(chē)場(chǎng)的處理

本文將多配車(chē)場(chǎng)中心車(chē)輛調(diào)度問(wèn)題看作一個(gè)復(fù)雜的組合優(yōu)化問(wèn)題來(lái)進(jìn)行研究。假定每個(gè)車(chē)場(chǎng)可以派出車(chē)輛數(shù)所限制的前提下，本算法在帶軟時(shí)間窗約束的多車(chē)場(chǎng)車(chē)輛路徑問(wèn)題中多車(chē)場(chǎng)的處理方法是：從車(chē)場(chǎng)集合中隨機(jī)地選取一個(gè)車(chē)場(chǎng)，配送車(chē)從被選中的車(chē)場(chǎng)出發(fā)，到各個(gè)客戶點(diǎn)去完成配送任務(wù)，直到車(chē)輛足夠滿為止，在完成最后一個(gè)客戶點(diǎn)的任務(wù)后，返回原車(chē)場(chǎng)的一條路線。如果所有的客戶點(diǎn)還沒(méi)有服務(wù)完，又從車(chē)場(chǎng)集合中隨機(jī)選取一個(gè)車(chē)場(chǎng)，配送車(chē)從被選中車(chē)場(chǎng)出發(fā)，然后完成剩余的客戶點(diǎn)的配送任務(wù)，直到車(chē)輛足夠滿為止，在完成最后一個(gè)客戶點(diǎn)的任務(wù)后，返回原車(chē)場(chǎng)，一直循環(huán)，直到所有的客戶點(diǎn)的配送任務(wù)都服務(wù)完畢。

3 MDVRPSTW案例測(cè)試

本算法已經(jīng)在Pentium-Ⅳ2.67 GHZ微機(jī)上使用Delphi語(yǔ)言編程實(shí)現(xiàn)。為了測(cè)試算法的計(jì)算效果，本文使用兩個(gè)案例進(jìn)行計(jì)算，兩個(gè)案例客戶點(diǎn)坐標(biāo)與載重量和時(shí)間窗數(shù)據(jù)見(jiàn)表1。兩個(gè)案例數(shù)據(jù)都包含30個(gè)客戶和4個(gè)車(chē)場(chǎng)，其中31、32、33、34為車(chē)場(chǎng)。假定車(chē)輛載重量為450，車(chē)速為1個(gè)單位，每一距離單位行駛費(fèi)用為2.5，派車(chē)固定費(fèi)用為100，車(chē)輛最大行駛距離為240，提前到達(dá)等待費(fèi)用為0.2，延遲到達(dá)懲罰費(fèi)用為2，忽略客戶點(diǎn)的服務(wù)時(shí)間。本文按照兩個(gè)案例數(shù)據(jù)分別進(jìn)行計(jì)算，案例1的具體結(jié)果如表2所示、配送路徑圖如圖1所示；案例2的具體結(jié)果如表3所示、配送路徑圖如圖2所示。

表1 兩個(gè)案例的客戶點(diǎn)和各車(chē)場(chǎng)數(shù)據(jù)表

本文計(jì)算案例1的結(jié)果如表2所示，配送路徑如圖1所示：最優(yōu)路徑總長(zhǎng)度551.1，行駛費(fèi)用為1 377.78，程序運(yùn)行時(shí)間0.05，時(shí)間窗內(nèi)的客戶點(diǎn)數(shù)29，等待與懲罰費(fèi)用66.07，派車(chē)固定費(fèi)用600，總費(fèi)用為2 043.85。計(jì)算案例2的結(jié)果如表3所示，配送路徑如圖2所示：最優(yōu)路徑總長(zhǎng)度628.34，行駛費(fèi)用為1 570.85，程序運(yùn)行時(shí)間0.05，時(shí)間窗內(nèi)的客戶點(diǎn)數(shù)28，等待與懲罰費(fèi)用90.02，派車(chē)固定費(fèi)用600，總費(fèi)用為2 260.87。

表2 本文按照案例1的數(shù)據(jù)測(cè)試的結(jié)果

表3 本文按照案例2的數(shù)據(jù)測(cè)試的結(jié)果

圖1 本文按案例1數(shù)據(jù)測(cè)試結(jié)果的車(chē)輛配送線路圖

圖2 本文按案例2數(shù)據(jù)測(cè)試結(jié)果的車(chē)輛配送線路圖

4 結(jié)論

本文對(duì)帶軟時(shí)間窗約束的多車(chē)場(chǎng)車(chē)輛路徑問(wèn)題進(jìn)行了研究，建立了相應(yīng)的數(shù)學(xué)模型。通過(guò)隨機(jī)選擇車(chē)場(chǎng)，然后從被選中的車(chē)場(chǎng)里隨機(jī)派車(chē)執(zhí)行配送任務(wù)，車(chē)輛執(zhí)行完配送任務(wù)后返回原車(chē)場(chǎng)，一直循環(huán)到所有的客戶點(diǎn)都被服務(wù)完畢，將帶軟時(shí)間窗約束的多車(chē)場(chǎng)車(chē)輛路徑問(wèn)題的求解作為一個(gè)復(fù)雜的組合優(yōu)化問(wèn)題來(lái)研究，拓展了此類問(wèn)題的求解算法。通過(guò)案例測(cè)試，得出了兩個(gè)案例最少的車(chē)輛數(shù)和最優(yōu)的路徑優(yōu)化解，能在較短的時(shí)間內(nèi)得到滿意的結(jié)果，等待與懲罰費(fèi)用也在合理的范圍內(nèi)。這表明用本文設(shè)計(jì)的禁忌搜索算法能得到比較好的計(jì)算結(jié)果，計(jì)算效率也較高。