铁路车站取送车作业图论模型及算法分析.pdf

《铁路车站取送车作业图论模型及算法分析.pdf》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、第31卷第1期华东交通大学学报Vo1．31NO．12014年2月JournalofEastChinaJiaotongUniversityFeb．，2014文章编号：1005．0523(2014}01．0102—06铁路车站取送车作业图论模型及算法分析郭垂江，雷定猷(1湖南铁路科技职业技术学院运输管理学院，湖南株洲412000；2．中南大学交通运输工程学院，湖南长沙410075)摘要：在设定条件下，以作业点(车站)间机车走行时间为权，把铁路车站取送车作业优化问题转化求解哈密尔顿图最短路问题，设计动态规划法和c一节约改进算法分别进行求解，并举例比较2种算法的优缺点，提出了两种算法

2、的应用范围。动态规划法计算次数少、能得到最优解，且可选择的方案多，适用于Ⅳ规模较小情况；C一节约改进算法虽可能只得到满意解，但能显著降低计算复杂度，适用于Ⅳ规模较大情况。把车站作业点的3种布置形式统一为树枝形，不会影响算法的有效性。关键词：铁路车站；取送车作业；哈密尔顿图；动态规划法；C一节约改进算法中图分类号：U291．2文献标志码：A合理安排货车取送车顺序，有助于加速机车车辆周转，压缩铁路货车在装卸车站的停留时间。为合理安排货车取送车顺序，提高机车车辆作业效率，我国相关领域的研究人员对其进行了一定的研究，并取得了阶段性的研究成果n。以前研究只针对某一种布置形式进行研究，没

3、有统一的模型及算法，而且计算复杂，所得到的解的可靠性也难以保证。在综合以前研究的基础上，针对作业点的数目，提出了相应的求解方法，以确保计算的准确性与复杂度的有机统一。1模型的建立货场和专用线是铁路车站的货物装卸作业地点，统称为作业点，按布置方式分为放射形、树枝形和混合形3类。结合铁路现场实际工作情况，设定如下条件：1)有1台调车机车作业；2)各作业点待送、待取车数已定；3)各作业点的距离或调车机车走行时间已知，确定去货场(专用线)的走行时间以货位中心线为准，且送车时间包括对货位时间，取车时间包括收集车辆时间在内。同一走行线往返机车走行时间相等。4)机车附挂车辆数量的多少对机车

4、在走行线的走行时间影响忽略不计。5)调机一批作业向各作业点取送车，规定经过各作业点仅1次，最后调机返回车站。研究目标是如何安排调车机车一批作业的取送车顺序，使其完成作业点的取送车任务所走行的总时问最小。如图1，v0为铁路车站或技术站调车场，～为铁路车站的装卸作业点，口为分路道岔辙岔心与辙收稿日期：2013-11．20作者简介：郭垂江(1980-)男，讲师，博士研究生，主要研究方向为运输组织优化。第1期郭垂江，等：铁路车站取送车作业图论模型及算法分析103岔心(或作业点、车站中心线)间的机车的走行时间。把问题构造成哈密尔顿图G=A，c】，如图1。图中={v0，，．．．，}表示调

5、机经过的作业点(车站或调车场中心)编号，A={=0，1，．．．，n，表示铁路走行线集合；t表示机车在对应段的走行时间，包括调机在纯走行时间及在作业点进行摘挂、对货位等作业所需要的时间，可通过写实法查定。将车站视作哈密尔顿图的出发顶点，每一个装卸作业点看作一个需要经过一次的哈密尔顿图顶点，如果找到恰好经过各个装卸作业点并回到车站顶点的一条回路，就得到一条哈密尔顿回路。哈密尔顿回路的权值为机车走行路线上的时间权值tⅡ总。由于作业点之间是互相连通的，此图是一个完备图，同时也是一个无向图，所以对于树枝形作业点构成的哈密尔顿图，其可行的哈密尔顿回路多达fⅣ一!个(Ⅳ是哈密尔顿图的顶点个

6、数)。V2图2哈密尔顿图图1树枝形作业点布置图Fig．2HamiltongraphFig．1Layoutofbranch—shapedoperationsites3求解方法哈密尔顿图最短路回路问题属于组合最优化问题，是典型的NP完全问题，当作业点规模较大时，很难得到精确解。本文提出当一批调车作业货物作业点较少时，选择动态规划方法得到最优解；当作业点较多时，利用c一节约改进算法得到满意解或最优解。3．1动态规划方法当作业点n较少时，利用动态规划方法求解是比较简便的。把第一个作业点起往下～作业点取送车和返回车站作为作业阶段，因此把整个取送车作业过程划分为rt个阶段。设s表示到达作

7、业点之前机车已完成取送作业的作业点(包括车站出发点)集合，则有Sc_V。因此，可选取，作为描述过程的状态变量，状态转移方程为s川=s十；决策为机车从作业点选择前往的下一个作业点，允许决策集合D)={I∈一，

8、s)}；P(，为最优决策函数，它表示从车站开始机车经由k个装卸作业点的s集到作业点的最短路线上紧挨着作业点i前的作业点；边界条件为=；最优值函数，为从作业点开始经由k个作业点的s集到作业点的最小机车走行时间，因此动态规划的递推关系为：，=啊一l，)+t](k=1，2，．．．，n；i：l，2，．．．，