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

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

　　論文關鍵詞：鐵路車站  行包  裝配  編程實現

　　論文摘要：行包裝配是鐵路行包的重難點之一，在鐵路行包中出現的大部分問題均是由行包裝配不當引起的。影響行包裝配的因素較多，通過對鐵路行包裝配的流程和影響行包裝配的主要因素進行分析，建立了鐵路車站行包裝配問題的條件約束模型，提出鐵路行包裝配的目標函數，最后給出了鐵路行包裝配問題的編程實現方法。

　　鐵路行李包裹運輸（以下簡稱行包運輸）是利用鐵路客運設施，以隨掛旅客列車的行李車為載體的一種運輸形式^[1]，其業務流程如圖1所示。近年來，隨著行包運輸業務量的增長，大部分車站在承運、交付、中轉和綜合報表打印等都實現了的自動化管理。但是，在整個業務流程中的裝車單生成部分，現如今依然采用人工或半人工的方式進行處理。由于與“裝車”相關的因素較多，所以大多的鐵路行包管理系統對此采取回避的辦法。如今，在行包運輸中出現的大部分問題如貨物漏裝、錯裝、中轉不暢、快件不快等問題均是由行包裝配不當引起的^[2]。為此，解決好行包配裝問題，優化運載設備的利用率，降低運輸是一個非常有價值的研究課題。本文從行包管理軟件編程的實際出發，提出了一種優化的行包配裝算法，并給出了實現方法。

　　1  行包配裝問題分析

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

　　Step 1：根據車次和行包到站生成待裝車的行包集

　　行包的到站與車次的�？空局�間有兩種情況，一是貨物的到站屬于當前車次的�？空�，此行包直接加入到備裝貨物集；二是貨物到站不在本次車的�？空局�，但又無直達車，經計算裝此趟車進行中轉的距離最短，則此到站的行包加入到備裝貨物集中。

　　Step 2：根據行包運達要求，生成當前車次的裝車單

　　第一步生成的是應裝車的貨物清單，目前鐵路行包運輸還達不到應運即運的程度，因此還應根據行包運達的要求，通過計算機科學的輔助決策，使行李車的利用效率最大，最大可能的減少和避免裝車錯誤^[8]。裝車單生成的約束條件主要有重量和體積等方面。

　　Step 3: 人工調整確認裝車單

　　計算機輔助生成的裝裝配計劃應基本達到了最佳優化裝車方案，但由于車站運輸的某些臨時特殊要求，車站行李員可對裝車單在一定許可范圍內進行調整。

　　2  行包配裝問題的模型

　　令待運行包集合為X，車站發車車次集合T。二者的映射定義為：

　　ƒ：X → T                                                          (1)

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

 　　ƒ(x) →T_i  (1 £ i £ m，共有m趟車)             (2)

　　令T_i車次�？空镜募�合用S_i（1 £ i £ m）表示，承運站直達站集合S_直達 = {S₁ ∩ S₂ ∩ … ∩ S_m}。貨物�？空炯�合用D = {D₁, D₂, … , D_n}表示。

　　2.1  條件約束模型

　　2.1.1  行包到站約束條件

　　（1）行包到站為T_i次車的�？空�，即：D_i ÎS_i 。

　�。�2）行包到站無直達車（D_iÏS_直達），但是裝此車次中轉貨物運送距離最短。

　　因此行包到站約束條件公式：

　　(D_i ÎS_i) || (D_iÏS_直達 && min D (D_i, T_i))                      (3)

　　式中min D (D_i, T_i)表示貨物裝載T_i次車運送距離最短。

　　2.1.2  行包車載重約束條件

         ｋ=1，2，…           (4)

　　式中x_ij∈{0,1}為第i車站，第j件貨物的裝載狀態，g_ij為第i車站，第j件貨物的的重量，Ｇ_裝為車輛已裝載重量，G_車為車輛的規定載重量。

　　2.1.3  行包運輸車容積約束條件

　　 　ｋ=1，2，…             (5)

　　式中V_ij為第ｉ站上第ｊ件行包的體積，V_裝為車輛已裝載容積，V_車為行李車的容積；

　　2.1.4  行包運到期限約束條件

　　         (6)

　　式中 為第ｉ站上第ｊ件行包的運到期限； 為第ｉ站上第ｊ件行包在該站已存放的時間， 為該列車從第ｉ站到第ｍ站所需運行時間，第k站為該行包卸車站。

　　2.1.5  �？空狙b卸能力約束條件

                ｋ=1，2，…      (7)

　　式中 為第ｉ站的行包作業裝卸效率； 為運輸設備在第ｉ站的停站時間。目前車站的裝卸能力基本上可以滿足要求，此約束條件在實際處理時做為參考。

　　2.2  貨物配裝目標函數

　　由于運力有限，經常不能一次把所有的行包運完，這樣就需要找到最大或較大的裝載效益值，裝載效益用maxＢ來表示。影響maxＢ的因素按照權重值由大到小依次為行包種類的優先級、貨物的存放時間、到站距離和保價金額。裝載效益目標函數如公式(8)所示。

　　maxＢ= (8)

　　公式(8)中，r_ij表示貨物的優先級權重，不同種類行包的優先級如表1所示，表1中的r_ij值在使用時可根據具體情況進行等比浮動； （≥1）表示貨物的存放時間；d_ij表示行包到站里程；m_ij表示行包保價金額。行包的保價金額是行包價值的重要體現之一，在其他條件相同的情況下，可以把保價作為是否裝車的衡量標準。這樣可以做到行包配裝的進一步公平，同時也可以促進保價收入。公式(8)中的四種權重在具體使用時可根據要求不同而作相應的比例浮動。

