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

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

2、業(yè)務(wù)量的增長(zhǎng)，大部分車站在承運(yùn)、交付、中轉(zhuǎn)和綜合統(tǒng)計(jì)報(bào)表打印等都實(shí)現(xiàn)了計(jì)算機(jī)的自動(dòng)化管理。但是，在整個(gè)業(yè)務(wù)流程中的裝車單生成部分，現(xiàn)如今依然采用人工或半人工的方式進(jìn)行處理。由于與“裝車”相關(guān)的因素較多，所以大多的鐵路行包管理系統(tǒng)對(duì)此采取回避的辦法。如今，在行包運(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  行包配裝問題分析   行包裝配主要是指合理

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

4、種情況，一是貨物的到站屬于當(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í)特殊要求，車站行李員

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

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

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

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

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

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

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

12、裝車的衡量標(biāo)準(zhǔn)。這樣可以做到行包配裝的進(jìn)一步公平，同時(shí)也可以促進(jìn)保價(jià)收入。公式(8)中的四種權(quán)重在具體使用時(shí)可根據(jù)要求不同而作相應(yīng)的比例浮動(dòng)。表1  行包分類優(yōu)先級(jí)優(yōu)先級(jí)（rij）行包種類名稱優(yōu)先級(jí)（rij）行包種類名稱12搶險(xiǎn)救災(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  編程實(shí)現(xiàn) 鐵路各個(gè)客運(yùn)車站分布距離相對(duì)比廣泛，操作人員的水平參差不齊，這就要求軟件的可靠性和簡(jiǎn)單易操作性必須要強(qiáng)?！拌F路行包管理系統(tǒng)”開發(fā)工具采用的是Delphi 7.0，數(shù)據(jù)庫(kù)采用的是M

13、icrosoft公司的SQL Server 2000。3.1  數(shù)據(jù)庫(kù)設(shè)計(jì) 在行包配裝算法中主要用到車次信息、?？空拘畔?、行包信息和行包種類優(yōu)先級(jí)信息等。車次和車次?？空臼莾蓚€(gè)基礎(chǔ)數(shù)據(jù)信息，這兩個(gè)表的字段定義如表2 和表3所示。是行包配裝的重要依據(jù)。表2  CCB車次信息表字段名類型中文說明TrainNumberVarchar(10)車次StartStationVarchar(16)始發(fā)站ArriveStationVarchar(16)終到站ArriveTimedatetime到站時(shí)間StartTimedatetime發(fā)車時(shí)間UseTimeInt運(yùn)行時(shí)間DistanceIn

14、t里程WeightInt載重重量CapabilityFloat車廂容積表3  TKZB?？空拘畔⒈碜侄蚊愋椭形恼f明TrainNumberVarchar(10)車次StationNameVarchar(16)站名StationSerielInt站次ArriveTimedatetime到站時(shí)間StartTimedatetime發(fā)車時(shí)間RunTimeInt運(yùn)行時(shí)間RunDayInt運(yùn)行天數(shù)DistanceInt里程CrossLBoolean中轉(zhuǎn)站標(biāo)志本篇論文由網(wǎng)友投稿，3COME文檔只給大家提供一個(gè)交流平臺(tái)，請(qǐng)大家參考，如有版權(quán)問題請(qǐng)聯(lián)系我們盡快處理。表2 和表3的數(shù)據(jù)可以從鐵路管理信息

15、系統(tǒng)（TMIS）的客運(yùn)制票數(shù)據(jù)庫(kù)服務(wù)器中導(dǎo)出，鐵路局下面的每個(gè)車站直接導(dǎo)入使用。行包信息表的字段定義如表4 所示。行包信息表中包括始發(fā)貨物和中轉(zhuǎn)貨物。表4：XBXX行包信息表字段名類型中文說明TicketNumberVarchar(7)票號(hào)PackageNameVarchar(20)品名ArriveStationVarchar(16)到站名稱DistanceInt到站里程PackageTypeInt行包類別PackTypeVarchar(16)包裝種類NumberInt件數(shù)WeightInt重量VolumeFloat體積InsureMoneyInt保價(jià)金額LimitedDayInt運(yùn)到期限Fr

16、eightFloat運(yùn)費(fèi)TicketTimedatetime制票時(shí)間maxbint裝載效益 3.2  關(guān)鍵程序設(shè)計(jì) 行包配裝的目的是從所有的行包X中挑選出要裝車的行包x?；谇懊鏀?shù)學(xué)模型分析，程序設(shè)計(jì)將根據(jù)行包配裝的約束條件，采取逐步剔除不符合裝車條件的行包，生成最終裝車單，具體的程序設(shè)計(jì)流程如圖3所示。3.2.1  根據(jù)到站選擇裝車行包 由約束條件公式(3)可知，滿足到站裝車的條件有兩種，一是(Di ÎSi)；二是(DiÏS直達(dá) && min D (Di, Ti)；第二種情況計(jì)算貨物裝載車次到站最短距離（CalculateMi

17、nDis）函數(shù)的實(shí)現(xiàn)相對(duì)復(fù)雜一些，但此函數(shù)是屬于圖論中求兩點(diǎn)之間最短路徑的問題。為了簡(jiǎn)化此函數(shù)的算法，在停靠站表（TKZB）中添加了一個(gè)中轉(zhuǎn)站標(biāo)志（CrossL）字段，有了此項(xiàng)將大大降低程序的復(fù)雜度和提高函數(shù)的處理速度。部分程序代碼如下：CreatTempTable(#TKZB_T);  / 創(chuàng)建?？空九R時(shí)表CreatTempTable(#XBXX_T);  / 創(chuàng)建行包信息臨時(shí)表 AdoQuery1.sql.clear;         AdoQuery1.add(insert into #T

18、KZB_T (select * from TKZB where TrainNumber =”當(dāng)前車次”);         AdoQuery1.ExeSql;   / 將滿足( Di Î Si )條件的到站添加到停靠站臨時(shí)表中CalculateMinDis (當(dāng)前車次);   / 將滿足(DiÏS直達(dá) && min D (Di, Ti)條件的到站添加到?？空九R時(shí)表中 AdoQuery1.sql.close;AdoQuery1.sql.cle

19、ar;         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í)將用到行

20、包類別、貨物存放時(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;               / maxAdoQuery1.sql.close;AdoQuery1.sql.clear;         AdoQuery1.add (select * from #XBXX_T order by maxb);AdoQuery1.Open;                / 按max進(jìn)行排序3.2.3