- 相關(guān)推薦
鐵路行包配裝算法研究與實(shí)現(xiàn)
論文關(guān)鍵詞:鐵路車站 行包 裝配 編程實(shí)現(xiàn)
論文摘要:行包裝配是鐵路行包的重難點(diǎn)之一,在鐵路行包中出現(xiàn)的大部分問題均是由行包裝配不當(dāng)引起的。影響行包裝配的因素較多,通過對(duì)鐵路行包裝配的流程和影響行包裝配的主要因素進(jìn)行分析,建立了鐵路車站行包裝配問題的條件約束模型,提出鐵路行包裝配的目標(biāo)函數(shù),最后給出了鐵路行包裝配問題的編程實(shí)現(xiàn)方法。
鐵路行李包裹運(yùn)輸(以下簡(jiǎn)稱行包運(yùn)輸)是利用鐵路客運(yùn)設(shè)施,以隨掛旅客列車的行李車為載體的一種運(yùn)輸形式[1],其業(yè)務(wù)流程如圖1所示。近年來,隨著行包運(yùn)輸業(yè)務(wù)量的增長(zhǎng),大部分車站在承運(yùn)、交付、中轉(zhuǎn)和綜合報(bào)表打印等都實(shí)現(xiàn)了的自動(dòng)化管理。但是,在整個(gè)業(yè)務(wù)流程中的裝車單生成部分,現(xiàn)如今依然采用人工或半人工的方式進(jìn)行處理。由于與“裝車”相關(guān)的因素較多,所以大多的鐵路行包管理系統(tǒng)對(duì)此采取回避的辦法。如今,在行包運(yùn)輸中出現(xiàn)的大部分問題如貨物漏裝、錯(cuò)裝、中轉(zhuǎn)不暢、快件不快等問題均是由行包裝配不當(dāng)引起的[2]。為此,解決好行包配裝問題,優(yōu)化運(yùn)載設(shè)備的利用率,降低運(yùn)輸是一個(gè)非常有價(jià)值的研究課題。本文從行包管理軟件編程的實(shí)際出發(fā),提出了一種優(yōu)化的行包配裝算法,并給出了實(shí)現(xiàn)方法。
1 行包配裝問題分析
行包裝配主要是指合理制定待裝行包的裝配計(jì)劃。在現(xiàn)有運(yùn)能一定的條件下,根據(jù)行包運(yùn)達(dá)的要求,通過計(jì)算機(jī)科學(xué)的輔助決策,使行李車的利用效率最大[3],最大可能的減少和避免裝車錯(cuò)誤。鐵路車站行包配裝歸屬背包問題,但又與普通的背包問題有一定的不同。普通的背包問題是一對(duì)多的關(guān)系,而對(duì)于本問題的映射是多對(duì)多的關(guān)系,約束條件需要考慮客運(yùn)車次、行包到站、運(yùn)到期限、保價(jià)金額、貨物優(yōu)先級(jí)和車次的運(yùn)量、容積、沿途站裝卸作業(yè)能力等因素,行包配裝單的生成流程如圖2所示。鐵路行包裝配問題在學(xué)術(shù)上屬于復(fù)雜約束條件的組合優(yōu)化間題。從圖2可以得出鐵路行包配裝可分解為三步。
Step 1:根據(jù)車次和行包到站生成待裝車的行包集
行包的到站與車次的?空局g有兩種情況,一是貨物的到站屬于當(dāng)前車次的?空,此行包直接加入到備裝貨物集;二是貨物到站不在本次車的?空局校譄o直達(dá)車,經(jīng)計(jì)算裝此趟車進(jìn)行中轉(zhuǎn)的距離最短,則此到站的行包加入到備裝貨物集中。
Step 2:根據(jù)行包運(yùn)達(dá)要求,生成當(dāng)前車次的裝車單
第一步生成的是應(yīng)裝車的貨物清單,目前鐵路行包運(yùn)輸還達(dá)不到應(yīng)運(yùn)即運(yùn)的程度,因此還應(yīng)根據(jù)行包運(yùn)達(dá)的要求,通過計(jì)算機(jī)科學(xué)的輔助決策,使行李車的利用效率最大,最大可能的減少和避免裝車錯(cuò)誤[8]。裝車單生成的約束條件主要有重量和體積等方面。
Step 3: 人工調(diào)整確認(rèn)裝車單
計(jì)算機(jī)輔助生成的裝裝配計(jì)劃應(yīng)基本達(dá)到了最佳優(yōu)化裝車方案,但由于車站運(yùn)輸?shù)哪承┡R時(shí)特殊要求,車站行李員可對(duì)裝車單在一定許可范圍內(nèi)進(jìn)行調(diào)整。
2 行包配裝問題的模型令待運(yùn)行包集合為X,車站發(fā)車車次集合T。二者的映射定義為:
ƒ:X → T (1)
現(xiàn)在要為每一趟車進(jìn)行配裝,生成每一車次的裝車單:x ∈ X。為了求解x,首先要確定映射關(guān)系ƒ。由公式(1)可以看出,即使確定了ƒ,也很難最終求解x,如果能求出T中一個(gè)車次的結(jié)果,則其他車次依此類推,便可求出全部解。由此將公式(1)簡(jiǎn)化為:
ƒ(x) →Ti (1 £ i £ m,共有m趟車) (2)
令Ti車次?空镜募嫌肧i(1 £ i £ m)表示,承運(yùn)站直達(dá)站集合S直達(dá) = {S1 ∩ S2 ∩ … ∩ Sm}。貨物停靠站集合用D = {D1, D2, … , Dn}表示。
2.1 條件約束模型
2.1.1 行包到站約束條件
。1)行包到站為Ti次車的?空,即:Di ÎSi 。
。2)行包到站無直達(dá)車(DiÏS直達(dá)),但是裝此車次中轉(zhuǎn)貨物運(yùn)送距離最短。
因此行包到站約束條件公式:
(Di ÎSi) || (DiÏS直達(dá) && min D (Di, Ti)) (3)
式中min D (Di, Ti)表示貨物裝載Ti次車運(yùn)送距離最短。
2.1.2 行包車載重約束條件k=1,2,… (4)
式中xij∈{0,1}為第i車站,第j件貨物的裝載狀態(tài),gij為第i車站,第j件貨物的的重量,G裝為車輛已裝載重量,G車為車輛的規(guī)定載重量。
2.1.3 行包運(yùn)輸車容積約束條件k=1,2,… (5)
式中Vij為第i站上第j件行包的體積,V裝為車輛已裝載容積,V車為行李車的容積;
2.1.4 行包運(yùn)到期限約束條件(6)
式中 為第i站上第j件行包的運(yùn)到期限; 為第i站上第j件行包在該站已存放的時(shí)間, 為該列車從第i站到第m站所需運(yùn)行時(shí)間,第k站為該行包卸車站。
2.1.5 ?空狙b卸能力約束條件k=1,2,… (7)
式中 為第i站的行包作業(yè)裝卸效率; 為運(yùn)輸設(shè)備在第i站的停站時(shí)間。目前車站的裝卸能力基本上可以滿足要求,此約束條件在實(shí)際處理時(shí)做為參考。
2.2 貨物配裝目標(biāo)函數(shù)由于運(yùn)力有限,經(jīng)常不能一次把所有的行包運(yùn)完,這樣就需要找到最大或較大的裝載效益值,裝載效益用maxB來表示。影響maxB的因素按照權(quán)重值由大到小依次為行包種類的優(yōu)先級(jí)、貨物的存放時(shí)間、到站距離和保價(jià)金額。裝載效益目標(biāo)函數(shù)如公式(8)所示。
maxB= (8)
公式(8)中,rij表示貨物的優(yōu)先級(jí)權(quán)重,不同種類行包的優(yōu)先級(jí)如表1所示,表1中的rij值在使用時(shí)可根據(jù)具體情況進(jìn)行等比浮動(dòng); (≥1)表示貨物的存放時(shí)間;dij表示行包到站里程;mij表示行包保價(jià)金額。行包的保價(jià)金額是行包價(jià)值的重要體現(xiàn)之一,在其他條件相同的情況下,可以把保價(jià)作為是否裝車的衡量標(biāo)準(zhǔn)。這樣可以做到行包配裝的進(jìn)一步公平,同時(shí)也可以促進(jìn)保價(jià)收入。公式(8)中的四種權(quán)重在具體使用時(shí)可根據(jù)要求不同而作相應(yīng)的比例浮動(dòng)。
表1 行包分類優(yōu)先級(jí)
3 編程實(shí)現(xiàn)鐵路各個(gè)客運(yùn)車站分布距離相對(duì)比廣泛,操作人員的水平參差不齊,這就要求軟件的可靠性和簡(jiǎn)單易操作性必須要強(qiáng)!拌F路行包系統(tǒng)”開發(fā)工具采用的是Delphi 7.0,數(shù)據(jù)庫采用的是Microsoft公司的SQL Server 2000。
3.1 數(shù)據(jù)庫設(shè)計(jì)在行包配裝算法中主要用到車次信息、停靠站信息、行包信息和行包種類優(yōu)先級(jí)信息等。車次和車次?空臼莾蓚(gè)基礎(chǔ)數(shù)據(jù)信息,這兩個(gè)表的字段定義如表2 和表3所示。是行包配裝的重要依據(jù)。
表2 CCB—車次信息表
表3 TKZB—?空拘畔⒈
表2 和表3的數(shù)據(jù)可以從鐵路管理信息系統(tǒng)(TMIS)的客運(yùn)制票數(shù)據(jù)庫服務(wù)器中導(dǎo)出,鐵路局下面的每個(gè)車站直接導(dǎo)入使用。行包信息表的字段定義如表4 所示。行包信息表中包括始發(fā)貨物和中轉(zhuǎn)貨物。
表4:XBXX—行包信息表
3.2 關(guān)鍵程序設(shè)計(jì)行包配裝的目的是從所有的行包X中挑選出要裝車的行包x;谇懊婺P头治觯绦蛟O(shè)計(jì)將根據(jù)行包配裝的約束條件,采取逐步剔除不符合裝車條件的行包,生成最終裝車單,具體的程序設(shè)計(jì)流程如圖3所示。
3.2.1 根據(jù)到站選擇裝車行包
由約束條件公式(3)可知,滿足到站裝車的條件有兩種,一是(Di ÎSi);二是(DiÏS直達(dá) && min D (Di, Ti));第二種情況計(jì)算貨物裝載車次到站最短距離(CalculateMinDis)函數(shù)的實(shí)現(xiàn)相對(duì)復(fù)雜一些,但此函數(shù)是屬于圖論中求兩點(diǎn)之間最短路徑的問題。為了簡(jiǎn)化此函數(shù)的算法,在停靠站表(TKZB)中添加了一個(gè)中轉(zhuǎn)站標(biāo)志(CrossL)字段,有了此項(xiàng)將大大降低程序的復(fù)雜度和提高函數(shù)的處理速度。部分程序代碼如下:
CreatTempTable(#TKZB_T); // 創(chuàng)建?空九R時(shí)表
CreatTempTable(#XBXX_T); // 創(chuàng)建行包信息臨時(shí)表
AdoQuery1.sql.clear;
AdoQuery1.add(‘insert into #TKZB_T (select * from TKZB where TrainNumber =”當(dāng)前車次”)’);
AdoQuery1.ExeSql; // 將滿足( Di Î Si )條件的到站添加到?空九R時(shí)表中
CalculateMinDis (‘當(dāng)前車次’); // 將滿足(DiÏS直達(dá) && min D (Di, Ti))條件的到站添加到?空九R時(shí)表中 AdoQuery1.sql.close;
AdoQuery1.sql.clear;
AdoQuery1.add (‘insert into #XBXX_T (select XBXX.* from XBXX,#TKZB_T where #TKZB_T.StationName = XBXX.ArriveStation)’);
AdoQuery1.ExeSql; // 將滿足到站條件的行包添加到行包信息臨時(shí)表中
3.2.2 計(jì)算備裝行包的maxB并排序
從目標(biāo)函數(shù)公式(8)知,在計(jì)算maxB時(shí)將用到行包類別、貨物存放時(shí)間、到站里程和保價(jià)金額。其中貨物存放時(shí)間可根據(jù)制票時(shí)間求得。部分程序代碼如下:
AdoQuery1.sql.close;
AdoQuery1.sql.clear;
AdoQuery1.add (‘update #XBXX_T set maxb =
PackageType* (now- TicketTime)+
Distance/200+ InsureMoney/500’);
AdoQuery1.ExeSql; // maxB
AdoQuery1.sql.close;
AdoQuery1.sql.clear;
AdoQuery1.add (‘select * from #XBXX_T order by maxb’);
AdoQuery1.Open; // 按maxB進(jìn)行排序
3.2.3 根據(jù)約束條件剔除多出的行包約束條件公式(4)是在生成裝成單時(shí)必須要考慮的項(xiàng)。目前在一些站由于每一個(gè)行包的體積不能準(zhǔn)確給出,所以約束條件公式(5)這一項(xiàng)在實(shí)際編程時(shí)可根據(jù)實(shí)際的體積數(shù)據(jù)進(jìn)行處理,主要是作為參考。?空狙b卸能力約束,如公式(7),此約束條件若知道了每一個(gè)?空镜 和 ,則具體的編程實(shí)現(xiàn)并不復(fù)雜,單位時(shí)間裝卸能力和裝卸時(shí)間的值可通過系統(tǒng)參數(shù)輸入界面人工維護(hù)進(jìn)去。
4 結(jié)束語本配裝算法對(duì)每一批行包是否裝車的進(jìn)行了科學(xué)的量化,避免了人為處理的隨意性,算法程序的可實(shí)現(xiàn)性大大增強(qiáng)。此算法在實(shí)際的使用過程中,可根據(jù)各個(gè)車站的實(shí)際來調(diào)整maxB的各個(gè)條件權(quán)重值來取得最佳的裝車效果。裝車的約束條件可根據(jù)不同的車站而有選擇性地進(jìn)行處理。本文是作者在開發(fā)實(shí)踐經(jīng)驗(yàn)的基礎(chǔ)上進(jìn)行的歸納。
參考文獻(xiàn)
1 潘俊杰,王一新.鐵路旅客列車行李車配裝問題的遺傳算法研究[J].蘭州:甘肅科技,2004.6
2 孫遠(yuǎn)運(yùn).TMIS總體架構(gòu)設(shè)計(jì)研究[J].北京:鐵路應(yīng)用,2005.7
3 賀振歡,劉軍.鐵路車站行包配裝計(jì)算機(jī)輔助決策系統(tǒng)的研究[J].北京:北京大學(xué)學(xué)報(bào),2000.6
4 雷定獻(xiàn),陳德良.平衡裝載問題的優(yōu)化模型和算法[J].天津:系統(tǒng)工程學(xué)報(bào),2004.6
5 吳清一.物流[M].北京:中國(guó)物資出版社,2003
6 譚顯倫,阮永良.一種新的背包加強(qiáng)算法[J].合肥:電腦知識(shí)與技術(shù),2004.10
7 瀏小群,馬士華,徐天亮.裝載能力有限下多品種貨物配裝的容重比平衡法[J].上海:工程與管理,2004.3
8 中華人民共和國(guó)鐵道部.鐵路旅客管理規(guī)則[S].北京:中國(guó)鐵道出版社,1998
【鐵路行包配裝算法研究與實(shí)現(xiàn)】相關(guān)文章:
基于價(jià)值網(wǎng)理論的鐵路多元經(jīng)營(yíng)物流企業(yè)經(jīng)營(yíng)模式研究06-04
數(shù)據(jù)關(guān)聯(lián)算法綜述及其性能評(píng)估05-05
都市頻道制作網(wǎng)的設(shè)計(jì)與實(shí)現(xiàn)05-29
基于minigui的網(wǎng)真機(jī)界面的實(shí)現(xiàn)08-05
城市旅游網(wǎng)站的設(shè)計(jì)與實(shí)現(xiàn)論文(精選6篇)05-07
企業(yè)知識(shí)管理的實(shí)現(xiàn)技術(shù)和工具的電商論文05-02
企業(yè)法律風(fēng)險(xiǎn)防范體系建立的原因及實(shí)現(xiàn)路徑08-06
如何通過內(nèi)部控制實(shí)現(xiàn)企業(yè)持續(xù)性發(fā)展05-21