鐵路行包配裝算法研究與實(shí)現(xiàn)

1、    鐵路行包配裝算法研究與實(shí)現(xiàn)            作者：李宏權(quán) 楊偉鋒 陳莉時(shí)間：2010-2-2 9:39:00                     論文關(guān)鍵詞：鐵路車(chē)站  行包  裝配  編程實(shí)

2、現(xiàn)論文摘要：行包裝配是鐵路行包管理的重難點(diǎn)之一，在鐵路行包運(yùn)輸中出現(xiàn)的大部分問(wèn)題均是由行包裝配不當(dāng)引起的。影響行包裝配的因素較多，通過(guò)對(duì)鐵路行包裝配的流程和影響行包裝配的主要因素進(jìn)行分析，建立了鐵路車(chē)站行包裝配問(wèn)題的條件約束模型，提出鐵路行包裝配的目標(biāo)函數(shù)，最后給出了鐵路行包裝配問(wèn)題的編程實(shí)現(xiàn)方法。鐵路行李包裹運(yùn)輸（以下簡(jiǎn)稱行包運(yùn)輸）是利用鐵路客運(yùn)設(shè)施，以隨掛旅客列車(chē)的行李車(chē)為載體的一種運(yùn)輸形式1，其業(yè)務(wù)流程如圖1所示。近年來(lái)，隨著行包運(yùn)輸業(yè)務(wù)量的增長(zhǎng)，大部分車(chē)站在承運(yùn)、交付、中轉(zhuǎn)和綜合統(tǒng)計(jì)報(bào)表打印等都實(shí)現(xiàn)了計(jì)算機(jī)的自動(dòng)化管理。但是，在整個(gè)業(yè)務(wù)流程中的裝車(chē)單生成部分，現(xiàn)如今依然采用人工或半人工

3、的方式進(jìn)行處理。由于與“裝車(chē)”相關(guān)的因素較多，所以大多的鐵路行包管理系統(tǒng)對(duì)此采取回避的辦法。如今，在行包運(yùn)輸中出現(xiàn)的大部分問(wèn)題如貨物漏裝、錯(cuò)裝、中轉(zhuǎn)不暢、快件不快等問(wèn)題均是由行包裝配不當(dāng)引起的2。為此，解決好行包配裝問(wèn)題，優(yōu)化運(yùn)載設(shè)備的利用率，降低運(yùn)輸成本是一個(gè)非常有價(jià)值的研究課題。本文從行包管理軟件編程的實(shí)際出發(fā)，提出了一種優(yōu)化的行包配裝算法，并給出了實(shí)現(xiàn)方法。1  行包配裝問(wèn)題分析               行包裝配主要是指合理制定待裝行包

4、的裝配計(jì)劃。在現(xiàn)有運(yùn)能一定的條件下，根據(jù)行包運(yùn)達(dá)的要求，通過(guò)計(jì)算機(jī)科學(xué)的輔助決策，使行李車(chē)的利用效率最大3，最大可能的減少和避免裝車(chē)錯(cuò)誤。鐵路車(chē)站行包配裝歸屬背包問(wèn)題，但又與普通的背包問(wèn)題有一定的不同。普通的背包問(wèn)題是一對(duì)多的關(guān)系，而對(duì)于本問(wèn)題的映射是多對(duì)多的關(guān)系，約束條件需要考慮客運(yùn)車(chē)次、行包到站、運(yùn)到期限、保價(jià)金額、貨物優(yōu)先級(jí)和車(chē)次的運(yùn)量、容積、沿途站裝卸作業(yè)能力等因素，行包配裝單的生成流程如圖2所示。鐵路行包裝配問(wèn)題在學(xué)術(shù)上屬于復(fù)雜約束條件的組合優(yōu)化間題。從圖2可以得出鐵路行包配裝可分解為三步。Step 1：根據(jù)車(chē)次和行包到站生成待裝車(chē)的行包集行包的到站與車(chē)次的停靠站之間有兩種情況，一是

5、貨物的到站屬于當(dāng)前車(chē)次的?？空荆诵邪苯蛹尤氲絺溲b貨物集；二是貨物到站不在本次車(chē)的停靠站中，但又無(wú)直達(dá)車(chē)，經(jīng)計(jì)算裝此趟車(chē)進(jìn)行中轉(zhuǎn)的距離最短，則此到站的行包加入到備裝貨物集中。Step 2：根據(jù)行包運(yùn)達(dá)要求，生成當(dāng)前車(chē)次的裝車(chē)單第一步生成的是應(yīng)裝車(chē)的貨物清單，目前鐵路行包運(yùn)輸還達(dá)不到應(yīng)運(yùn)即運(yùn)的程度，因此還應(yīng)根據(jù)行包運(yùn)達(dá)的要求，通過(guò)計(jì)算機(jī)科學(xué)的輔助決策，使行李車(chē)的利用效率最大，最大可能的減少和避免裝車(chē)錯(cuò)誤8。裝車(chē)單生成的約束條件主要有重量和體積等方面。Step 3: 人工調(diào)整確認(rèn)裝車(chē)單計(jì)算機(jī)輔助生成的裝裝配計(jì)劃應(yīng)基本達(dá)到了最佳優(yōu)化裝車(chē)方案，但由于車(chē)站運(yùn)輸?shù)哪承┡R時(shí)特殊要求，車(chē)站行李員可對(duì)裝車(chē)單在

