铁路行包配装算法研究与实现

1、    铁路行包配装算法研究与实现            作者：李宏权 杨伟锋 陈莉时间：2010-2-2 9:39:00                     论文关键词：铁路车站  行包  装配  编程实

2、现论文摘要：行包装配是铁路行包管理的重难点之一，在铁路行包运输中出现的大部分问题均是由行包装配不当引起的。影响行包装配的因素较多，通过对铁路行包装配的流程和影响行包装配的主要因素进行分析，建立了铁路车站行包装配问题的条件约束模型，提出铁路行包装配的目标函数，最后给出了铁路行包装配问题的编程实现方法。铁路行李包裹运输（以下简称行包运输）是利用铁路客运设施，以随挂旅客列车的行李车为载体的一种运输形式1，其业务流程如图1所示。近年来，随着行包运输业务量的增长，大部分车站在承运、交付、中转和综合统计报表打印等都实现了计算机的自动化管理。但是，在整个业务流程中的装车单生成部分，现如今依然采用人工或半人工

3、的方式进行处理。由于与“装车”相关的因素较多，所以大多的铁路行包管理系统对此采取回避的办法。如今，在行包运输中出现的大部分问题如货物漏装、错装、中转不畅、快件不快等问题均是由行包装配不当引起的2。为此，解决好行包配装问题，优化运载设备的利用率，降低运输成本是一个非常有价值的研究课题。本文从行包管理软件编程的实际出发，提出了一种优化的行包配装算法，并给出了实现方法。1  行包配装问题分析               行包装配主要是指合理制定待装行包

4、的装配计划。在现有运能一定的条件下，根据行包运达的要求，通过计算机科学的辅助决策，使行李车的利用效率最大3，最大可能的减少和避免装车错误。铁路车站行包配装归属背包问题，但又与普通的背包问题有一定的不同。普通的背包问题是一对多的关系，而对于本问题的映射是多对多的关系，约束条件需要考虑客运车次、行包到站、运到期限、保价金额、货物优先级和车次的运量、容积、沿途站装卸作业能力等因素，行包配装单的生成流程如图2所示。铁路行包装配问题在学术上属于复杂约束条件的组合优化间题。从图2可以得出铁路行包配装可分解为三步。Step 1：根据车次和行包到站生成待装车的行包集行包的到站与车次的停靠站之间有两种情况，一是

5、货物的到站属于当前车次的停靠站，此行包直接加入到备装货物集；二是货物到站不在本次车的停靠站中，但又无直达车，经计算装此趟车进行中转的距离最短，则此到站的行包加入到备装货物集中。Step 2：根据行包运达要求，生成当前车次的装车单第一步生成的是应装车的货物清单，目前铁路行包运输还达不到应运即运的程度，因此还应根据行包运达的要求，通过计算机科学的辅助决策，使行李车的利用效率最大，最大可能的减少和避免装车错误8。装车单生成的约束条件主要有重量和体积等方面。Step 3: 人工调整确认装车单计算机辅助生成的装装配计划应基本达到了最佳优化装车方案，但由于车站运输的某些临时特殊要求，车站行李员可对装车单在

6、一定许可范围内进行调整。2  行包配装问题的数学模型 令待运行包集合为X，车站发车车次集合T。二者的映射定义为：X T                                          

7、;                (1)现在要为每一趟车进行配装，生成每一车次的装车单：x X。为了求解x，首先要确定映射关系。由公式(1)可以看出，即使确定了，也很难最终求解x，如果能求出T中一个车次的结果，则其他车次依此类推，便可求出全部解。由此将公式(1)简化为： (x) Ti  (1 £ i £ m，共有m趟车)        &

8、#160;    (2)    令Ti车次停靠站的集合用Si（1 £ i £ m）表示，承运站直达站集合S直达 = S1 S2 Sm。货物停靠站集合用D = D1, D2, , Dn表示。2.1  条件约束模型 （1）行包到站为Ti次车的停靠站，即：Di ÎSi 。（2）行包到站无直达车（DiÏS直达），但是装此车次中转货物运送距离最短。因此行包到站约束条件公式：(Di ÎSi) | (DiÏS直达 && min D (Di, Ti) &#

9、160;                    (3)式中min D (Di, Ti)表示货物装载Ti次车运送距离最短。         =1，2，           (4)式中xij0,1为第i车站，第j件货物的装载状态，gij为第i车

