鐵路行包配裝算法研究與實現

1、    鐵路行包配裝算法研究與實現            作者：李宏權 楊偉鋒 陳莉時間：2010-2-2 9:39:00                     論文關鍵詞：鐵路車站  行包  裝配  編程實

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

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

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

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

6、一定許可范圍內進行調整。2  行包配裝問題的數學模型 令待運行包集合為X，車站發(fā)車車次集合T。二者的映射定義為：X T                                          

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

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

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

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

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

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

13、60; 編程實現 鐵路各個客運車站分布距離相對比廣泛，操作人員的水平參差不齊，這就要求軟件的可靠性和簡單易操作性必須要強?！拌F路行包管理系統”開發(fā)工具采用的是Delphi 7.0，數據庫采用的是Microsoft公司的SQL Server 2000。3.1  數據庫設計 在行包配裝算法中主要用到車次信息、停靠站信息、行包信息和行包種類優(yōu)先級信息等。車次和車次?？空臼莾蓚€基礎數據信息，這兩個表的字段定義如表2 和表3所示。是行包配裝的重要依據。表2  CCB車次信息表字段名類型中文說明TrainNumberVarchar(10)車次StartStationVarchar(16

14、)始發(fā)站ArriveStationVarchar(16)終到站ArriveTimedatetime到站時間StartTimedatetime發(fā)車時間UseTimeInt運行時間DistanceInt里程WeightInt載重重量CapabilityFloat車廂容積表3  TKZB?？空拘畔⒈碜侄蚊愋椭形恼f明TrainNumberVarchar(10)車次StationNameVarchar(16)站名StationSerielInt站次ArriveTimedatetime到站時間StartTimedatetime發(fā)車時間RunTimeInt運行時間RunDayInt運行天數Dis

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

16、靠站表（TKZB）中添加了一個中轉站標志（CrossL）字段，有了此項將大大降低程序的復雜度和提高函數的處理速度。部分程序代碼如下：CreatTempTable(#TKZB_T);  / 創(chuàng)建?？空九R時表CreatTempTable(#XBXX_T);  / 創(chuàng)建行包信息臨時表 AdoQuery1.sql.clear;         AdoQuery1.add(insert into #TKZB_T (select * from TKZB where TrainNumber =”當前車次”);

17、         AdoQuery1.ExeSql;   / 將滿足( Di Î Si )條件的到站添加到?？空九R時表中CalculateMinDis (當前車次);   / 將滿足(DiÏS直達 && min D (Di, Ti)條件的到站添加到停靠站臨時表中 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;       / 將滿足到站條件的行包添加到行包信息臨時表中3.2.2  計算備裝行包的max并排序 從目標函數公式(8)知，在計算max時將用到行包類別、貨物存放時間、到站里程和保價金額。其中貨物存放時間可根據制票時間求得。部分程序代碼如下：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進行排序3.2.3  根據約束條件剔除多出的行包 約束條件公式(4)是在生成裝成單時必須要考慮的項。目前在一些站由于每一個行包的體積不能準確給出，所以