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

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

　　论文关键词：铁路车站  行包  装配  编程实现

　　论文摘要：行包装配是铁路行包的重难点之一，在铁路行包中出现的大部分问题均是由行包装配不当引起的。影响行包装配的因素较多，通过对铁路行包装配的流程和影响行包装配的主要因素进行分析，建立了铁路车站行包装配问题的条件约束模型，提出铁路行包装配的目标函数，最后给出了铁路行包装配问题的编程实现方法。

　　铁路行李包裹运输（以下简称行包运输）是利用铁路客运设施，以随挂旅客列车的行李车为载体的一种运输形式^[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  停靠站装卸能力约束条件

                ｋ=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  编程实现

　　铁路各个客运车站分布距离相对比广泛，操作人员的水平参差不齐，这就要求软件的可靠性和简单易操作性必须要强。“铁路行包系统”开发工具采用的是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）函数的实现相对复杂一些，但此函数是属于图论中求两点之间最短路径的问题。为了简化此函数的算法，在停靠站表（TKZB）中添加了一个中转站标志（CrossL）字段，有了此项将大大降低程序的复杂度和提高函数的处理速度。部分程序代码如下：

　　CreatTempTable(#TKZB_T);  // 创建停靠站临时表

　　CreatTempTable(#XBXX_T);  // 创建行包信息临时表

　　AdoQuery1.sql.clear;

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

         AdoQuery1.ExeSql;   // 将满足( D_i Î S_i )条件的到站添加到停靠站临时表中

　　CalculateMinDis (‘当前车次’);   // 将满足(D_iÏS_直达 && min D (D_i, T_i))条件的到站添加到停靠站临时表中 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)这一项在实际编程时可根据实际的体积数据进行处理，主要是作为参考。停靠站装卸能力约束，如公式(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

【铁路行包配装算法研究与实现】相关文章：

FFT算法的研究与DSP实现03-07

指纹预处理算法与实现的研究03-07

图像拼接算法及实现03-03

采用快速导向滤波的暗通道先验去雾算法的研究与实现03-21

图像处理中的模糊算法及实现03-13

网页模糊归类算法的应用与实现03-19

基于分布式算法和FPGA实现基带信号成形的研究03-18

计数查找算法的研究11-22

3-DES算法的FPGA高速实现03-20