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

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

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

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

4、貨物集；二是貨物到站不在本次車的?？空局?，但又無直達(dá)車，經(jīng)計算裝此趟車進(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ī)科學(xué)的輔助決策，使行李車的利用效率最大，最大可能的減少和避免裝車錯誤8。裝車單生成的約束條件主要有重量和體積等方面。 Step 3: 人工調(diào)整確認(rèn)裝車單 計算機(jī)輔助生成的裝裝配計劃應(yīng)基本達(dá)到了最佳優(yōu)化裝車方案，但由于車站運(yùn)輸?shù)哪承┡R時特殊要求，車站行李員可對裝車單在一定許可范圍內(nèi)進(jìn)行調(diào)整。 2 行包配裝問題的

5、數(shù)學(xué)模型令待運(yùn)行包集合為X，車站發(fā)車車次集合T。二者的映射定義為： ：X T (1) 現(xiàn)在要為每一趟車進(jìn)行配裝，生成每一車次的裝車單：x X。為了求解x，首先要確定映射關(guān)系。由公式(1)可以看出，即使確定了，也很難最終求解x，如果能求出T中一個車次的結(jié)果，則其他車次依此類推，便可求出全部解。由此將公式(1)簡化為： (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.

6、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 行包運(yùn)輸車載重約束條件 =1，2， (4) 式中xij0,1為第i車站，第j件貨物的裝載狀態(tài)，gij為第i車站，第j件貨物的的重量，裝為車輛已裝載重量，G車為車輛的規(guī)定載重量。 2.1.3 行包運(yùn)

7、輸車容積約束條件 =1，2， (5) 式中Vij為第站上第件行包的體積，V裝為車輛已裝載容積，V車為行李車的容積； 2.1.4 行包運(yùn)到期限約束條件 (6) 式中 為第站上第件行包的運(yùn)到期限； 為第站上第件行包在該站已存放的時間，為該列車從第站到第站所需運(yùn)行時間，第k站為該行包卸車站。 2.1.5 停靠站裝卸能力約束條件 =1，2， (7) 式中 為第站的行包作業(yè)裝卸效率；為運(yùn)輸設(shè)備在第站的停站時間。目前車站的裝卸能力基本上可以滿足要求，此約束條件在實際處理時做為參考。 2.2 貨物配裝目標(biāo)函數(shù)由于運(yùn)力有限，經(jīng)常不能一次把所有的行包運(yùn)完，這樣就需要找到最大或較大的裝載效益值，裝載效益用max來

8、表示。影響max的因素按照權(quán)重值由大到小依次為行包種類的優(yōu)先級、貨物的存放時間、到站距離和保價金額。裝載效益目標(biāo)函數(shù)如公式(8)所示。 max= (8) 公式(8)中，rij表示貨物的優(yōu)先級權(quán)重，不同種類行包的優(yōu)先級如表1所示，表1中的rij值在使用時可根據(jù)具體情況進(jìn)行等比浮動； （1）表示貨物的存放時間；dij表示行包到站里程；mij表示行包保價金額。行包的保價金額是行包價值的重要體現(xiàn)之一，在其他條件相同的情況下，可以把保價作為是否裝車的衡量標(biāo)準(zhǔn)。這樣可以做到行包配裝的進(jìn)一步公平，同時也可以促進(jìn)保價收入。公式(8)中的四種權(quán)重在具體使用時可根據(jù)要求不同而作相應(yīng)的比例浮動。 表1 行包分類優(yōu)先

9、級 優(yōu)先級（rij） 行包種類名稱 優(yōu)先級（rij） 行包種類名稱 12 搶險救災(zāi)物資 6 滯留始發(fā)行李 11 急救藥品 5 當(dāng)日始發(fā)行李 10 誤運(yùn)行包 4 提前始發(fā)行李 9 零星支農(nóng)物資 3 中轉(zhuǎn)包裹 8 生鮮物品 2 快運(yùn)始發(fā)包裹 7 中轉(zhuǎn)行李 1 普通始發(fā)包裹 3 編程實現(xiàn)鐵路各個客運(yùn)車站分布距離相對比廣泛，操作人員的水平參差不齊，這就要求軟件的可靠性和簡單易操作性必須要強(qiáng)?！拌F路行包管理系統(tǒng)”開發(fā)工具采用的是Delphi 7.0，數(shù)據(jù)庫采用的是Microsoft公司的SQL Server 2000。 3.1 數(shù)據(jù)庫設(shè)計在行包配裝算法中主要用到車次信息、?？空拘畔?、行包信息和行包種類優(yōu)

10、先級信息等。車次和車次?？空臼莾蓚€基礎(chǔ)數(shù)據(jù)信息，這兩個表的字段定義如表2 和表3所示。是行包配裝的重要依據(jù)。 表2 CCB車次信息表 字段名 類型 中文說明 TrainNumber Varchar(10) 車次 StartStation Varchar(16) 始發(fā)站 ArriveStation Varchar(16) 終到站 ArriveTime datetime 到站時間 StartTime datetime 發(fā)車時間 UseTime Int 運(yùn)行時間 Distance Int 里程 Weight Int 載重重量 Capability Float 車廂容積 表3 TKZB?？空拘畔⒈?字

11、段名 類型 中文說明 TrainNumber Varchar(10) 車次 StationName Varchar(16) 站名 StationSeriel Int 站次 ArriveTime datetime 到站時間 StartTime datetime 發(fā)車時間 RunTime Int 運(yùn)行時間 RunDay Int 運(yùn)行天數(shù) Distance Int 里程 CrossL Boolean 中轉(zhuǎn)站標(biāo)志 表2 和表3的數(shù)據(jù)可以從鐵路管理信息系統(tǒng)（TMIS）的客運(yùn)制票數(shù)據(jù)庫服務(wù)器中導(dǎo)出，鐵路局下面的每個車站直接導(dǎo)入使用。行包信息表的字段定義如表4 所示。行包信息表中包括始發(fā)貨物和中轉(zhuǎn)貨物。 表

12、4：XBXX行包信息表 字段名 類型 中文說明 TicketNumber Varchar(7) 票號 PackageName Varchar(20) 品名 ArriveStation Varchar(16) 到站名稱 Distance Int 到站里程 PackageType Int 行包類別 PackType Varchar(16) 包裝種類 Number Int 件數(shù) Weight Int 重量 Volume Float 體積 InsureMoney Int 保價金額 LimitedDay Int 運(yùn)到期限 Freight Float 運(yùn)費(fèi) TicketTime datetime 制票時間

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

14、算法，在?？空颈恚═KZB）中添加了一個中轉(zhuǎn)站標(biāo)志（CrossL）字段，有了此項將大大降低程序的復(fù)雜度和提高函數(shù)的處理速度。部分程序代碼如下： 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 =”當(dāng)前車次”); AdoQuery1.ExeSql; / 將滿足( Di Î Si )條件的到站添加到?？空九R時

