1、第25卷第1期2005年2月杭州電子科技大學(xué)學(xué)報JournalofHangzhouDianziUniversityVol.25,No.1Feb.2005物流配送路線模型優(yōu)化及應(yīng)用卜心怡,于濤(杭州電子科技大學(xué)管理學(xué)院,浙江杭州310018)摘要:在物流配送問題中,車輛調(diào)度問題(VRP)是一個關(guān)鍵問題,也是組合優(yōu)化領(lǐng)域的前沿與熱點(diǎn)問題。該文根據(jù)MG公司配送中心的特點(diǎn),建立了該公司的VRP模型,公司配送網(wǎng)絡(luò)進(jìn)行了細(xì)致的優(yōu)化,找到一個滿意的方案。關(guān)鍵詞:配送中心;啟發(fā)式算法;節(jié)約算法;車輛調(diào)度問題中圖分類號:F224.3文獻(xiàn)標(biāo)識碼:A(2005)-0引言,稱之為“配送”。配送的特點(diǎn)一是直接面向用戶的

2、運(yùn)送活動,;在配送問題中,車輛調(diào)度問題(VehicleRVRP)是一個極具魅力的優(yōu)化問題,吸引著全世界無數(shù)的科學(xué)家、工程師和管理者為之探索。,構(gòu)造運(yùn)算簡單、尋優(yōu)性能優(yōu)異的啟發(fā)式算法,不僅對于配送系統(tǒng)而且對于許多可轉(zhuǎn)化為車輛路徑問題求解的組合優(yōu)化問題都具有十分重要的意義。1VRP模型的假設(shè)及MG公司VRP模型的建立VRP模型最早是由Dantzig和Ramser提出的,目前已成為運(yùn)籌學(xué)和組合優(yōu)化領(lǐng)域的前沿與熱點(diǎn)問題。該問題的研究目標(biāo)是:對一系列顧客需求點(diǎn)設(shè)計適當(dāng)?shù)穆肪€,使車輛有序地通過它們,在滿足一定的約束條件(如貨物需求量、發(fā)送量、交發(fā)貨時間、車輛容量限制、行使里程限制、時間限制等)下,達(dá)到一定

3、的優(yōu)化目標(biāo)。1.1模型的假設(shè)和考慮因素(1)模型的假設(shè)考慮VRP模型問題時,需做如下假設(shè):在一個城市中有N個客戶,每個客戶的位置坐標(biāo)和貨物需求已知,車輛的負(fù)載能力一定,但數(shù)量尚未確定,VRP模型是對車輛(每輛車一條路徑,開始和終止都在起始點(diǎn))所要訪問的客戶進(jìn)行排序,使所有客戶都滿足要求,而且總旅行成本最小。(2)模型應(yīng)考慮的因素建立VRP模型前,要對實(shí)際問題進(jìn)行研究,需要考慮以下幾個方面的問題:1)倉庫。倉庫的技術(shù),每級倉庫的數(shù)量、地點(diǎn)和規(guī)模;2)車輛。車輛的型號和數(shù)量,每種車的容積和運(yùn)作費(fèi)用,出發(fā)時間和返回時間,司機(jī)休息時間,最大的里程和時間限制;3)時間窗。由于各處的工作時間不同,需要各個

4、地點(diǎn)協(xié)調(diào);4)顧客。顧客需求,軟硬時間窗,裝載或卸載,地理位置,分離需求,優(yōu)先等級;5)道路信息。車流密度,道路交通費(fèi)用,距離或時間屬性;收稿日期:2004-09-02作者簡介:卜心怡(1961-)女,上海人,副教授,管理科學(xué)與工程.杭州電子科技大學(xué)學(xué)報2005年926)貨物信息。貨物的種類多少,兼容性,貨物的保鮮;7)運(yùn)輸規(guī)章。工人每天的工作時間,車輛的周期維護(hù)。1.2MG公司的背景與VRP模型的建立(1)MG公司的背景MG公司是一家模具鋼生產(chǎn)企業(yè),隨著業(yè)務(wù)的發(fā)展,MG公司決定在業(yè)務(wù)最多增長最快的蘇州設(shè)立一個配送中心,配送中心的任務(wù)是接受來自蘇州及附近城市客戶的訂單要求,將之發(fā)回總部處理,同

5、時接受從總部發(fā)來的貨物及指令,分配車輛將貨物及時地送往目的地。為了方便建立模型,在此模型中顧客的時間窗問題、道路信息問題和運(yùn)輸規(guī)章問題也可忽略。(2)建立MG公司的VRP模型為了敘述方便,引入下面的符號:1)客戶集合,P=i,i=0,1,n,且i=0指起始點(diǎn);2)車輛集合,M=k,k=1,m,m是一個待決定的決策變量;3)客戶i的需求量q,iV(i=0時,q=0);4)客戶i到客戶j的距離C,Ci0=0,C0j=0,iP/0,Cij,i5)每輛車的能力(每輛車的載重重量相同),Qmax 如上假設(shè),可建立VRP模型如下:minmminijkikPPyjk=k=1ni=1n1,i=1,2,nm,i

