2001年2月系統(tǒng)工程理論與實踐第2期文章編號:1000-6788(2001 )02-0117-05組合運輸?shù)膬?yōu)化調(diào)度李軍，郭強，劉建新(西南交通大學(xué)經(jīng)濟管理學(xué)院,四川成都610031)摘要:對多車場情況的非滿載的小貨運量運輸問題進行了分析.提出采用組合運輸方式可以提高車輛的使用效率,進而構(gòu)造了由分組和連接構(gòu)成的序列優(yōu)化啟發(fā)式算法,并用實例進行了驗證.關(guān)鍵詞:非滿載; 分組;連接;行駛線路中圖分類號: U116.2, 0221.1Optimal Scheduling onCombinatorial TransportationLI Jun, GUO Qiang, LIU Jian-xin(School of Economics and Management, Southwest Jiaotong University ,Chengdu 610031)Abstract In this paper, the vehicle-scheduling problem with non-full load at the caseof multiple depots is analyzed. The combinatorial transportation is presented in order toenhance the effectiveness of transportation utilizing a single vehicle. A sequentialheuristic algorithm is constructed, which consists of clustering and chaining. Lastly,the method is applied to a case study.Keywords non- full load; clustering; chaining ; vehicle routes1引言有多項貨運任務(wù),對每項任務(wù),要求從發(fā)貨點運送貨物到收貨點，已知某些任務(wù)的貨運量小于車輛容量的二分之一,這時如果每項任務(wù)安排-輛車,則車輛處于不滿載狀態(tài)，造成車輛利用率不高.因而可考慮幾項任務(wù)合起來用一輛車運輸(貨物可混裝或車輛有分割倉前提下),即實行組合運輸,-輛車在幾個發(fā)貨點裝貨,然后再到幾個收貨點卸貨-般來說,幾項任務(wù)的發(fā)貨點和(或)收貨點比較接近時,組合用一輛車運輸才比較有利,這樣的-些任務(wù)稱為一組任務(wù)，一輛車完成 . -組內(nèi)的所有任務(wù)后,在滿足總行駛里程約束的前提下,可再考慮完成其它組的任務(wù)，即組與組之間進行一定的連接、這樣大大提高了車輛的使用效率,使總發(fā)車數(shù)減少.問題可描述為:n項貨物運輸任務(wù),編號為...n,對任務(wù)i,其發(fā)貨點為u,收貨點為v,貨運量為g.共有m個車場可發(fā)出車輛.車輛容量為Q.存在一些任務(wù),有g(shù);SQ/2.2分組中國煤化工分組就是將位置比較靠近且貨運量之和不大于2.1分組模型:MYHCNMHG各任務(wù)點的位置接近程度,可用各點與它們的重心距離來反映[。對一個組,有發(fā)貨點重心和收貨點重心兩個指標(biāo).某一任務(wù)與-組的距離，應(yīng)為此任務(wù)的發(fā)貨點與所屬分組的發(fā)貨點重心距離和收貨點與所，收稿日期7資助項目:國家自然科學(xué)基金(79700019)118系統(tǒng)工程理論與實踐2001年2月屬分組的收貨點重心距離之和.設(shè)任務(wù)i的發(fā)貨點坐標(biāo)為(fa,fb,),收貨點坐標(biāo)為(sai,sb;).設(shè)組k的發(fā)貨點重心坐標(biāo)為(Fa,Jb,),收貨點重心坐標(biāo)為(san, sbn)定義分配變量如下:1任務(wù)i分配給組kXCki =0否則'minz=乙藝[fas- fa,)2+ (fb。- 16)°]”工n十22[(san- sa,)2 + (sbo- s),)9]1"zxu .> jgxe≤Q2r;=1 i= 1,.nxn=0 或2.2模型求解2.2.1 初始分組由于不同任務(wù)的發(fā)貨、收貨地點以及特性可能不同,合并在-起運輸時,裝卸車就具有-定的復(fù)雜性.-些任務(wù)雖然貨運量可組合在. -起,但組合運輸并不一定有利,因而分組也具有一定的復(fù)雜性、 為此,引入“人工容量”的概念,定義如下:Q;=Q.其中,β為系數(shù),且0<β<1.可設(shè)計一定的分組規(guī)則,根據(jù)人工容量對任務(wù)進行初始分組. β可通過人機進行交互式調(diào)整,這樣就可對不同任務(wù)的裝卸車復(fù)雜性給予-定考慮,并估計了分組時的復(fù)雜性,增大了組之間調(diào)整的彈性.2.2.2組的調(diào)整 .采用動態(tài)聚類分析方法進行組的調(diào)整.聚類時,以初始分組作為聚類分析的初始分類,以組的重心作為聚類中心，按最接近原則將各任務(wù)進行聚類，判斷分類是否合理的標(biāo)準(zhǔn),是當(dāng)前分類中各任務(wù)與它所屬分類中心的距離是否是最近距離.需要注意的是,在按最接近原則聚類時,必須檢查新的分類容量是否超過了車輛的實際容量.為了增加調(diào)整的彈性,初始分組是按人工容量得到的,而應(yīng)用聚類方法修改分類時,應(yīng)按實際容量進行.在進行組的調(diào)整時,可按下面步驟進行:1)以初始分組為初始分類;2)計算各類的發(fā)貨點重心與收貨點重心;3)計算各任務(wù)與各類的重心距離;4)檢查各距離,若不存在與其它類距離比與當(dāng)前自己所屬分類距離更近的任務(wù),則分類不變,得到最后分類,終止，否則,進行下一步;5)按最接近原則進行重新分類;6)計算各類的容量;7)若類容量在車輛實際容量限制內(nèi),則轉(zhuǎn)回到不則切出空昌明制的類中,將距離該類重心最中國煤化工遠的任務(wù)分給另-距它最近的類,回到6).若在此始分組,調(diào)整β的值,可值到不同的分組.MYHCNMHG3組內(nèi)線路安排3.1初始線路形成3.1.1單獨行驟樊?dāng)f點和收貨點的線路分別對發(fā)貨點和收貨點應(yīng)C-W節(jié)約算法求得各自的旅行商線路[2],然后再將哈密爾頓圈轉(zhuǎn)換成哈密.第2期組合運輸?shù)膬?yōu)化調(diào)度119爾頓路,即兩條有向線路.3.1.2發(fā)貨點線路與收貨點線路的連接由于分組是以各任務(wù)發(fā)貨點和(或)收貨點比較接近為基礎(chǔ)的,因此，安排線路時.考慮車輛首先行駛完全部發(fā)貨點后再駛向某一收貨點,直至駛完全部收貨點,目的是行駛的總距離最短、這樣行駛線路的所有方案構(gòu)成-棵有向樹形圖(圖1).設(shè)組內(nèi)共有m項任務(wù),S為組的入點,它可向所有發(fā)貨點u,ou..u.發(fā)車;由每一發(fā)貨點u;為起始點向下可分成兩枝,分枝結(jié)點即為行駛線路的發(fā)貨點結(jié)束點u。和un;由每-發(fā)貨點結(jié)束點向下可向所有收貨點v,,...V發(fā)車;每一收貨點起始點心向下又分成兩枝,結(jié)點為收貨點結(jié)束點vo,和Vr.在此采用動態(tài)規(guī)劃方法,將已得到的發(fā)貨點線路與收貨點線路進行連接.根據(jù)動態(tài)規(guī)劃原理,采用逆向遞推方法進行初始線路音一M安排[3].整個過程分成五個階段如下:階段1組的入點S 至發(fā)貨點起始點;s階段2發(fā)貨點起始 點至發(fā)貨點終止點;u階段3發(fā)貨點終止點至收貨點起始點;階段4收貨起始 點至收貨點終止點.以,\1m以階段的始點位置作為該階段的狀態(tài),它既是該階段某支路的起始點,又是前一階段某支路的終點，設(shè)階段pv好\的狀態(tài)為sp.d,(sp)為決策變量,表示階段p的狀態(tài)變量為sp時選擇的路徑,D。(sp)為相應(yīng)得允許決策集合. R。(sp，d,)表示在階段p的狀態(tài)sp時,采用策略dp時的階段收圖1樹形圖益,即相應(yīng)的路徑長度.設(shè)c(i,j)表示點i到點j的距離; L(i,j)表示以i為起始點,以j為終止點的旅行商線路的長度、各階段的狀態(tài)變量、允許決策集合和階段收益分別示于表1中.設(shè)fp(sp)為階段p的狀態(tài)最優(yōu)值,表示在階段p的狀態(tài)Sp到收貨點終止點的最短距離,此動態(tài)規(guī)劃的遞推方程可寫為fp(sp)= min [R,(sp,d,) + fp+l(sp+)]fs<(s)= 0f.(sn)即為所求的組內(nèi)線路長,由fi(s1)確定的線路即為所求的初始線路.表1狀態(tài)變量、允許決策集合和階段收益pDp(sp)Rp(sprdp) .第一階段s}(u;}第二階段({u;|u;為發(fā)貨點起始點}{u;|u;=uis，ur}L(u,aul)第三階段.({u;|uj為發(fā)貨點終止點}{v}c(uj,v)第四階段{vklve為收貨點起始點){v1 |v= VkerUh}L(ve+v)3.2組內(nèi)線路的優(yōu)化已安排的線路是基于先安排任務(wù)的發(fā)貨點,再中國煤化工考慮在發(fā)貨點間插入一些收貨點,是否會使總行駛里程減少,這里利用or交指TYHCNMH G_設(shè)某點從當(dāng)前位置中去掉的目標(biāo)函數(shù)減少值.為............定位時的目標(biāo)函數(shù)增加值為0x'.則當(dāng)0x>Oz'時，重新定位有利.這里正向定位時，發(fā)貨點只能在它的當(dāng)前位置與收貨點位置之間定位,收貨點可以在當(dāng)前位置之后的任一位置定位;反向定位時.發(fā)貨點可以在當(dāng)前位置之前的任一位置定位,收貨點只能在它的當(dāng)前位置與發(fā)貨點位置戽調(diào)數(shù)據(jù)這是因為一項任務(wù)的收貨點必須在其發(fā)貨點之后出現(xiàn).120系統(tǒng)工程理論與實踐2001年2月4組間線路的連接把組與組進行連接,即把子線路連接起來以合并成完整的車輛路線.這里把每-組任務(wù)作為一項“任務(wù)”,忽略內(nèi)部結(jié)構(gòu),僅考慮組內(nèi)線路的起點與終點.利用C-W算法原理進行組的連接,類似于旅行商問題中非對稱距離情況下的C-W算法[2].當(dāng)有多個車場可收發(fā)空車時,遵循“就近發(fā)車,就近收車”的原則,即對每-組任務(wù)而言,由距離它的起點最近的車場發(fā)車,完成任務(wù)后回到距它的終點最近的車場.設(shè)一組任務(wù)i的起點為si.終點為t,組內(nèi)線路長L..設(shè)有車場D.,D...D.可收發(fā)車,則連接子線路;和j時,比車輛單獨行駛線路i和j的費用的節(jié)約值為.s(i,j)= mincDp; + L;十minc,D, + mincp, + Lj + minc,p,'mincD;一L;一C一L;一minc,pe= minc,Dg + mincDp;一Cts計算所有連接的“節(jié)約"值,然后根據(jù)“節(jié)約”值的大小進行連接，若對收發(fā)車有特殊要求,則按要求收發(fā)車.5實例分析有一組貨運任務(wù),編號為1,2,3,4,5,6,各自的貨運量及相應(yīng)的發(fā)貨點和收貨點坐標(biāo)如表2所示.各任務(wù)用載重量10噸的車輛來完成.有三個車場,位置分別為D.(40,40),D2(20,40),D3(50.20).試安排車輛路線.表2各任務(wù)貨運量 及位置任務(wù)i1234貨運量(噸)5.22.51.81.50.5發(fā)貨點坐標(biāo)(10,40)(30,20)(50, 60)(60,40)(60,20)(40,20)收貨點坐標(biāo)(50,10)(20,50)(30,50)(50,40)(30 ,30)設(shè)β=0.85,則得到Qg=8.5(噸).得到初始分組如下:組一:任務(wù)1,任務(wù)2,任務(wù)6;組二:任務(wù)3,任務(wù)4.任務(wù)5.確定各組內(nèi)的初始線路如下:us→u4→us→Us→v→Vz利用or交換法優(yōu)化后,得到→V→U2→U2→llx→V8Us→us→Vs→tls→v→V3在組與組間連接后得到線路如下:D3→uls→us→U→us→v→U3中國煤化工，線路示于圖2中,其中實線為車輛線路,虛線連接表TYHCNMHG6討論初始分組是基于-定的規(guī)則進行的，由于問題結(jié)構(gòu).數(shù)據(jù)結(jié)構(gòu)的不同而具有隨機性,因此可設(shè)定不同的β值,得到多個分組,在進行組與組的連接時,同時考慮多個分組,從中選擇最好的連接.但要注意,含有相同任務(wù)的羯者數(shù)搪能連接.第2期組合運輸?shù)膬?yōu)化調(diào)度12170 [605040●D:30204qD:4s1070中國煤化工圖2MHCNMHG參考文獻:[1] L庫柏，U N勃哈特，LJ勒布朗，運籌學(xué)模型概論[M].魏國華,周仲良譯，上海:上?？茖W(xué)技術(shù)出版社,1987.[2] 郭耀煌,李軍，車輛優(yōu)化調(diào)度[M].成都:成都科技大學(xué)出版社,1994.[3] 郭耀煙紡麩孱學(xué)原理與方法[M].成都: 西南交通大學(xué)出版社,1994. .