6、一定許可范圍內(nèi)進(jìn)行調(diào)整。2  行包配裝問(wèn)題的數(shù)學(xué)模型 令待運(yùn)行包集合為X，車(chē)站發(fā)車(chē)車(chē)次集合T。二者的映射定義為：X T                                          

7、;                (1)現(xiàn)在要為每一趟車(chē)進(jìn)行配裝，生成每一車(chē)次的裝車(chē)單：x X。為了求解x，首先要確定映射關(guān)系。由公式(1)可以看出，即使確定了，也很難最終求解x，如果能求出T中一個(gè)車(chē)次的結(jié)果，則其他車(chē)次依此類(lèi)推，便可求出全部解。由此將公式(1)簡(jiǎn)化為： (x) Ti  (1 £ i £ m，共有m趟車(chē))        &

8、#160;    (2)    令Ti車(chē)次停靠站的集合用Si（1 £ i £ m）表示，承運(yùn)站直達(dá)站集合S直達(dá) = S1 S2 Sm。貨物?？空炯嫌肈 = D1, D2, , Dn表示。2.1  條件約束模型 （1）行包到站為T(mén)i次車(chē)的?？空?，即：Di ÎSi 。（2）行包到站無(wú)直達(dá)車(chē)（DiÏS直達(dá)），但是裝此車(chē)次中轉(zhuǎn)貨物運(yùn)送距離最短。因此行包到站約束條件公式：(Di ÎSi) | (DiÏS直達(dá) && min D (Di, Ti) &#

9、160;                    (3)式中min D (Di, Ti)表示貨物裝載Ti次車(chē)運(yùn)送距離最短。         =1，2，           (4)式中xij0,1為第i車(chē)站，第j件貨物的裝載狀態(tài)，gij為第i車(chē)

10、站，第j件貨物的的重量，裝為車(chē)輛已裝載重量，G車(chē)為車(chē)輛的規(guī)定載重量。 =1，2，             (5)式中Vij為第站上第件行包的體積，V裝為車(chē)輛已裝載容積，V車(chē)為行李車(chē)的容積；         (6)式中 為第站上第件行包的運(yùn)到期限； 為第站上第件行包在該站已存放的時(shí)間， 為該列車(chē)從第站到第站所需運(yùn)行時(shí)間，第k站為該行包卸車(chē)站。     

11、;           =1，2，      (7)式中 為第站的行包作業(yè)裝卸效率； 為運(yùn)輸設(shè)備在第站的停站時(shí)間。目前車(chē)站的裝卸能力基本上可以滿足要求，此約束條件在實(shí)際處理時(shí)做為參考。2.2  貨物配裝目標(biāo)函數(shù) 由于運(yùn)力有限，經(jīng)常不能一次把所有的行包運(yùn)完，這樣就需要找到最大或較大的裝載效益值，裝載效益用max來(lái)表示。影響max的因素按照權(quán)重值由大到小依次為行包種類(lèi)的優(yōu)先級(jí)、貨物的存放時(shí)間、到站距離和保價(jià)金額。裝載效益目標(biāo)函數(shù)如公式(8)所示。max= (8

12、)公式(8)中，rij表示貨物的優(yōu)先級(jí)權(quán)重，不同種類(lèi)行包的優(yōu)先級(jí)如表1所示，表1中的rij值在使用時(shí)可根據(jù)具體情況進(jìn)行等比浮動(dòng)； （1）表示貨物的存放時(shí)間；dij表示行包到站里程；mij表示行包保價(jià)金額。行包的保價(jià)金額是行包價(jià)值的重要體現(xiàn)之一，在其他條件相同的情況下，可以把保價(jià)作為是否裝車(chē)的衡量標(biāo)準(zhǔn)。這樣可以做到行包配裝的進(jìn)一步公平，同時(shí)也可以促進(jìn)保價(jià)收入。公式(8)中的四種權(quán)重在具體使用時(shí)可根據(jù)要求不同而作相應(yīng)的比例浮動(dòng)。表1  行包分類(lèi)優(yōu)先級(jí)優(yōu)先級(jí)（rij）行包種類(lèi)名稱優(yōu)先級(jí)（rij）行包種類(lèi)名稱12搶險(xiǎn)救災(zāi)物資6滯留始發(fā)行李11急救藥品5當(dāng)日始發(fā)行李10誤運(yùn)行包<3