6、=0qiyikQkk=1,mxtjk=xjik=yjkj=1j=1n(i=1,n)(k=1,m)0,1yik,0,1xijki,j=0,n;(k=1,m)其中xijk和yki為變量,定義為:yik=1,顧客i的任務(wù)由車輛K完成yik0,其他xijk=1,車輛訪問顧客i之后馬上行駛至顧客jxijk=0,其他2求解VRP模型的算法與數(shù)據(jù)匯總2.1節(jié)約算法為了制定VRP模型中的分配式配送優(yōu)化方案,模型主要運(yùn)用的方法是啟發(fā)式算法中的節(jié)約算法(也叫里程節(jié)約法)。由模型的提示所得,節(jié)約算法制訂出的方案除了使配送總tkm最小之外,還應(yīng)該滿足以下條件:(1)能滿足所有用戶的供貨需求;(2)不使任何一輛超載;(

7、3)每車輛每天的總行使里程不超過規(guī)定的上限;(4)方案能滿足所有到貨時間要求。2.2數(shù)據(jù)的匯總與歸類經(jīng)過前期的數(shù)據(jù)整理后,將MG公司去年(2003年)在蘇州這一地區(qū)的整體銷售量進(jìn)行了統(tǒng)計分析,在對第1期卜心怡等:物流配送路線模型優(yōu)化及應(yīng)用93大約100多家客戶通過排列選優(yōu)、綜合評定選出10家大客戶,現(xiàn)在將有關(guān)數(shù)據(jù)下列表中列示,其中表1是配送中心C0與10家客戶Pj(j=1,10)間的距離及客戶對貨物的需求量Q,表2是10家客戶相互間的距離:表1配送中心與客戶之間的距離(km)以及運(yùn)送的貨物重量(kg)C0Q3.5133193105358412525306123327.5334253001717

8、911.5273P1P2P3P4P5P6P7P8P9P10表2各個客戶之間的距離(km)P1P2P3P4P5P6P7P8P9P101711232223151712102.517108.515.59418.53193181.52714.551316152412.52322121417P1P2P3P4P5P6P7P89P103初始方案、修正方案與最終方案的確定3.1方案的確定采用節(jié)約算法,利用表1,2中的數(shù)據(jù),可以得到以下方案。(1)初始方案:對每個客戶分別單獨(dú)派車送貨,配送線路10條。配送距離:S0=2doj=129.5×2=259(km),配送車輛:1t×10。i=110(

9、2)修正方案1:按節(jié)約里程Cij由大到小的順序,連接P5和P8,P5和P10,得到配送線路8條,配送距離:S1=S0-S5,10-S5,8=259-34-38=187(km)裝車量:qA=q5+q8+q10=306+300+273=879(kg)=0.879(t);配送車輛:1t×8。(3)修正方案2:再繼續(xù)按Sij由大到小排出S2,8、S2,5、S2,10、S6,10、S8,10、S8,9、S9,10,其中最大的是S2,8=32.5(km),此時P8已經(jīng)屬于線路A,若將P2并入線路A中,則車輛會超載,其它的線路其相應(yīng)的用戶也都已經(jīng)包含在線路A中,若加入也將超載,故都不予以考慮。在剩

10、余的Sij中,最大的是S6,9=24(km),連接P6和P9形成一個新的線路B,得修正方案2,配送線路:7條;配送距離:S2=S1-S6,9=187-24=163(km)裝車量:qB=q6+q9=332+179=511(kg)=0.511(T);配送車輛:1y×7。同理還可以得到修正方案3、修正方案4和修正方案5,限于篇幅這里略去。(7)最終方案:在剩下的Sij中S2,3、S2,4、S3,10、S6,7、S1,4、S1,8、S1,2、S1,9、S4,5、S1,6,由于與其相對應(yīng)的用戶已包含在已完成的線路里,故不予考慮,把S1,7對應(yīng)的P7點(diǎn)并入到線路C中,則qC=qC+q7=616+

11、334=950(kg)=0.95(t),S6=S5-S1,7=130.5-2=128.5(km),得到最終方案。杭州電子科技大學(xué)學(xué)報2005年943條配送線路分別為:配送線路AP0P8P5P10P0使用一輛1t的車;配送線路BP0P2P9P6P0使用一輛1t的車;配送線路CP0P7P1P3P4P0使用一輛1t的車。4結(jié)束語本文通過啟發(fā)式方法中的節(jié)約算法對一個配送網(wǎng)絡(luò)進(jìn)行了細(xì)致的優(yōu)化。在這個模型中雖然只有10家客戶,總體規(guī)模比較小,但通過信息技術(shù),它也能處理較多客戶的需求,而且效率很高。在這個模型中,距離成本是所有因素成本中最高的,縮短運(yùn)送路程就能降低成本;其次它的勞動消耗最低,由于路程縮短則油

12、耗、司機(jī)人數(shù)及司機(jī)工作時間也隨之降低了。值得注意的是,無論是企業(yè)的物流管理建設(shè)和發(fā)展,還是物流配送模型的實(shí)現(xiàn)和改進(jìn),企業(yè)已有的舊體系長期的磨合過程。而與此同時,強(qiáng)的生命力和競爭力。參考文獻(xiàn)1李延輝,馬士華.基于時間約束的配送系統(tǒng)模型及一種啟發(fā)式算法J.系統(tǒng)工程,2003,7(3):4-7.2李軍.物流配送車輛優(yōu)化調(diào)度理論與方法M.北京:中國物資出版社,2001.87-94.3張濤,張鑰杰,王夢光.不確定車輛數(shù)的車輛路徑問題模型和混合算法J.系統(tǒng)工程理論方法應(yīng)用,2002,6(5):21-24.4張麗萍,柴躍廷.車輛路徑問題的改進(jìn)遺傳算法J.系統(tǒng)工程理論方法應(yīng)用,2002,6(8):79-84.5JiShouwen,WangRongben.NeuralNetworkApproachforOptimalTransportPathofModule-unitedFlexibleManufacturingSystemC.Beijing:MachineEngineeringPress,2000.392-394.TheLogisticsbasedonHeuristicAlgorithmProvidesandDeliversRouteM