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

1、鐵路行包配裝算法研究與實現(xiàn)     論文 關鍵詞：鐵路車站  行包  裝配  編程實現(xiàn)論文摘要：行包裝配是鐵路行包管理的重難點之一，在鐵路行包運輸中出現(xiàn)的大部分問題均是由行包裝配不當引起的。影響行包裝配的因素較多，通過對鐵路行包裝配的流程和影響行包裝配的主要因素進行分析，建立了鐵路車站行包裝配問題的條件約束模型，提出鐵路行包裝配的目標函數(shù)，最后給出了鐵路行包裝配問題的編程實現(xiàn)方法。鐵路行李包裹運輸（以下簡稱行包運輸）是利用鐵路客運設施，以隨掛旅客列車的行李車為載體的一種運輸形式1，其業(yè)務流程如圖1所示。近年來，隨著行包運輸業(yè)

2、務量的增長，大部分車站在承運、交付、中轉(zhuǎn)和綜合統(tǒng)計報表打印等都實現(xiàn)了 計算 機的自動化管理。但是，在整個業(yè)務流程中的裝車單生成部分，現(xiàn)如今依然采用人工或半人工的方式進行處理。由于與“裝車”相關的因素較多，所以大多的鐵路行包管理系統(tǒng)對此采取回避的辦法。如今，在行包運輸中出現(xiàn)的大部分問題如貨物漏裝、錯裝、中轉(zhuǎn)不暢、快件不快等問題均是由行包裝配不當引起的2。為此，解決好行包配裝問題，優(yōu)化運載設備的利用率，降低運輸成本是一個非常有價值的研究課題。本文從行包管理軟件編程的實際出發(fā)，提出了一種優(yōu)化的行包配裝算法，并給出了實現(xiàn)方法。1  行包配裝問題分析     行包裝配主要是

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

4、站之間有兩種情況，一是貨物的到站屬于當前車次的停靠站，此行包直接加入到備裝貨物集；二是貨物到站不在本次車的?？空局?，但又無直達車，經(jīng)計算裝此趟車進行中轉(zhuǎn)的距離最短，則此到站的行包加入到備裝貨物集中。Step 2：根據(jù)行包運達要求，生成當前車次的裝車單第一步生成的是應裝車的貨物清單，目前鐵路行包運輸還達不到應運即運的程度，因此還應根據(jù)行包運達的要求，通過計算機科學的輔助決策，使行李車的利用效率最大，最大可能的減少和避免裝車錯誤8。裝車單生成的約束條件主要有重量和體積等方面。Step 3: 人工調(diào)整確認裝車單計算機輔助生成的裝裝配計劃應基本達到了最佳優(yōu)化裝車方案，但由于車站運輸?shù)哪承┡R時特殊要求，

5、車站行李員可對裝車單在一定許可范圍內(nèi)進行調(diào)整。2  行包配裝問題的數(shù)學模型 令待運行包集合為X，車站發(fā)車車次集合T。二者的映射定義為：X T                                     

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

