裝卸混合的軟時間窗VRP問題混合算法研究

張 亮，杜培俊，何兆芳（中國十七冶集團(tuán)有限公司，安徽 馬鞍山 243000）

0 引 言

配送一直是物流企業(yè)頭疼的問題。物流企業(yè)往往在配送過程中造成很大的浪費(fèi)。配送前的合理規(guī)劃，尤其是配送前車輛路線合理規(guī)劃，可以在一定程度上降低配送成本，減少配送過程中不必要的浪費(fèi)。

對于車輛路線規(guī)劃問題，最初歸結(jié)為一般VRP問題，對此類問題的一般表述為：單一配送中心有一系列客戶點(diǎn)，需要合理安排車隊(duì)，使車隊(duì)有序地通過他們，在滿足一定的約束條件（如貨物需求量、發(fā)送量、交貨時間、車輛容量限制、行使里程限制）下，達(dá)到一定的目標(biāo)（如路程最短、費(fèi)用最少、時間盡量少、使用車輛數(shù)盡量少等），并返回車輛停放場地。文獻(xiàn)[1-5]分別從構(gòu)建模型和使用算法改進(jìn)方面解決此類問題，通過改進(jìn)模型和算法的改進(jìn)，將原先得出的結(jié)果加以優(yōu)化。

當(dāng)約束條件中增入時間約束之后，原本的VRP問題轉(zhuǎn)變成為VRPTW問題。此類問題分為兩類：軟時間窗VRP問題和硬時間窗VRP問題。硬時間窗VRP問題要求車輛必須在客戶要求的時間窗內(nèi)將貨物到達(dá)，否則拒收。此問題對時間的要求很高；而軟時間窗VRP問題則可以允許車輛在客戶允許的容忍范圍內(nèi)將貨物到達(dá)，客戶并不會拒收，但是車輛會接到客戶要求的懲罰。此問題對時間的要求并沒有很高。

不難發(fā)現(xiàn)，現(xiàn)實(shí)中應(yīng)用多半是軟時間窗VRP問題，相關(guān)研究的文獻(xiàn)也很多。比較有代表性的有：吳璟莉[6]使用遺傳禁忌算法求解VRPTW問題。劉誠，陳治亞[7]提出了一種新的算法，初始種群構(gòu)建時采用隨機(jī)和構(gòu)造初始化法來構(gòu)造初始解，克服原有初始種群的單一性?；艏颜?，張磊[8]使用節(jié)約法來求解VRPTW問題，提出了一種基于節(jié)約值比較的最小化成本的啟發(fā)式算法。

當(dāng)VRPTW問題被學(xué)者們研究深入之后，學(xué)者們發(fā)現(xiàn)：現(xiàn)有研究的多是僅考慮車輛送貨的VRPTW問題。而現(xiàn)實(shí)中，車輛不僅要將貨物送到客戶手里，有時客戶還需要將一部分貨物裝上車帶回中心。裝卸一體化的VRPTW問題成為研究的重點(diǎn)。蔣泰[9]構(gòu)建了裝卸混合VRP問題的一般模型，并使用蟻群和禁忌算法求解此類問題。孫小年[10]使用改進(jìn)遺傳算法來求解此類問題。采用四位數(shù)的遺傳編碼，降低對交叉和變異算子的要求，有效地提高解的質(zhì)量。張濤[11]在原有模型的基礎(chǔ)上，加入了車輛最大行程約束，采用基于排序的螞蟻系統(tǒng)和最大最小螞蟻系統(tǒng)算法的信息素更新策略，設(shè)計了考慮車輛裝載率的啟發(fā)式算法，運(yùn)用此算法可以有效提高車輛的負(fù)載率，避免因負(fù)載波動而增加車輛總行程。本文正是在此基礎(chǔ)之上，提出了裝卸混合的VRP模型，使用遺傳禁忌算法進(jìn)行求解，與之前的算法得出的結(jié)果相比較，本文的結(jié)果更好。

1 模型建立