15、表中 CalculateMinDis (當(dāng)前車次); / 將滿足(DiÏS直達(dá) && min D (Di, Ti)條件的到站添加到?？空九R時表中 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; / 將滿足到站條件的行包添加到行包信息臨時表中 3.2.2 計算備裝行包的

16、max并排序從目標(biāo)函數(shù)公式(8)知，在計算max時將用到行包類別、貨物存放時間、到站里程和保價金額。其中貨物存放時間可根據(jù)制票時間求得。部分程序代碼如下： AdoQuery1.sql.close; AdoQuery1.sql.clear; AdoQuery1.add (update #XBXX_T set maxb = PackageType* (now- TicketTime)+ Distance/200+ InsureMoney/500); AdoQuery1.ExeSql; / max AdoQuery1.sql.close; AdoQuery1.sql.clear; AdoQuery1

17、.add (select * from #XBXX_T order by maxb); AdoQuery1.Open; / 按max進(jìn)行排序 3.2.3 根據(jù)約束條件剔除多出的行包約束條件公式(4)是在生成裝成單時必須要考慮的項。目前在一些站由于每一個行包的體積不能準(zhǔn)確給出，所以約束條件公式(5)這一項在實際編程時可根據(jù)實際的體積數(shù)據(jù)進(jìn)行處理，主要是作為參考。?？空狙b卸能力約束，如公式(7)，此約束條件若知道了每一個?？空镜?和，則具體的編程實現(xiàn)并不復(fù)雜，單位時間裝卸能力和裝卸時間的值可通過系統(tǒng)參數(shù)輸入界面人工維護(hù)進(jìn)去。 4 結(jié)束語本配裝算法對每一批行包是否裝車的進(jìn)行了科學(xué)的量化，避免了人為處理的隨意性，算法程序的可實現(xiàn)性大大增強(qiáng)。此算法在實際的使用過程中，可根據(jù)各個車站的實際來調(diào)整max的各個條件權(quán)重值來取得最佳的裝車效果。裝車的約束條件可根據(jù)不同的車站而有選擇性地進(jìn)行處理。本文是作者在開發(fā)實踐經(jīng)驗的基礎(chǔ)上進(jìn)行的歸納總結(jié)。 參考文獻(xiàn) 1 潘俊杰,王一新.鐵路旅客列車行李車配裝問題的遺傳算法研究J.蘭州:甘肅科技,2004.6 2 孫遠(yuǎn)運(yùn).TMIS總體架構(gòu)設(shè)計研究J.北京:鐵路計算機(jī)應(yīng)用,2005.7 3 賀