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

　　論文關(guān)鍵詞：鐵路車站  行包  裝配  編程實(shí)現(xiàn)

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

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

　　1  行包配裝問題分析

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

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

　　行包的到站與車次的停靠站之間有兩種情況，一是貨物的到站屬于當(dāng)前車次的�？空�，此行包直接加入到備裝貨物集；二是貨物到站不在本次車的停靠站中，但又無直達(dá)車，經(jīng)計(jì)算裝此趟車進(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ì)算機(jī)科學(xué)的輔助決策，使行李車的利用效率最大，最大可能的減少和避免裝車錯(cuò)誤^[8]。裝車單生成的約束條件主要有重量和體積等方面。

　　Step 3: 人工調(diào)整確認(rèn)裝車單

　　計(jì)算機(jī)輔助生成的裝裝配計(jì)劃應(yīng)基本達(dá)到了最佳優(yōu)化裝車方案，但由于車站運(yùn)輸?shù)哪承┡R時(shí)特殊要求，車站行李員可對裝車單在一定許可范圍內(nèi)進(jìn)行調(diào)整。

　　2  行包配裝問題的模型

　　令待運(yùn)行包集合為X，車站發(fā)車車次集合T。二者的映射定義為：

　　ƒ：X → T                                                          (1)

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

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

　　令T_i車次停靠站的集合用S_i（1 £ i £ m）表示，承運(yùn)站直達(dá)站集合S_直達(dá) = {S₁ ∩ S₂ ∩ … ∩ S_m}。貨物�？空炯�合用D = {D₁, D₂, … , D_n}表示。

　　2.1  條件約束模型

　　2.1.1  行包到站約束條件

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

　　（2）行包到站無直達(dá)車（D_iÏS_直達(dá)），但是裝此車次中轉(zhuǎn)貨物運(yùn)送距離最短。

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

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

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

　　2.1.2  行包車載重約束條件

         ｋ=1，2，…           (4)

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

　　2.1.3  行包運(yùn)輸車容積約束條件

　　 �。�=1，2，…             (5)

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

　　2.1.4  行包運(yùn)到期限約束條件

　　         (6)

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

　　2.1.5  停靠站裝卸能力約束條件

                ｋ=1，2，…      (7)

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

　　2.2  貨物配裝目標(biāo)函數(shù)

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

　　maxＢ= (8)

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

表1  行包分類優(yōu)先級

　　3  編程實(shí)現(xiàn)

　　鐵路各個(gè)客運(yùn)車站分布距離相對比廣泛，操作人員的水平參差不齊，這就要求軟件的可靠性和簡單易操作性必須要強(qiáng)。“鐵路行包系統(tǒng)”開發(fā)工具采用的是Delphi 7.0，數(shù)據(jù)庫采用的是Microsoft公司的SQL Server 2000。

　　3.1  數(shù)據(jù)庫設(shè)計(jì)

　　在行包配裝算法中主要用到車次信息、�？空拘畔�、行包信息和行包種類優(yōu)先級信息等。車次和車次停靠站是兩個(gè)基礎(chǔ)數(shù)據(jù)信息，這兩個(gè)表的字段定義如表2 和表3所示。是行包配裝的重要依據(jù)。

表2  CCB—車次信息表

表3  TKZB—�？空拘畔⒈�

　　表2 和表3的數(shù)據(jù)可以從鐵路管理信息系統(tǒng)（TMIS）的客運(yùn)制票數(shù)據(jù)庫服務(wù)器中導(dǎo)出，鐵路局下面的每個(gè)車站直接導(dǎo)入使用。行包信息表的字段定義如表4 所示。行包信息表中包括始發(fā)貨物和中轉(zhuǎn)貨物。

表4：XBXX—行包信息表

　　3.2  關(guān)鍵程序設(shè)計(jì)

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

　　3.2.1  根據(jù)到站選擇裝車行包

        

 

 

 

 

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

　　CreatTempTable(#TKZB_T);  // 創(chuàng)建停靠站臨時(shí)表

　　CreatTempTable(#XBXX_T);  // 創(chuàng)建行包信息臨時(shí)表

　　AdoQuery1.sql.clear;

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

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

　　CalculateMinDis (‘當(dāng)前車次’);   // 將滿足(D_iÏS_直達(dá) && min D (D_i, T_i))條件的到站添加到�？空九R時(shí)表中 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;       // 將滿足到站條件的行包添加到行包信息臨時(shí)表中

　　3.2.2  計(jì)算備裝行包的maxＢ并排序

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

　　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Ｂ進(jìn)行排序

　　3.2.3  根據(jù)約束條件剔除多出的行包

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

　　4  結(jié)束語

　　本配裝算法對每一批行包是否裝車的進(jìn)行了科學(xué)的量化，避免了人為處理的隨意性，算法程序的可實(shí)現(xiàn)性大大增強(qiáng)。此算法在實(shí)際的使用過程中，可根據(jù)各個(gè)車站的實(shí)際來調(diào)整maxＢ的各個(gè)條件權(quán)重值來取得最佳的裝車效果。裝車的約束條件可根據(jù)不同的車站而有選擇性地進(jìn)行處理。本文是作者在開發(fā)實(shí)踐經(jīng)驗(yàn)的基礎(chǔ)上進(jìn)行的歸納。

　　參考文獻(xiàn)

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

　　2 孫遠(yuǎn)運(yùn).TMIS總體架構(gòu)設(shè)計(jì)研究[J].北京:鐵路應(yīng)用,2005.7

　　3 賀振歡,劉軍.鐵路車站行包配裝計(jì)算機(jī)輔助決策系統(tǒng)的研究[J].北京:北京大學(xué)學(xué)報(bào)，2000.6

　　4  雷定獻(xiàn),陳德良.平衡裝載問題的優(yōu)化模型和算法[J].天津:系統(tǒng)工程學(xué)報(bào),2004.6

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

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

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

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

【鐵路行包配裝算法研究與實(shí)現(xiàn)】相關(guān)文章：

基于價(jià)值網(wǎng)理論的鐵路多元經(jīng)營物流企業(yè)經(jīng)營模式研究06-04

數(shù)據(jù)關(guān)聯(lián)算法綜述及其性能評估05-05

都市頻道制作網(wǎng)的設(shè)計(jì)與實(shí)現(xiàn)05-29

基于minigui的網(wǎng)真機(jī)界面的實(shí)現(xiàn)08-05

城市旅游網(wǎng)站的設(shè)計(jì)與實(shí)現(xiàn)論文（精選6篇）05-07

企業(yè)知識管理的實(shí)現(xiàn)技術(shù)和工具的電商論文05-02

企業(yè)法律風(fēng)險(xiǎn)防范體系建立的原因及實(shí)現(xiàn)路徑08-06

如何通過內(nèi)部控制實(shí)現(xiàn)企業(yè)持續(xù)性發(fā)展05-21

用Verilog HDL實(shí)現(xiàn)I2C總線功能06-01

利用電力線實(shí)現(xiàn)住宅智能化06-13