問題描述：單一配送中心，有n個客戶，多輛車（同車型），每個客戶既是需求客戶，又是供應(yīng)客戶。如何合理安排行車路線，使車輛能完成配送任務(wù)的同時，也能把客戶點(diǎn)提供的貨物運(yùn)回，減少空載率。并盡量保證貨物在客戶規(guī)定時間窗內(nèi)送至客戶手上。

模型建立如下：

模型中，式（1）表示運(yùn)輸中費(fèi)用包括三個部分：車輛使用費(fèi)用，車輛行駛費(fèi)用和時間成本。式（2）確保車輛從配送中心出發(fā)完成任務(wù)后回到配送中心。式（3）、式（4）保證每個客戶都被服務(wù)且僅被服務(wù)一次。式（5）、式（6）、式（7）表示車輛中裝載的貨物總重量不大于車輛本身的最大載重量。式（8）表示時間窗約束。到達(dá)客戶j時刻由四部分相加而成：到達(dá)客戶i時刻、i點(diǎn)的卸貨時間和i點(diǎn)的裝貨時間，從客戶i到客戶j的行駛時間。

2 算法設(shè)計

傳統(tǒng)的遺傳算法（GA）常被用來解決此類問題。源于其魯棒性強(qiáng)、并行搜索、收斂速度快、運(yùn)算簡單、搜索能力強(qiáng)、且對搜索空間無特別要求，無需求等優(yōu)點(diǎn)。但是應(yīng)用發(fā)現(xiàn)，使用該算法往往會使求出的解是局部最優(yōu)解，“早熟收斂”現(xiàn)象嚴(yán)重，通常全局最優(yōu)解往往還沒被搜索到，問題解即以被確定。

為了改善這些不足，本文提出了解決此種不足的辦法：在變異中引入了禁忌算法（TS），形成禁忌變異算子。TS的優(yōu)點(diǎn)在于：“爬山能力”很強(qiáng)?？梢院芎玫靥鼍植孔顑?yōu)解，大大增加了獲得全局最優(yōu)解的概率。

算法設(shè)計步驟：

Step1：（初始化）設(shè)置演化代數(shù)Ngen，種群規(guī)模Npop，交叉概率pc，變異概率pm。

Step2：（初始解）gen=0，使用自然數(shù)編碼方式，隨機(jī)產(chǎn)生Npop個個體，作為初始種群。

Step3：（評價個體）計算當(dāng)前群體中染色體的適應(yīng)值fi。

Step4：（選擇）采用最佳個體保留和賭輪法相結(jié)合的選擇策略。首先各個體適應(yīng)度值排序，適應(yīng)度值最大個體被保留，其他個體采用賭輪法，使適應(yīng)度大的個體被選擇的可能概率加大，適應(yīng)度小的個體被選擇的可能概率變小。

Step5：（交叉）：采用類PMX法交叉。

Step6：（變異、禁忌）：采用多點(diǎn)變異，并引入TS算法，對局部最優(yōu)解進(jìn)行把關(guān)，設(shè)立禁忌表，擴(kuò)大搜索范圍搜索，尋找全局最優(yōu)解。

Step7：gen=gen+1，如果gen＜Ngen，轉(zhuǎn)Step3；否則輸出最優(yōu)解，終止算法。

3 實(shí)例分析

假設(shè)某配送中心和20個客戶都分布在邊長為20km的正方形地域內(nèi)，每個客戶的貨物需求量和供應(yīng)量都在2t以內(nèi)，該配送中心有8輛車，其載重量為8t。本文利用計算機(jī)隨機(jī)產(chǎn)生了配送中心和20個客戶的位置坐標(biāo)以及各客戶的貨物需求量和供應(yīng)量，其中物流中心的坐標(biāo)為（3.2km，14.1km），20個客戶的坐標(biāo)和貨物需求量、供應(yīng)量、時間窗等見表1，另車輛在行駛過程中假設(shè)是勻速行駛的，速度為20km/h，則從i到j(luò)車輛行駛時間在這里，tij的單位用分鐘表示。要求根據(jù)上述條件，合理安排車輛配送路線，使目標(biāo)函數(shù)最小。

