帶軟時(shí)間窗約束的多車場車輛路徑問題及其禁忌搜索算法研究

何小年

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

0 引言

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

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

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

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

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

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

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

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

滿足：

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

2 求解MDVRPSTW問題的禁忌搜索算法

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

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

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

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

禁忌搜索算法優(yōu)化過程中一個(gè)很重要的組成部分就是鄰域結(jié)構(gòu)，其作用就是如何由一個(gè)解來產(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 算法的禁忌對象和禁忌長度

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

2.4 特赦規(guī)則

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

2.5 終止準(zhǔn)則

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

2.6 多車場的處理

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

3 MDVRPSTW案例測試

本算法已經(jīng)在Pentium-Ⅳ2.67 GHZ微機(jī)上使用Delphi語言編程實(shí)現(xiàn)。為了測試算法的計(jì)算效果，本文使用兩個(gè)案例進(jìn)行計(jì)算，兩個(gè)案例客戶點(diǎn)坐標(biāo)與載重量和時(shí)間窗數(shù)據(jù)見表1。兩個(gè)案例數(shù)據(jù)都包含30個(gè)客戶和4個(gè)車場，其中31、32、33、34為車場。假定車輛載重量為450，車速為1個(gè)單位，每一距離單位行駛費(fèi)用為2.5，派車固定費(fèi)用為100，車輛最大行駛距離為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)和各車場數(shù)據(jù)表

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

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

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

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

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

4 結(jié)論

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