組合運輸的優(yōu)化調度

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