文中參數(shù)設(shè)置：d=100元/時，e=300元/時，Ngen=800，cij=10元/km，C=100，禁忌長度為10，禁忌迭代次數(shù)為400，每次迭代共搜索當(dāng)前解的40個鄰居。pc=0.6，pm=0.1。利用混合算法隨機(jī)求解10次。

本文使用C++進(jìn)行編程，試驗(yàn)結(jié)果如表2。

4 小 結(jié)

本文針對傳統(tǒng)遺傳算法“爬山能力”差，所得解易陷入局部最優(yōu)解的缺陷，采用遺傳禁忌混合遺傳算法來彌補(bǔ)這一缺陷，并用該混合算法來求解裝卸貨混合軟時間窗VRP問題，所得結(jié)果較原有使用遺傳算法求得解而言更優(yōu)。

表1 客戶相關(guān)信息

表2 混合算法求解得出結(jié)果

但是，在文章撰寫的過程中，對裝卸貨混合問題考慮還不是很全面，比如在本文中考慮的貨物都是可以混裝的，不能混裝的情況下相關(guān)貨物怎么處理沒有考慮；還有，客戶在本文中沒有區(qū)分重要客戶和一般客戶，統(tǒng)統(tǒng)做為一般對待?？涩F(xiàn)實(shí)中客戶往往區(qū)分重要客戶和一般客戶，對于重要客戶，沒有在規(guī)定時間窗內(nèi)送達(dá)給企業(yè)造成的損失往往大于那些一般客戶。

[1] 郎茂祥，胡思繼.車輛路徑問題的遺傳搜索算法研究[J].管理工程學(xué)報，2004,1(18):81-83.

[2] 郎茂祥.物流配送車輛調(diào)度問題的模型和算法研究[D].北京：北方交通大學(xué)（博士學(xué)位論文），2002.

[3] 郎茂祥.用單親遺傳算法求解配送車輛調(diào)度問題的研究[J].交通與計算機(jī)，2006,1(24):119-121.

[4] 肖鵬，李茂軍，張軍平,等.單親遺傳算法及其在物流配送系統(tǒng)中的應(yīng)用[J].系統(tǒng)工程，2000(1):64-66.

[5] 宋康，蔡延光，張敏捷,等.多目標(biāo)車輛路徑的遺傳算法[J].微計算機(jī)信息，2010,26(4-1):221-223.

[6] 吳璟莉，李陶深.遺傳算法與禁忌算法的混合策略在VRPTW問題上的應(yīng)用[J].計算機(jī)工程與應(yīng)用，2004,18:54-57.

[7] 劉誠，陳治亞，封全喜.軟時間窗物流配送車輛路徑問題的并行遺傳算法[J].系統(tǒng)工程，2005,10(10):7-10.

[8] 霍佳震，張磊.用節(jié)約法解決帶有時間窗的滿載車輛調(diào)度問題[J].工業(yè)工程與管理，2006(4):38-42.

[9] 蔣泰，殷佳林.具有同時送貨和取貨需求的車輛路徑問題的蟻群禁忌混合優(yōu)化算法[J].廣西科學(xué)院學(xué)報，2008,24(4):279-283.

[10] 孫小年，陳幼林，楊東援.裝卸一體化車輛路徑問題的遺傳算法研究[J].系統(tǒng)工程理論與實(shí)踐，2007,2:149-152.

[11] 張濤，田文馨，劉士新.帶車輛行程約束的VRPSPD問題的改進(jìn)蟻群算法[J].系統(tǒng)工程理論與實(shí)踐，2008,1:132-140.

[12] 楊宇棟,等.有時間窗車輛路徑問題的模型及其改進(jìn)模擬退火算法研究[J].管理工程學(xué)報，2006,3(20):104-107.

[13] 李大衛(wèi)，王夢光，王莉.一個求解帶有時間窗口約束的車輛路徑問題的啟發(fā)式算法[J].系統(tǒng)工程，1998,7:20-24.

[14] 郎茂祥.裝卸混合車輛路徑問題的模擬退火算法研究[J].系統(tǒng)工程學(xué)報，2005,20(5):485-491.

[15] 王曉博，李一軍.多車場多車型裝卸混合車輛路徑問題研究[J].控制與決策，2009,24(12):1769-1774.