13、60; 編程實(shí)現(xiàn) 鐵路各個(gè)客運(yùn)車(chē)站分布距離相對(duì)比廣泛，操作人員的水平參差不齊，這就要求軟件的可靠性和簡(jiǎn)單易操作性必須要強(qiáng)?！拌F路行包管理系統(tǒng)”開(kāi)發(fā)工具采用的是Delphi 7.0，數(shù)據(jù)庫(kù)采用的是Microsoft公司的SQL Server 2000。3.1  數(shù)據(jù)庫(kù)設(shè)計(jì) 在行包配裝算法中主要用到車(chē)次信息、?？空拘畔ⅰ⑿邪畔⒑托邪N類(lèi)優(yōu)先級(jí)信息等。車(chē)次和車(chē)次?？空臼莾蓚€(gè)基礎(chǔ)數(shù)據(jù)信息，這兩個(gè)表的字段定義如表2 和表3所示。是行包配裝的重要依據(jù)。表2  CCB車(chē)次信息表字段名類(lèi)型中文說(shuō)明TrainNumberVarchar(10)車(chē)次StartStationVarchar(16

14、)始發(fā)站ArriveStationVarchar(16)終到站ArriveTimedatetime到站時(shí)間StartTimedatetime發(fā)車(chē)時(shí)間UseTimeInt運(yùn)行時(shí)間DistanceInt里程WeightInt載重重量CapabilityFloat車(chē)廂容積表3  TKZB?？空拘畔⒈碜侄蚊?lèi)型中文說(shuō)明TrainNumberVarchar(10)車(chē)次StationNameVarchar(16)站名StationSerielInt站次ArriveTimedatetime到站時(shí)間StartTimedatetime發(fā)車(chē)時(shí)間RunTimeInt運(yùn)行時(shí)間RunDayInt運(yùn)行天數(shù)Dis

15、tanceInt里程CrossLBoolean中轉(zhuǎn)站標(biāo)志表2 和表3的數(shù)據(jù)可以從鐵路管理信息系統(tǒng)（TMIS）的客運(yùn)制票數(shù)據(jù)庫(kù)服務(wù)器中導(dǎo)出，鐵路局下面的每個(gè)車(chē)站直接導(dǎo)入使用。行包信息表的字段定義如表4 所示。行包信息表中包括始發(fā)貨物和中轉(zhuǎn)貨物。表4：XBXX行包信息表由約束條件公式(3)可知，滿足到站裝車(chē)的條件有兩種，一是(Di ÎSi)；二是(DiÏS直達(dá) && min D (Di, Ti)；第二種情況計(jì)算貨物裝載車(chē)次到站最短距離（CalculateMinDis）函數(shù)的實(shí)現(xiàn)相對(duì)復(fù)雜一些，但此函數(shù)是屬于圖論中求兩點(diǎn)之間最短路徑的問(wèn)題。為了簡(jiǎn)化此函數(shù)的算法，在停

16、靠站表（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)前車(chē)次”);

17、         AdoQuery1.ExeSql;   / 將滿足( Di Î Si )條件的到站添加到?？空九R時(shí)表中CalculateMinDis (當(dāng)前車(chē)次);   / 將滿足(DiÏS直達(dá) && min D (Di, Ti)條件的到站添加到?？空九R時(shí)表中 AdoQuery1.sql.close;AdoQuery1.sql.clear;       

18、60; 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ì)算備裝行包的max并排序 從目標(biāo)函數(shù)公式(8)知，在計(jì)算max時(shí)將用到行包類(lèi)別、貨物存放時(shí)間、到站里程和保價(jià)金額。其中貨物存放時(shí)間可根據(jù)制票時(shí)間求得。部分程序代碼如下：AdoQue

19、ry1.sql.close;AdoQuery1.sql.clear;AdoQuery1.add (update #XBXX_T set maxb = PackageType* (now- TicketTime)+ Distance/200+ InsureMoney/500);AdoQuery1.ExeSql;               / maxAdoQuery1.sql.close;AdoQuery1.sql.clear;         AdoQuery1.add (select * from #XBXX_T order by maxb);AdoQuery1.Open;                / 按max進(jìn)行排序3.2.3  根據(jù)約束條件剔除多出的行包 約束條件公式(4)是在生成裝成單時(shí)必須要考慮的項(xiàng)。目前在一些站由于每一個(gè)行包的體積不能準(zhǔn)確給出，所以