張 倩，丁根宏

(河海大學(xué)理學(xué)院，南京 211100)

隨著互聯(lián)網(wǎng)的普及和信息技術(shù)的高速發(fā)展，人類進(jìn)入了以網(wǎng)絡(luò)為主的信息時(shí)代?；贗nternet開展的電子商務(wù)已經(jīng)逐漸成為人們進(jìn)行商務(wù)活動(dòng)的新模式。而物流是電子商務(wù)的核心力量，其快速、通暢是電子商務(wù)可以正常、順利進(jìn)行的一個(gè)重要保證［1］。

車輛路徑問題(vehicle routing problem，VRP)［2］是物流配送系統(tǒng)中的關(guān)鍵環(huán)節(jié)，是在1959年由Dantzig和Ramser共同提出的。車輛路徑問題是近年來研究的一個(gè)熱點(diǎn)問題，其中最廣泛關(guān)注的問題如快遞問題中的線路優(yōu)化問題、信件運(yùn)輸與投遞問題等［3］。

PDPTW［4－5］是一類具有廣泛實(shí)際應(yīng)用的優(yōu)化組合問題。PDPTW是指一列車隊(duì)必須完成的運(yùn)輸需求，裝貨點(diǎn)和卸貨點(diǎn)是組成運(yùn)輸任務(wù)的2個(gè)需求要素。配送中心的每輛車從車庫出發(fā)，沿所選的最優(yōu)化路線為客戶服務(wù)，以滿足客戶的運(yùn)輸需求，并最終返回車庫。車輛在訪問客戶點(diǎn)時(shí)，必須依次服務(wù)所有需求，且滿足時(shí)間窗、負(fù)載的限制，并最終返回車庫。要用最大裝貨量和裝載貨物類型來限制每輛車，但是由于裝貨點(diǎn)和卸貨點(diǎn)所在的實(shí)際位置不同，所以車輛必須在給出的時(shí)間窗口范圍內(nèi)訪問到每個(gè)客戶點(diǎn)。在解決PDPTW問題時(shí)，為了方便，定義其為整數(shù)線性規(guī)劃問題。由于PDPTW問題比VRP問題多了時(shí)間窗限制，所以PDPTW是對(duì)VRP的擴(kuò)展，VRP又是TSP的一種推廣，而TSP已被證明是一個(gè)NP－h(huán)ard問題［6］。因此，在解決PDPTW也具有許多類似的實(shí)際困難。由于PDPTW可以作為物流中運(yùn)籌規(guī)劃問題的模型，在實(shí)際生活中的應(yīng)用越來越多，從而引起國內(nèi)外學(xué)者的廣泛關(guān)注。

1 PDPTW描述及模型

根據(jù)上述對(duì)PDPTW問題的定義，給出該問題的總體描述:首先設(shè)定不限定配貨車輛的數(shù)目，并設(shè)負(fù)載Q都相同。設(shè)有1個(gè)中心車庫，需要對(duì)L個(gè)客戶點(diǎn)進(jìn)行配送服務(wù)，令i為變量，i=1，2，…，L。定義客戶點(diǎn) i的裝貨地點(diǎn)為 i，卸貨地點(diǎn)為L+i，用點(diǎn)O和2L+1表示中心車場(chǎng)。由于所處的地理位置可能不能和點(diǎn)一一對(duì)應(yīng)，每個(gè)貨物都有各自的裝貨點(diǎn)和卸貨點(diǎn)，故有可能出現(xiàn)同一個(gè)點(diǎn)既是裝貨點(diǎn)又是卸貨點(diǎn)的情況。設(shè)N={1，2，…，L，L+1，…，2L}為所有裝貨點(diǎn)與卸貨點(diǎn)的集合。P+={1，2，…，L}為裝貨點(diǎn)集合，P－={L+1，L+2，…，2L}為卸貨點(diǎn)集合，V={0，2L+1}為中心車場(chǎng)集合，N*=N∪V，M={1，2，…，m}為車輛集合。車輛在客戶點(diǎn)i的貨物裝卸量為qi，i∈N。要從點(diǎn)i運(yùn)到點(diǎn)L+i，qi為正數(shù)時(shí)則為裝貨，為負(fù)數(shù)時(shí)則為卸貨，車輛k運(yùn)輸?shù)娇蛻酎c(diǎn)i時(shí)的負(fù)載量為 zik。設(shè)點(diǎn) i的裝貨時(shí)間窗口為［ei，li］，卸貨時(shí)間窗口為［eL+i，lL+i］，［e0，l0］表示車輛從中心車場(chǎng)開始的時(shí)間窗口，［e2L+1，l2L+1］表示回到中心車場(chǎng)的時(shí)間窗口。?i，j∈N*，tij代表從點(diǎn) i到點(diǎn) j的行駛時(shí)間，cij代表從點(diǎn)i到點(diǎn)j的行駛距離，si為車輛在客戶點(diǎn)i處的服務(wù)時(shí)間，ti為車輛在客戶點(diǎn)i開始服務(wù)的時(shí)間，ei表示為允許客戶點(diǎn)i服務(wù)的最早時(shí)間，li表示為允許客戶點(diǎn)i服務(wù)的最遲時(shí)間，這里［ei，li］表示一個(gè)時(shí)間窗。從中心車場(chǎng)派出車輛，為這些客戶點(diǎn)的需求進(jìn)行服務(wù)，并且在客戶點(diǎn)規(guī)定的時(shí)間窗內(nèi)進(jìn)行服務(wù)，最后要返回到到中心車場(chǎng)，要求找到使用車輛總費(fèi)用最少的車輛路徑方案。

