張 亮,杜培俊,何兆芳(中國十七冶集團有限公司,安徽 馬鞍山 243000)
配送一直是物流企業(yè)頭疼的問題。物流企業(yè)往往在配送過程中造成很大的浪費。配送前的合理規(guī)劃,尤其是配送前車輛路線合理規(guī)劃,可以在一定程度上降低配送成本,減少配送過程中不必要的浪費。
對于車輛路線規(guī)劃問題,最初歸結(jié)為一般VRP問題,對此類問題的一般表述為:單一配送中心有一系列客戶點,需要合理安排車隊,使車隊有序地通過他們,在滿足一定的約束條件(如貨物需求量、發(fā)送量、交貨時間、車輛容量限制、行使里程限制)下,達到一定的目標(biāo)(如路程最短、費用最少、時間盡量少、使用車輛數(shù)盡量少等),并返回車輛停放場地。文獻[1-5]分別從構(gòu)建模型和使用算法改進方面解決此類問題,通過改進模型和算法的改進,將原先得出的結(jié)果加以優(yōu)化。
當(dāng)約束條件中增入時間約束之后,原本的VRP問題轉(zhuǎn)變成為VRPTW問題。此類問題分為兩類:軟時間窗VRP問題和硬時間窗VRP問題。硬時間窗VRP問題要求車輛必須在客戶要求的時間窗內(nèi)將貨物到達,否則拒收。此問題對時間的要求很高;而軟時間窗VRP問題則可以允許車輛在客戶允許的容忍范圍內(nèi)將貨物到達,客戶并不會拒收,但是車輛會接到客戶要求的懲罰。此問題對時間的要求并沒有很高。
不難發(fā)現(xiàn),現(xiàn)實中應(yīng)用多半是軟時間窗VRP問題,相關(guān)研究的文獻也很多。比較有代表性的有:吳璟莉[6]使用遺傳禁忌算法求解VRPTW問題。劉誠,陳治亞[7]提出了一種新的算法,初始種群構(gòu)建時采用隨機和構(gòu)造初始化法來構(gòu)造初始解,克服原有初始種群的單一性?;艏颜穑瑥埨赱8]使用節(jié)約法來求解VRPTW問題,提出了一種基于節(jié)約值比較的最小化成本的啟發(fā)式算法。
當(dāng)VRPTW問題被學(xué)者們研究深入之后,學(xué)者們發(fā)現(xiàn):現(xiàn)有研究的多是僅考慮車輛送貨的VRPTW問題。而現(xiàn)實中,車輛不僅要將貨物送到客戶手里,有時客戶還需要將一部分貨物裝上車帶回中心。裝卸一體化的VRPTW問題成為研究的重點。蔣泰[9]構(gòu)建了裝卸混合VRP問題的一般模型,并使用蟻群和禁忌算法求解此類問題。孫小年[10]使用改進遺傳算法來求解此類問題。采用四位數(shù)的遺傳編碼,降低對交叉和變異算子的要求,有效地提高解的質(zhì)量。張濤[11]在原有模型的基礎(chǔ)上,加入了車輛最大行程約束,采用基于排序的螞蟻系統(tǒng)和最大最小螞蟻系統(tǒng)算法的信息素更新策略,設(shè)計了考慮車輛裝載率的啟發(fā)式算法,運用此算法可以有效提高車輛的負(fù)載率,避免因負(fù)載波動而增加車輛總行程。本文正是在此基礎(chǔ)之上,提出了裝卸混合的VRP模型,使用遺傳禁忌算法進行求解,與之前的算法得出的結(jié)果相比較,本文的結(jié)果更好。
問題描述:單一配送中心,有n個客戶,多輛車(同車型),每個客戶既是需求客戶,又是供應(yīng)客戶。如何合理安排行車路線,使車輛能完成配送任務(wù)的同時,也能把客戶點提供的貨物運回,減少空載率。并盡量保證貨物在客戶規(guī)定時間窗內(nèi)送至客戶手上。
模型建立如下:
模型中,式(1)表示運輸中費用包括三個部分:車輛使用費用,車輛行駛費用和時間成本。式(2)確保車輛從配送中心出發(fā)完成任務(wù)后回到配送中心。式(3)、式(4)保證每個客戶都被服務(wù)且僅被服務(wù)一次。式(5)、式(6)、式(7)表示車輛中裝載的貨物總重量不大于車輛本身的最大載重量。式(8)表示時間窗約束。到達客戶j時刻由四部分相加而成:到達客戶i時刻、i點的卸貨時間和i點的裝貨時間,從客戶i到客戶j的行駛時間。
傳統(tǒng)的遺傳算法(GA)常被用來解決此類問題。源于其魯棒性強、并行搜索、收斂速度快、運算簡單、搜索能力強、且對搜索空間無特別要求,無需求等優(yōu)點。但是應(yīng)用發(fā)現(xiàn),使用該算法往往會使求出的解是局部最優(yōu)解,“早熟收斂”現(xiàn)象嚴(yán)重,通常全局最優(yōu)解往往還沒被搜索到,問題解即以被確定。
為了改善這些不足,本文提出了解決此種不足的辦法:在變異中引入了禁忌算法(TS),形成禁忌變異算子。TS的優(yōu)點在于:“爬山能力”很強??梢院芎玫靥鼍植孔顑?yōu)解,大大增加了獲得全局最優(yōu)解的概率。
算法設(shè)計步驟:
Step1:(初始化)設(shè)置演化代數(shù)Ngen,種群規(guī)模Npop,交叉概率pc,變異概率pm。
Step2:(初始解)gen=0,使用自然數(shù)編碼方式,隨機產(chǎn)生Npop個個體,作為初始種群。
Step3:(評價個體)計算當(dāng)前群體中染色體的適應(yīng)值fi。
Step4:(選擇)采用最佳個體保留和賭輪法相結(jié)合的選擇策略。首先各個體適應(yīng)度值排序,適應(yīng)度值最大個體被保留,其他個體采用賭輪法,使適應(yīng)度大的個體被選擇的可能概率加大,適應(yīng)度小的個體被選擇的可能概率變小。
Step5:(交叉):采用類PMX法交叉。
Step6:(變異、禁忌):采用多點變異,并引入TS算法,對局部最優(yōu)解進行把關(guān),設(shè)立禁忌表,擴大搜索范圍搜索,尋找全局最優(yōu)解。
Step7:gen=gen+1,如果gen<Ngen,轉(zhuǎn)Step3;否則輸出最優(yōu)解,終止算法。
假設(shè)某配送中心和20個客戶都分布在邊長為20km的正方形地域內(nèi),每個客戶的貨物需求量和供應(yīng)量都在2t以內(nèi),該配送中心有8輛車,其載重量為8t。本文利用計算機隨機產(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。利用混合算法隨機求解10次。
本文使用C++進行編程,試驗結(jié)果如表2。
本文針對傳統(tǒng)遺傳算法“爬山能力”差,所得解易陷入局部最優(yōu)解的缺陷,采用遺傳禁忌混合遺傳算法來彌補這一缺陷,并用該混合算法來求解裝卸貨混合軟時間窗VRP問題,所得結(jié)果較原有使用遺傳算法求得解而言更優(yōu)。
表1 客戶相關(guān)信息
表2 混合算法求解得出結(jié)果
但是,在文章撰寫的過程中,對裝卸貨混合問題考慮還不是很全面,比如在本文中考慮的貨物都是可以混裝的,不能混裝的情況下相關(guān)貨物怎么處理沒有考慮;還有,客戶在本文中沒有區(qū)分重要客戶和一般客戶,統(tǒng)統(tǒng)做為一般對待。可現(xiàn)實中客戶往往區(qū)分重要客戶和一般客戶,對于重要客戶,沒有在規(guī)定時間窗內(nèi)送達給企業(yè)造成的損失往往大于那些一般客戶。
[1] 郎茂祥,胡思繼.車輛路徑問題的遺傳搜索算法研究[J].管理工程學(xué)報,2004,1(18):81-83.
[2] 郎茂祥.物流配送車輛調(diào)度問題的模型和算法研究[D].北京:北方交通大學(xué)(博士學(xué)位論文),2002.
[3] 郎茂祥.用單親遺傳算法求解配送車輛調(diào)度問題的研究[J].交通與計算機,2006,1(24):119-121.
[4] 肖鵬,李茂軍,張軍平,等.單親遺傳算法及其在物流配送系統(tǒng)中的應(yīng)用[J].系統(tǒng)工程,2000(1):64-66.
[5] 宋康,蔡延光,張敏捷,等.多目標(biāo)車輛路徑的遺傳算法[J].微計算機信息,2010,26(4-1):221-223.
[6] 吳璟莉,李陶深.遺傳算法與禁忌算法的混合策略在VRPTW問題上的應(yīng)用[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)工程理論與實踐,2007,2:149-152.
[11] 張濤,田文馨,劉士新.帶車輛行程約束的VRPSPD問題的改進蟻群算法[J].系統(tǒng)工程理論與實踐,2008,1:132-140.
[12] 楊宇棟,等.有時間窗車輛路徑問題的模型及其改進模擬退火算法研究[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.