表1  行包分類優先級

　　3  編程實現

　　鐵路各個客運車站分布距離相對比廣泛，操作人員的水平參差不齊，這就要求軟件的可靠性和簡單易操作性必須要強�！拌F路行包系統”開發工具采用的是Delphi 7.0，數據庫采用的是Microsoft公司的SQL Server 2000。

　　3.1  數據庫設計

　　在行包配裝算法中主要用到車次信息、�？空拘畔ⅰ⑿邪�信息和行包種類優先級信息等。車次和車次停靠站是兩個基礎數據信息，這兩個表的字段定義如表2 和表3所示。是行包配裝的重要依據。

表2  CCB—車次信息表

表3  TKZB—�？空拘畔⒈�

　　表2 和表3的數據可以從鐵路管理信息系統（TMIS）的客運制票數據庫服務器中導出，鐵路局下面的每個車站直接導入使用。行包信息表的字段定義如表4 所示。行包信息表中包括始發貨物和中轉貨物。

表4：XBXX—行包信息表

　　3.2  關鍵程序設計

　　行包配裝的目的是從所有的行包X中挑選出要裝車的行包x�；�于前面模型分析，程序設計將根據行包配裝的約束條件，采取逐步剔除不符合裝車條件的行包，生成最終裝車單，具體的程序設計流程如圖3所示。

　　3.2.1  根據到站選擇裝車行包

        

 

 

 

 

　　由約束條件公式(3)可知，滿足到站裝車的條件有兩種，一是(D_i ÎS_i)；二是(D_iÏS_直達 && min D (D_i, T_i))；第二種情況計算貨物裝載車次到站最短距離（CalculateMinDis）函數的實現相對復雜一些，但此函數是屬于圖論中求兩點之間最短路徑的問題。為了簡化此函數的算法，在�？空颈恚═KZB）中添加了一個中轉站標志（CrossL）字段，有了此項將大大降低程序的復雜度和提高函數的處理速度。部分程序代碼如下：

　　CreatTempTable(#TKZB_T);  // 創建�？空九R時表

　　CreatTempTable(#XBXX_T);  // 創建行包信息臨時表

　　AdoQuery1.sql.clear;

         AdoQuery1.add(‘insert into #TKZB_T (select * from TKZB where TrainNumber =”當前車次”)’);

         AdoQuery1.ExeSql;   // 將滿足( D_i Î S_i )條件的到站添加到�？空九R時表中

　　CalculateMinDis (‘當前車次’);   // 將滿足(D_iÏS_直達 && min D (D_i, T_i))條件的到站添加到�？空九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  計算備裝行包的maxＢ并排序

　　從目標函數公式(8)知，在計算maxＢ時將用到行包類別、貨物存放時間、到站里程和保價金額。其中貨物存放時間可根據制票時間求得。部分程序代碼如下：

　　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.add (‘select * from #XBXX_T order by maxb’);

　　AdoQuery1.Open;                // 按maxＢ進行排序

　　3.2.3  根據約束條件剔除多出的行包

　　約束條件公式(4)是在生成裝成單時必須要考慮的項。目前在一些站由于每一個行包的體積不能準確給出，所以約束條件公式(5)這一項在實際編程時可根據實際的體積數據進行處理，主要是作為參考。�？空狙b卸能力約束，如公式(7)，此約束條件若知道了每一個�？空镜� 和 ，則具體的編程實現并不復雜，單位時間裝卸能力和裝卸時間的值可通過系統參數輸入界面人工維護進去。

　　4  結束語

　　本配裝算法對每一批行包是否裝車的進行了科學的量化，避免了人為處理的隨意性，算法程序的可實現性大大增強。此算法在實際的使用過程中，可根據各個車站的實際來調整maxＢ的各個條件權重值來取得最佳的裝車效果。裝車的約束條件可根據不同的車站而有選擇性地進行處理。本文是作者在開發實踐經驗的基礎上進行的歸納。

　　參考文獻

　　1 潘俊杰,王一新.鐵路旅客列車行李車配裝問題的遺傳算法研究[J].蘭州:甘肅科技,2004.6

　　2 孫遠運.TMIS總體架構設計研究[J].北京:鐵路應用,2005.7

　　3 賀振歡,劉軍.鐵路車站行包配裝計算機輔助決策系統的研究[J].北京:北京大學學報，2000.6

　　4  雷定獻,陳德良.平衡裝載問題的優化模型和算法[J].天津:系統工程學報,2004.6

　　5 吳清一.物流[M].北京:中國物資出版社,2003

　　6 譚顯倫,阮永良.一種新的背包加強算法[J].合肥:電腦知識與技術,2004.10

　　7 瀏小群,馬士華,徐天亮.裝載能力有限下多品種貨物配裝的容重比平衡法[J].上海:工程與管理,2004.3

　　8 中華人民共和國鐵道部.鐵路旅客管理規則[S].北京:中國鐵道出版社,1998

【鐵路行包配裝算法研究與實現】相關文章：

基于價值網理論的鐵路多元經營物流企業經營模式研究06-04

數據關聯算法綜述及其性能評估05-05

都市頻道制作網的設計與實現05-29

基于minigui的網真機界面的實現08-05

城市旅游網站的設計與實現論文（精選6篇）05-07

企業知識管理的實現技術和工具的電商論文05-02

企業法律風險防范體系建立的原因及實現路徑08-06

如何通過內部控制實現企業持續性發展05-21

用Verilog HDL實現I2C總線功能06-01

利用電力線實現住宅智能化06-13