針對(duì)上面的描述，將引進(jìn)2個(gè)變量:

數(shù)學(xué)模型［7］為:

在此模型中:式(1)、(2)是目標(biāo)函數(shù)，分別是車輛的數(shù)目與每個(gè)車輛行駛距離;式(3)表示每個(gè)客戶點(diǎn)只被服務(wù)1次;式(4)、(5)表示每個(gè)客戶點(diǎn)只有1輛智能車進(jìn)行服務(wù);式(6)表示一個(gè)客戶的裝貨點(diǎn)與卸貨點(diǎn)必須由同一輛車進(jìn)行服務(wù);式(7)、(8)表示車輛必須從中心車場(chǎng)出發(fā)，最后要返回至中心車場(chǎng);式(9)～(11)表示時(shí)間窗、前序;式(12)、(13)是車輛負(fù)載。

由于PDPTW是多目標(biāo)優(yōu)化問題，本文主要研究的優(yōu)化目標(biāo)為:① 使用車輛總數(shù)最小;② 行車總距離最小，即車輛行駛路線的總長度最小。

2 混合分組編碼智能算法

為減少PDPTW問題的計(jì)算復(fù)雜度，本文提出了一種混合分組編碼智能算法來求解此類問題。該算法結(jié)合了遺傳算法與粒子群算法在解決PDPTW時(shí)的優(yōu)點(diǎn)。

粒子群算法是一種基于群體迭代的優(yōu)化算法，該算法通過粒子個(gè)體之間的互相協(xié)助來尋找最優(yōu)解。葉海燕等［9］提出了分組粒子群算法，這種算法其實(shí)是對(duì)粒子群算法的一種改進(jìn)，該算法在運(yùn)行時(shí)將種群分成若干個(gè)小組，對(duì)每個(gè)小組分別設(shè)置不同的算法參數(shù)進(jìn)行搜索和優(yōu)化。本文將繼續(xù)采用粒子群算法來搜索不容易搜索到而且精度較高的解。

遺傳算法是一種新型的全局優(yōu)化搜索算法，它的基本思想就是模擬達(dá)爾文適者生存的自然選擇和遺傳機(jī)理的進(jìn)化過程，對(duì)優(yōu)化組合問題中的NP-hard問題的求解非常有效。商麗媛［7］在Giselher Pankratz提出的一種分組編碼遺傳算法［8］基礎(chǔ)上，給出了一種多策略分組編碼遺傳算法，并用該算法對(duì)國際上的算例集進(jìn)行計(jì)算，結(jié)果表明，該算法的搜索性能比國際上的其他算法要好。本文將在混合分組編碼智能算法后期采用上述改進(jìn)的分組編碼遺傳算法來進(jìn)行優(yōu)化求解。

混合分組編碼智能算法的步驟:

第1步隨機(jī)產(chǎn)生1個(gè)初始種群P，設(shè)定種群規(guī)模;

第2步先采用分組粒子群算法進(jìn)行m次迭代，將初始種群P分成m個(gè)小組，在每個(gè)小組中對(duì)各自的參數(shù)進(jìn)行初始化;

第3步在各個(gè)小組內(nèi)獨(dú)立進(jìn)行粒子群優(yōu)化迭代，迭代周期為t，對(duì)各小組進(jìn)行相同次數(shù)的種群變異和重組操作;

第4步更新各小組中各自的參數(shù);

第5步繼續(xù)進(jìn)行迭代，若滿足終止條件繼續(xù)第6步，否則返回第3步;

