張 倩,丁根宏
(河海大學(xué)理學(xué)院,南京 211100)
隨著互聯(lián)網(wǎng)的普及和信息技術(shù)的高速發(fā)展,人類進(jìn)入了以網(wǎng)絡(luò)為主的信息時代?;贗nternet開展的電子商務(wù)已經(jīng)逐漸成為人們進(jìn)行商務(wù)活動的新模式。而物流是電子商務(wù)的核心力量,其快速、通暢是電子商務(wù)可以正常、順利進(jìn)行的一個重要保證[1]。
車輛路徑問題(vehicle routing problem,VRP)[2]是物流配送系統(tǒng)中的關(guān)鍵環(huán)節(jié),是在1959年由Dantzig和Ramser共同提出的。車輛路徑問題是近年來研究的一個熱點問題,其中最廣泛關(guān)注的問題如快遞問題中的線路優(yōu)化問題、信件運輸與投遞問題等[3]。
PDPTW[4-5]是一類具有廣泛實際應(yīng)用的優(yōu)化組合問題。PDPTW是指一列車隊必須完成的運輸需求,裝貨點和卸貨點是組成運輸任務(wù)的2個需求要素。配送中心的每輛車從車庫出發(fā),沿所選的最優(yōu)化路線為客戶服務(wù),以滿足客戶的運輸需求,并最終返回車庫。車輛在訪問客戶點時,必須依次服務(wù)所有需求,且滿足時間窗、負(fù)載的限制,并最終返回車庫。要用最大裝貨量和裝載貨物類型來限制每輛車,但是由于裝貨點和卸貨點所在的實際位置不同,所以車輛必須在給出的時間窗口范圍內(nèi)訪問到每個客戶點。在解決PDPTW問題時,為了方便,定義其為整數(shù)線性規(guī)劃問題。由于PDPTW問題比VRP問題多了時間窗限制,所以PDPTW是對VRP的擴(kuò)展,VRP又是TSP的一種推廣,而TSP已被證明是一個NP-h(huán)ard問題[6]。因此,在解決PDPTW也具有許多類似的實際困難。由于PDPTW可以作為物流中運籌規(guī)劃問題的模型,在實際生活中的應(yīng)用越來越多,從而引起國內(nèi)外學(xué)者的廣泛關(guān)注。
根據(jù)上述對PDPTW問題的定義,給出該問題的總體描述:首先設(shè)定不限定配貨車輛的數(shù)目,并設(shè)負(fù)載Q都相同。設(shè)有1個中心車庫,需要對L個客戶點進(jìn)行配送服務(wù),令i為變量,i=1,2,…,L。定義客戶點 i的裝貨地點為 i,卸貨地點為L+i,用點O和2L+1表示中心車場。由于所處的地理位置可能不能和點一一對應(yīng),每個貨物都有各自的裝貨點和卸貨點,故有可能出現(xiàn)同一個點既是裝貨點又是卸貨點的情況。設(shè)N={1,2,…,L,L+1,…,2L}為所有裝貨點與卸貨點的集合。P+={1,2,…,L}為裝貨點集合,P-={L+1,L+2,…,2L}為卸貨點集合,V={0,2L+1}為中心車場集合,N*=N∪V,M={1,2,…,m}為車輛集合。車輛在客戶點i的貨物裝卸量為qi,i∈N。要從點i運到點L+i,qi為正數(shù)時則為裝貨,為負(fù)數(shù)時則為卸貨,車輛k運輸?shù)娇蛻酎ci時的負(fù)載量為 zik。設(shè)點 i的裝貨時間窗口為[ei,li],卸貨時間窗口為[eL+i,lL+i],[e0,l0]表示車輛從中心車場開始的時間窗口,[e2L+1,l2L+1]表示回到中心車場的時間窗口。?i,j∈N*,tij代表從點 i到點 j的行駛時間,cij代表從點i到點j的行駛距離,si為車輛在客戶點i處的服務(wù)時間,ti為車輛在客戶點i開始服務(wù)的時間,ei表示為允許客戶點i服務(wù)的最早時間,li表示為允許客戶點i服務(wù)的最遲時間,這里[ei,li]表示一個時間窗。從中心車場派出車輛,為這些客戶點的需求進(jìn)行服務(wù),并且在客戶點規(guī)定的時間窗內(nèi)進(jìn)行服務(wù),最后要返回到到中心車場,要求找到使用車輛總費用最少的車輛路徑方案。
針對上面的描述,將引進(jìn)2個變量:
數(shù)學(xué)模型[7]為:
在此模型中:式(1)、(2)是目標(biāo)函數(shù),分別是車輛的數(shù)目與每個車輛行駛距離;式(3)表示每個客戶點只被服務(wù)1次;式(4)、(5)表示每個客戶點只有1輛智能車進(jìn)行服務(wù);式(6)表示一個客戶的裝貨點與卸貨點必須由同一輛車進(jìn)行服務(wù);式(7)、(8)表示車輛必須從中心車場出發(fā),最后要返回至中心車場;式(9)~(11)表示時間窗、前序;式(12)、(13)是車輛負(fù)載。
由于PDPTW是多目標(biāo)優(yōu)化問題,本文主要研究的優(yōu)化目標(biāo)為:① 使用車輛總數(shù)最小;② 行車總距離最小,即車輛行駛路線的總長度最小。
為減少PDPTW問題的計算復(fù)雜度,本文提出了一種混合分組編碼智能算法來求解此類問題。該算法結(jié)合了遺傳算法與粒子群算法在解決PDPTW時的優(yōu)點。
粒子群算法是一種基于群體迭代的優(yōu)化算法,該算法通過粒子個體之間的互相協(xié)助來尋找最優(yōu)解。葉海燕等[9]提出了分組粒子群算法,這種算法其實是對粒子群算法的一種改進(jìn),該算法在運行時將種群分成若干個小組,對每個小組分別設(shè)置不同的算法參數(shù)進(jìn)行搜索和優(yōu)化。本文將繼續(xù)采用粒子群算法來搜索不容易搜索到而且精度較高的解。
遺傳算法是一種新型的全局優(yōu)化搜索算法,它的基本思想就是模擬達(dá)爾文適者生存的自然選擇和遺傳機(jī)理的進(jìn)化過程,對優(yōu)化組合問題中的NP-hard問題的求解非常有效。商麗媛[7]在Giselher Pankratz提出的一種分組編碼遺傳算法[8]基礎(chǔ)上,給出了一種多策略分組編碼遺傳算法,并用該算法對國際上的算例集進(jìn)行計算,結(jié)果表明,該算法的搜索性能比國際上的其他算法要好。本文將在混合分組編碼智能算法后期采用上述改進(jìn)的分組編碼遺傳算法來進(jìn)行優(yōu)化求解。
混合分組編碼智能算法的步驟:
第1步隨機(jī)產(chǎn)生1個初始種群P,設(shè)定種群規(guī)模;
第2步先采用分組粒子群算法進(jìn)行m次迭代,將初始種群P分成m個小組,在每個小組中對各自的參數(shù)進(jìn)行初始化;
第3步在各個小組內(nèi)獨立進(jìn)行粒子群優(yōu)化迭代,迭代周期為t,對各小組進(jìn)行相同次數(shù)的種群變異和重組操作;
第4步更新各小組中各自的參數(shù);
第5步繼續(xù)進(jìn)行迭代,若滿足終止條件繼續(xù)第6步,否則返回第3步;
第6步對種群實施多策略分組編碼遺傳算法優(yōu)化,根據(jù)個體適應(yīng)度值排序保優(yōu);
第7步對選擇后的種群進(jìn)行交叉操作;
第8步交叉后的種群進(jìn)行選擇操作,排序保優(yōu);
第9步算法繼續(xù)進(jìn)行優(yōu)化,當(dāng)滿足算法的終止條件時停止,否則返回第6步。
混合分組編碼智能算法流程見圖1。
圖1 混合分組編碼智能算法流程
下面給出PDPTW中簡單的算例來分析混合分組編碼智能算法性能。
以某縣為例,縣郵政局M轄有16個郵政支局。該縣郵局M每天將從市局送來的郵件派送到所轄支局,并將由這些支局收寄的郵件運回縣局X。郵車每天早上9:00出發(fā),最遲15:00回到縣局。郵車平均時速為30 km/h,郵車在支局卸裝郵件耗時5 min,每輛郵車最多容納65袋郵件。以縣局M及其所轄的16個支局為研究對象,在規(guī)定的時限以及郵車容量的約束下,以郵車數(shù)量最少、郵車所行駛的總郵路里程最短為優(yōu)化目標(biāo),合理規(guī)劃郵路。表1為每個支局的郵件量。表2為縣支局之間的距離。
表1 每個支局的郵件量
表2 縣支局之間的距離 km
由表1中數(shù)據(jù)可知,寄達(dá)各支局的郵件量為176袋,而從支局收寄的郵件量為170袋。由于郵車最多容納65袋郵件,所以可計算出縣局至少需要3輛郵車才能滿足該縣的郵件運輸需求。得到最少郵車數(shù)量為3。
有些文獻(xiàn)中還考慮以空車率造成損失最小為優(yōu)化目標(biāo),但經(jīng)過測試發(fā)現(xiàn),在最小化空車率造成損失時,雖然目標(biāo)值有一定減小,但卻造成運行里程和時間的大幅增加,綜合考慮成本時仍是增加的。追求降低空車率會與追求最短里程相沖突,所以這里不予考慮空車率目標(biāo)。
以總郵路里程最短為目標(biāo),即
約束條件包括時間約束:
容量約束:
采用混合分組編碼智能算法進(jìn)行迭代。得到最優(yōu)路線為:
車1路線:M—13—1—2—3—4—M
車2路線:M—10—9—8—7—5—6—(4)—M
車3路線:M—14—15—16—(15)—11—12—M
注:括號內(nèi)表示郵車只經(jīng)過而不裝卸郵件。
將算法計算的結(jié)果與相同實例的其他算法計算結(jié)果進(jìn)行比較,得到如表3結(jié)果。
表3 各算法結(jié)果的比較
上述所有測試都是在PC(Inter,2.40 GHz)機(jī)上進(jìn)行的。由表3可以看出,混合分組編碼智能算法求解的總花費時間最少,相對于改進(jìn)型貪心算法[9]和改進(jìn)蟻群算法[10],路程縮短了,時間節(jié)省了,解的精度更高。
本文在描述PDPTW問題的基礎(chǔ)上,將粒子群算法與分組編碼遺傳算法相結(jié)合,提出了一種混合分組編碼智能算法。但該算法在計算PDPTW算例時,只是在相對簡單的算例上得到較好的解,而對國際上的某些算例集還不能達(dá)到理想的效果,所以還需對算法進(jìn)行進(jìn)一步的改進(jìn)。
[1]劉華軍,劉軍.電子商務(wù)對物流及其管理的影響[J].商品儲運與保護(hù),2001(1):25-29.
[2]Dantzing G,Rasmer J.The truck dispatching problem[J].Management science,1959,(6):80 -91.
[3]李軍,郭耀煌.物流配送車輛優(yōu)化調(diào)度理論與方法[M].北京:中國物資出版社,2001.
[4]Savelsbergh M W P,Sol M.The General Pickup and Delivery Problem[J].Transportation Science,1991(29):17-29.
[5]Dumas Y,Desrosiers J,Soumis F.The Pickup and Delivery Problem with Time Windows[J].European Journal of Operational Research,1991(54):7 -22.
[6]Lenstra J K,Rinnooy K.Complexity of Vehicle Routing and Scheduling Problem[J].Networks,1981,40(2):221-227.
[7]商麗媛,丁根宏.有時間窗裝卸問題的多策略分組編碼遺傳算法[J].數(shù)學(xué)的實踐與認(rèn)識,2010,40(2):8-14.
[8]Giselher Pankratz.A Gouping Genetic Algorithm for the Pickup and Delivery Problem with Time Windows[J].Operatons Research,2005(27):21 -41.
[9]葉海燕,陳毓靈,高鷹.分組粒子群優(yōu)化算法[J].廣州大學(xué)學(xué)報,2007,6(2):64 -67.
[10]胡震宇,吳華玉,唐燕.郵政運輸網(wǎng)絡(luò)中的郵路規(guī)劃和郵車調(diào)度[J].數(shù)學(xué)實踐與認(rèn)識,2008,38(14):210-221.
[11]商麗媛.車輛路徑問題遺傳算法的設(shè)計與分析[D].南京:河海大學(xué),2006.