10、站，第j件货物的的重量，装为车辆已装载重量，G车为车辆的规定载重量。 =1，2，             (5)式中Vij为第站上第件行包的体积，V装为车辆已装载容积，V车为行李车的容积；         (6)式中 为第站上第件行包的运到期限； 为第站上第件行包在该站已存放的时间， 为该列车从第站到第站所需运行时间，第k站为该行包卸车站。     

11、;           =1，2，      (7)式中 为第站的行包作业装卸效率； 为运输设备在第站的停站时间。目前车站的装卸能力基本上可以满足要求，此约束条件在实际处理时做为参考。2.2  货物配装目标函数 由于运力有限，经常不能一次把所有的行包运完，这样就需要找到最大或较大的装载效益值，装载效益用max来表示。影响max的因素按照权重值由大到小依次为行包种类的优先级、货物的存放时间、到站距离和保价金额。装载效益目标函数如公式(8)所示。max= (8

12、)公式(8)中，rij表示货物的优先级权重，不同种类行包的优先级如表1所示，表1中的rij值在使用时可根据具体情况进行等比浮动； （1）表示货物的存放时间；dij表示行包到站里程；mij表示行包保价金额。行包的保价金额是行包价值的重要体现之一，在其他条件相同的情况下，可以把保价作为是否装车的衡量标准。这样可以做到行包配装的进一步公平，同时也可以促进保价收入。公式(8)中的四种权重在具体使用时可根据要求不同而作相应的比例浮动。表1  行包分类优先级优先级（rij）行包种类名称优先级（rij）行包种类名称12抢险救灾物资6滞留始发行李11急救药品5当日始发行李10误运行包<3

13、60; 编程实现 铁路各个客运车站分布距离相对比广泛，操作人员的水平参差不齐，这就要求软件的可靠性和简单易操作性必须要强。“铁路行包管理系统”开发工具采用的是Delphi 7.0，数据库采用的是Microsoft公司的SQL Server 2000。3.1  数据库设计 在行包配装算法中主要用到车次信息、停靠站信息、行包信息和行包种类优先级信息等。车次和车次停靠站是两个基础数据信息，这两个表的字段定义如表2 和表3所示。是行包配装的重要依据。表2  CCB车次信息表字段名类型中文说明TrainNumberVarchar(10)车次StartStationVarchar(16

14、)始发站ArriveStationVarchar(16)终到站ArriveTimedatetime到站时间StartTimedatetime发车时间UseTimeInt运行时间DistanceInt里程WeightInt载重重量CapabilityFloat车厢容积表3  TKZB停靠站信息表字段名类型中文说明TrainNumberVarchar(10)车次StationNameVarchar(16)站名StationSerielInt站次ArriveTimedatetime到站时间StartTimedatetime发车时间RunTimeInt运行时间RunDayInt运行天数Dis

15、tanceInt里程CrossLBoolean中转站标志表2 和表3的数据可以从铁路管理信息系统（TMIS）的客运制票数据库服务器中导出，铁路局下面的每个车站直接导入使用。行包信息表的字段定义如表4 所示。行包信息表中包括始发货物和中转货物。表4：XBXX行包信息表由约束条件公式(3)可知，满足到站装车的条件有两种，一是(Di ÎSi)；二是(DiÏS直达 && min D (Di, Ti)；第二种情况计算货物装载车次到站最短距离（CalculateMinDis）函数的实现相对复杂一些，但此函数是属于图论中求两点之间最短路径的问题。为了简化此函数的算法，在停

16、靠站表（TKZB）中添加了一个中转站标志（CrossL）字段，有了此项将大大降低程序的复杂度和提高函数的处理速度。部分程序代码如下：CreatTempTable(#TKZB_T);  / 创建停靠站临时表CreatTempTable(#XBXX_T);  / 创建行包信息临时表 AdoQuery1.sql.clear;         AdoQuery1.add(insert into #TKZB_T (select * from TKZB where TrainNumber =”当前车次”);

17、         AdoQuery1.ExeSql;   / 将满足( Di Î Si )条件的到站添加到停靠站临时表中CalculateMinDis (当前车次);   / 将满足(DiÏS直达 && min D (Di, Ti)条件的到站添加到停靠站临时表中 AdoQuery1.sql.close;AdoQuery1.sql.clear;       

18、60; 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时将用到行包类别、货物存放时间、到站里程和保价金额。其中货物存放时间可根据制票时间求得。部分程序代码如下：AdoQue

19、ry1.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进行排序3.2.3  根据约束条件剔除多出的行包 约束条件公式(4)是在生成装成单时必须要考虑的项。目前在一些站由于每一个行包的体积不能准确给出，所以