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

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

0 引 言

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

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

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

不難發現，現實中應用多半是軟時間窗VRP問題，相關研究的文獻也很多。比較有代表性的有：吳璟莉[6]使用遺傳禁忌算法求解VRPTW問題。劉誠，陳治亞[7]提出了一種新的算法，初始種群構建時采用隨機和構造初始化法來構造初始解，克服原有初始種群的單一性。霍佳震，張磊[8]使用節約法來求解VRPTW問題，提出了一種基于節約值比較的最小化成本的啟發式算法。

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

1 模型建立

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

模型建立如下：

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

2 算法設計

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

為了改善這些不足，本文提出了解決此種不足的辦法：在變異中引入了禁忌算法（TS），形成禁忌變異算子。TS的優點在于：“爬山能力”很強。可以很好地跳出局部最優解，大大增加了獲得全局最優解的概率。

算法設計步驟：

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

Step2：（初始解）gen=0，使用自然數編碼方式，隨機產生Npop個個體，作為初始種群。

Step3：（評價個體）計算當前群體中染色體的適應值fi。

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

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

Step6：（變異、禁忌）：采用多點變異，并引入TS算法，對局部最優解進行把關，設立禁忌表，擴大搜索范圍搜索，尋找全局最優解。

Step7：gen=gen+1，如果gen＜Ngen，轉Step3；否則輸出最優解，終止算法。

3 實例分析

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

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

本文使用C++進行編程，試驗結果如表2。

4 小 結

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

表1 客戶相關信息

表2 混合算法求解得出結果

但是，在文章撰寫的過程中，對裝卸貨混合問題考慮還不是很全面，比如在本文中考慮的貨物都是可以混裝的，不能混裝的情況下相關貨物怎么處理沒有考慮；還有，客戶在本文中沒有區分重要客戶和一般客戶，統統做為一般對待。可現實中客戶往往區分重要客戶和一般客戶，對于重要客戶，沒有在規定時間窗內送達給企業造成的損失往往大于那些一般客戶。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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