第6步對(duì)種群實(shí)施多策略分組編碼遺傳算法優(yōu)化，根據(jù)個(gè)體適應(yīng)度值排序保優(yōu);

第7步對(duì)選擇后的種群進(jìn)行交叉操作;

第8步交叉后的種群進(jìn)行選擇操作，排序保優(yōu);

第9步算法繼續(xù)進(jìn)行優(yōu)化，當(dāng)滿足算法的終止條件時(shí)停止，否則返回第6步。

混合分組編碼智能算法流程見圖1。

圖1 混合分組編碼智能算法流程

3 實(shí)例計(jì)算

下面給出PDPTW中簡單的算例來分析混合分組編碼智能算法性能。

以某縣為例，縣郵政局M轄有16個(gè)郵政支局。該縣郵局M每天將從市局送來的郵件派送到所轄支局，并將由這些支局收寄的郵件運(yùn)回縣局X。郵車每天早上9:00出發(fā)，最遲15:00回到縣局。郵車平均時(shí)速為30 km/h，郵車在支局卸裝郵件耗時(shí)5 min，每輛郵車最多容納65袋郵件。以縣局M及其所轄的16個(gè)支局為研究對(duì)象，在規(guī)定的時(shí)限以及郵車容量的約束下，以郵車數(shù)量最少、郵車所行駛的總郵路里程最短為優(yōu)化目標(biāo)，合理規(guī)劃郵路。表1為每個(gè)支局的郵件量。表2為縣支局之間的距離。

表1 每個(gè)支局的郵件量

表2 縣支局之間的距離 km

由表1中數(shù)據(jù)可知，寄達(dá)各支局的郵件量為176袋，而從支局收寄的郵件量為170袋。由于郵車最多容納65袋郵件，所以可計(jì)算出縣局至少需要3輛郵車才能滿足該縣的郵件運(yùn)輸需求。得到最少郵車數(shù)量為3。

有些文獻(xiàn)中還考慮以空車率造成損失最小為優(yōu)化目標(biāo)，但經(jīng)過測(cè)試發(fā)現(xiàn)，在最小化空車率造成損失時(shí)，雖然目標(biāo)值有一定減小，但卻造成運(yùn)行里程和時(shí)間的大幅增加，綜合考慮成本時(shí)仍是增加的。追求降低空車率會(huì)與追求最短里程相沖突，所以這里不予考慮空車率目標(biāo)。

以總郵路里程最短為目標(biāo)，即

約束條件包括時(shí)間約束:

容量約束:

采用混合分組編碼智能算法進(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

注:括號(hào)內(nèi)表示郵車只經(jīng)過而不裝卸郵件。

將算法計(jì)算的結(jié)果與相同實(shí)例的其他算法計(jì)算結(jié)果進(jìn)行比較，得到如表3結(jié)果。

表3 各算法結(jié)果的比較

上述所有測(cè)試都是在PC(Inter，2.40 GHz)機(jī)上進(jìn)行的。由表3可以看出，混合分組編碼智能算法求解的總花費(fèi)時(shí)間最少，相對(duì)于改進(jìn)型貪心算法［9］和改進(jìn)蟻群算法［10］，路程縮短了，時(shí)間節(jié)省了，解的精度更高。

4 結(jié)束語

本文在描述PDPTW問題的基礎(chǔ)上，將粒子群算法與分組編碼遺傳算法相結(jié)合，提出了一種混合分組編碼智能算法。但該算法在計(jì)算PDPTW算例時(shí)，只是在相對(duì)簡單的算例上得到較好的解，而對(duì)國際上的某些算例集還不能達(dá)到理想的效果，所以還需對(duì)算法進(jìn)行進(jìn)一步的改進(jìn)。

［1］劉華軍，劉軍.電子商務(wù)對(duì)物流及其管理的影響［J］.商品儲(chǔ)運(yùn)與保護(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］商麗媛，丁根宏.有時(shí)間窗裝卸問題的多策略分組編碼遺傳算法［J］.數(shù)學(xué)的實(shí)踐與認(rèn)識(shí)，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é)報(bào)，2007，6(2):64 －67.

［10］胡震宇，吳華玉，唐燕.郵政運(yùn)輸網(wǎng)絡(luò)中的郵路規(guī)劃和郵車調(diào)度［J］.數(shù)學(xué)實(shí)踐與認(rèn)識(shí)，2008，38(14):210－221.

［11］商麗媛.車輛路徑問題遺傳算法的設(shè)計(jì)與分析［D］.南京:河海大學(xué)，2006.