7、          (2)令Ti車次?？空镜募嫌肧i（1 £ i £ m）表示，承運站直達站集合S直達 = S1 S2 Sm。貨物?？空炯嫌肈 = D1, D2, , Dn表示。2.1  條件約束模型 2.1.1  行包到站約束條件 （1）行包到站為Ti次車的?？空荆矗篋i ÎSi 。（2）行包到站無直達車（DiÏS直達），但是裝此車次中轉(zhuǎn)貨物運送距離最短。因此行包到站約束條件公式：(Di ÎSi) | (DiÏS直達

8、&& min D (Di, Ti)                      (3)式中min D (Di, Ti)表示貨物裝載Ti次車運送距離最短。2.1.2  行包運輸車載重約束條件            =1，2，   

9、0;       (4)式中xij0,1為第i車站，第j件貨物的裝載狀態(tài)，gij為第i車站，第j件貨物的的重量，裝為車輛已裝載重量，G車為車輛的規(guī)定載重量。2.1.3  行包運輸車容積約束條件 =1，2，             (5)式中Vij為第站上第件行包的體積，V裝為車輛已裝載容積，V車為行李車的容積；2.1.4  行包運到期限約束條件     &#

10、160;    (6)式中 為第站上第件行包的運到期限； 為第站上第件行包在該站已存放的時間， 為該列車從第站到第站所需運行時間，第k站為該行包卸車站。2.1.5  ?？空狙b卸能力約束條件                   =1，2，      (7)式中 為第站的行包作業(yè)裝卸效率； 為運輸設備在第站的停站時間。目前車站的裝卸能力基本上

11、可以滿足要求，此約束條件在實際處理時做為 參考 。2.2  貨物配裝目標函數(shù) 由于運力有限，經(jīng)常不能一次把所有的行包運完，這樣就需要找到最大或較大的裝載效益值，裝載效益用max來表示。影響max的因素按照權重值由大到小依次為行包種類的優(yōu)先級、貨物的存放時間、到站距離和保價金額。裝載效益目標函數(shù)如公式(8)所示。max= (8)公式(8)中，rij表示貨物的優(yōu)先級權重，不同種類行包的優(yōu)先級如表1所示，表1中的rij值在使用時可根據(jù)具體情況進行等比浮動； （1）表示貨物的存放時間；dij表示行包到站里程；mij表示行包保價金額。行包的保價金額是行包價值的重要體現(xiàn)之一，在其他條件相同的情況

12、下，可以把保價作為是否裝車的衡量標準。這樣可以做到行包配裝的進一步公平，同時也可以促進保價收入。公式(8)中的四種權重在具體使用時可根據(jù)要求不同而作相應的比例浮動。表1  行包分類優(yōu)先級    優(yōu)先級（r ij ） 行包種類名稱 優(yōu)先級（r ij ） 行包種類名稱    12 搶險救災物資 6 滯留始發(fā)行李    11 急救藥品 5 當日始發(fā)行李    10 誤運行包 4 提前始發(fā)行李   

13、60;9 零星支農(nóng)物資 3 中轉(zhuǎn)包裹    8 生鮮物品 2 快運始發(fā)包裹    7 中轉(zhuǎn)行李 1 普通始發(fā)包裹     3  編程實現(xiàn) 鐵路各個客運車站分布距離相對比廣泛，操作人員的水平參差不齊，這就要求軟件的可靠性和簡單易操作性必須要強?！拌F路行包管理系統(tǒng)”開發(fā)工具采用的是Delphi 7.0，數(shù)據(jù)庫采用的是Microsoft公司的SQL Server 2000。3.1  數(shù)據(jù)庫設計 在行包配裝算法中主要用到車次信息、?？空拘畔ⅰ⑿邪畔⒑托?/p>

14、包種類優(yōu)先級信息等。車次和車次?？空臼莾蓚€基礎數(shù)據(jù)信息，這兩個表的字段定義如表2 和表3所示。是行包配裝的重要依據(jù)。表2  CCB車次信息表    字段名 類型 中文說明    TrainNumber Varchar(10) 車次    StartStation Varchar(16) 始發(fā)站    ArriveStation Varchar(16) 終到站    ArriveTime

15、datetime 到站時間    StartTime datetime 發(fā)車時間    UseTime Int 運行時間    Distance Int 里程    WEight Int 載重重量    Capability Float 車廂容積    表3  TKZB?？空拘畔⒈?#160;   字段名 類型 中文說

16、明    TrainNumber Varchar(10) 車次    StationName Varchar(16) 站名    StationSeriel Int 站次    ArriveTime datetime 到站時間    StartTime datetime 發(fā)車時間    RunTime Int 運行時間   &#

17、160;RunDay Int 運行天數(shù)    Distance Int 里程    CrossL Boolean 中轉(zhuǎn)站標志    表2 和表3的數(shù)據(jù)可以從鐵路管理信息系統(tǒng)（TMIS）的客運制票數(shù)據(jù)庫服務器中導出，鐵路局下面的每個車站直接導入使用。行包信息表的字段定義如表4 所示。行包信息表中包括始發(fā)貨物和中轉(zhuǎn)貨物。表4：XBXX行包信息表    字段名 類型 中文說明    TicketNumb

18、er Varchar(7) 票號    PackageName Varchar(20) 品名    ArriveStation Varchar(16) 到站名稱    Distance Int 到站里程    PackageType Int 行包類別    PackType Varchar(16) 包裝種類    Number Int 件數(shù) 

19、60;  WEight Int 重量    Volume Float 體積    InsureMoney Int 保價金額    LimitedDay Int 運到期限    FrEIght Float 運費    TicketTime datetime 制票時間    maxb int 裝載效益   

20、60; 3.2  關鍵程序設計 行包配裝的目的是從所有的行包X中挑選出要裝車的行包x?；谇懊鏀?shù)學模型分析，程序設計將根據(jù)行包配裝的約束條件，采取逐步剔除不符合裝車條件的行包，生成最終裝車單，具體的程序設計流程如圖3所示。3.2.1  根據(jù)到站選擇裝車行包 由約束條件公式(3)可知，滿足到站裝車的條件有兩種，一是(Di ÎSi)；二是(DiÏS直達 && min D (Di, Ti)；第二種情況 計算 貨物裝載車次到站最短距離（CalculateMinDis）函數(shù)的實現(xiàn)相對復雜一些，但此函數(shù)是屬于圖論中求兩點之間最短路徑的問題。

21、為了簡化此函數(shù)的算法，在?？空颈恚═KZB）中添加了一個中轉(zhuǎn)站標志（CrossL）字段，有了此項將大大降低程序的復雜度和提高函數(shù)的處理速度。部分程序代碼如下：CreatTempTable(#TKZB_T);  / 創(chuàng)建停靠站臨時表CreatTempTable(#XBXX_T);  / 創(chuàng)建行包信息臨時表 AdoQuery1.sql.clear;         AdoQuery1.add(insert into #TKZB_T (select * from TKZB where TrainNum

22、ber =”當前車次”);         AdoQuery1.ExeSql;   / 將滿足( Di Î Si )條件的到站添加到停靠站臨時表中CalculateMinDis (當前車次);   / 將滿足(DiÏS直達 && min D (Di, Ti)條件的到站添加到?？空九R時表中 AdoQuery1.sql.close;AdoQuery1.sql.clear;      &

23、#160;  AdoQuery1.add (insert into #XBXX_T (select XBXX.* from XBXX,#TKZB_T where #TKZB_T.StationName = XBXX.ArriveStation);AdoQuery1.ExeSql;       / 將滿足到站條件的行包添加到行包信息臨時表中 3.2.2  計算備裝行包的max并排序 從目標函數(shù)公式(8)知，在計算max時將用到行包類別、貨物存放時間、到站里程和保價金額。其中貨物存放時間可根據(jù)制票時間求得。部

24、分程序代碼如下：AdoQuery1.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; &