基于最小费用的高速铁路值乘区段集合模型研究

摘 要：高速铁路乘务计划编制的优劣直接影响着乘务工作的效率以及经济效益。该文研究了乘务交路计划编制过程中乘务交路的组成及其费用计算方法，提出了以便乘费用而非值乘费用计算各值乘区段的相关费用，设计了求解值乘区段集合覆盖问题的具有双重信息素和启发式信息的蚁群优化算法。

关键词：乘务交路 值乘区段 集合覆盖 最小费用

中途分类号：U292.8 文献标示码：A 文章编号：1674-098X（2014）04（a）-0012-02

1 问题的提出

值乘区段是按照列车运行图规定的列车在各站的停车情况和动车组司机换乘站的分布，将列车运行线或动车组交路划分为动车组司机能够连续值乘的最小片段。从运营成本等经济角度，有必要从乘务计划角度分析动车组司机的运用费用。

2 运用费用分析

动车组司机完成乘务交路值乘的过程分为出勤、值乘、换乘、值乘/便乘、退勤等部分，且都存在一定的费用，故将乘务交路费用分为以下几部分。

2.1 出、退勤费用

出、退勤费用主要包括动车组司机一次出乘的固定报酬和担当值乘任务所需耗材等支出的相关费用，其取值通常为定值，用常量mb表示。

2.2 值乘费用

对某一乘务交路而言，动车组司机担当该交路值乘任务的费用与值乘时间成正比。若值乘时间为tzc，单位时间值乘费用为mzc，则值乘费用为mzctzc。

2.3 换乘费用

乘务交路中的换乘涉及换乘次数与换乘时间两个问题，本文定义了换乘基本费用和无效换乘费用两个概念。换乘基本费用是换乘次数产生的相关费用。若乘务交路i中的换乘次数为ki，一次换乘基本费用为mhc，则乘务交路i换乘基本费用为kimhc。但在实际换乘中，乘务员实际换乘时间与换乘时间标准存在差值。若乘务员某次换乘实际时间为，乘务员换乘时间标准为thc，单位时间无效换乘费用为，则引起的无效换乘费用为（）mwx。

2.4 便乘费用

便乘费用是在便乘过程中产生的费用。设便乘时间为tbc，单位时间便乘费用为mbc，则便乘费用为mbctbc。

乘务交路i的总费用mi=mb+mzctzc+kimhc+

mwx+mbctbc （1）

其中，式中mzc、mwx、mbc均与时间有关，故可以将mwx、mbc转化为与mzc相关的函数。

令α为mwx相对于mzc的系数，β为mbc相对的mzc系数。

mi=mb+mzctzc+kimhc+αmzc+

βmzctbc （2）

若将可行乘务交路i中所有值乘区段费用均以便乘费用计算，则乘务交路i的费用可表示为：

=mb+kimhc+αmzc+

βmzcti （3）

则所有乘务交路的总费用为：

minZ= （4）

式中n―乘务交路总数；

xi―0-1决策变量，当乘务交路i被选入最终解时取1，否则取0。

3 优化目标和约束条件

3.1 优化目标

动车组司机是完成高速铁路运输生产任务的主体，计划使用的动车组司机（即覆盖所有值乘区段的可行交路数量）数量越多，相应的费用越高，故选择以最小化覆盖所有值乘区段的乘务交路的总费用最少作为优化目标。

3.2 约束条件

（1）在可行乘务交路中，接续的值乘区段满足空间约束，即前一值乘区段的终点和后一值乘区段的起点为同一车站。

（2）在可行乘务交路中，当接续的两个值乘区段不属于同一动车组交路时，应满足时间约束，即前一值乘区段的到达时间与后一值乘区段的发车时间满足动车组司机换乘时间标准。

（3）动车组司机一次连续作业时间满足机车乘务员工作和休息时间标准。

4 模型的建立

在上述分析的前提下，建立以乘务交路总费用为最小为目标的值乘区段集合覆盖模型如下：

minZ= （5）

≥1 j=1，2，3…p （6）

式中 n―乘务交路总数；

xi―0-1决策变量，当乘务交路i被选入最终解时取1，否则取0。

P―值乘区段的数量

―可行交路i的总费用

aij―0-1变量，当可行乘务交路i包含值乘区段j时为1，否则为0。

式（6）表示每一值乘区段至少属于一个乘务交路。

5 算法设计

该文蚁群算法的关键参数和主要操作如下。

5.1 解构建图的表示

解的构建图由所有值乘区段的结点和若干个原点组成，原点是虚拟的共同点，作为乘务交路的起点和终点，被复制为乘务交路的数目。

5.2 解的构建

所有蚂蚁均从某一原点出发，首先根据概率选择乘务交路的起始结点，并记录起始值乘区段的出发车站As，若出发车站为乘务基地，则令As=O，否则令As=1。根据概率选择下一个值乘区段结点，若某名动车组司机累计工作时间未达到相关时间标准，继续选择下一结点，直至接续一系列的值乘区段后返回该原点，形成一个回路（即乘务交路），记录乘务交路的终止车站Ae。如果若终止车站为乘务基地，则令Ae=0，否则令Ae=1，若乘务交路满足AsAe=O，则表示得到了一个满足相关时间和地点约束的乘务交路，否则采用回溯策略，使乘务交路满足AsAe=O。蚂蚁重复该过程进行解的构建，当所有的值乘区都被选择进入相应的乘务交路时，表示完成解的构建过程。

5.3 信息素的表示、初始化及更新

1）信息素的表示

该文同时记录解构建图中所有路径的信息素τij和全部结点的信息素τi。其中，τij是蚂蚁处于值乘区段结点i时所接续的是值乘区段j的期望程度，而τi是指当蚂蚁处于原点时，选择值乘区段j作为下一个乘务交路起始结点的期望程度。

2）信息素的初始化

在蚁群算法迭代前，各路径及值乘区段结点上的信息素初值按照式（7）和（8）确定：

τij（0）= （7）

τi（0）= （8）

3）信息素更新原则

在本蚁群算法中，只有迭代最优蚂蚁（即构造出本次迭代最优解的蚂蚁）才被允许释放信息素，在每次迭代后各路径及结点上信息素的更新原则表示为：

τij（n+1）=ρτij（n）+τij （9）

τi（n+1）=ρτi（n）+τi （10）

式中ρ为信息素的挥发系数，0

设λib为第n次迭代的最优解，fib为λib的目标函数值，则τij和τi可由式（11）和（12）确定：

τij= （11）

τi= （12）

其中，Starti为0-1变量，当值乘区段结点i在最终解中作为某个乘务交路的起点时取1，否则取0。

5.4 选择策略

1）当蚂蚁r所处结点i并非原点时，选择下一个值乘区段结点j的概率公式如下：

= （13）

其中，启发式信息ηij按式（14）取值：

ηij= （14）

式中Dij为0-1变量，当两个值乘区段所属动车组交路相同且为紧接续时为1，否则为0。

2）当蚂蚁r所处结点为原点是，选择值乘区段i作为下一个乘务交路起点的概率为

=（15）

其中，selectdi为0-1变量，表示值乘区段i是否已被选择。

ηi可按式（16）下式取值：

ηi= （16）

式中为值乘区段i的结束时间，为当前剩余值乘区段的最早结束时间；α为控制系数；Nuf为尚未被选入热河乘务交路的值乘区段的数量；N为值乘区段的总数。

6 算例分析

该文以现行的京沪高铁部分动车组北京南-济南西列车运行计划求解具有最小费用的乘务交路段集合，其基础数据.

在算例中，动车组司机换乘时间标准为15 min，间休时间标准为120 min，连续工作时间为300 min，一次出乘工作时间标准为480 min。采用C语言编程，在Intel Core5，CPU 2.66 GHz，内存2GB的计算机上执行20.2712 s后，最终共得到16个乘务交路，结果为表2。

7 结语

该文采用的集合覆盖模型表示乘务交路集合覆盖问题需要对可行乘务交路的费用进行明确的表示，在计算费用过程中，以便乘费用而非值乘费用计算动车组司机担当所有值乘区段的工作费用时，可以建立标准集合覆盖模型。在求解过程中，将问题转化为在网络图中寻找至少覆盖所有结点一次的最小费用链问题，经验证取得较好效果。

参考文献

[1] 赵鹏.高速铁路动车组和乘务员运用的研究[D].北京：北方交通大学，1998：62-67.

[2] 陈华群.动车组运用计划编制系统相关问题研究[D].西南交通大学硕士学位文，2007.

[3] 王莹，刘军，苗建瑞.客运专线乘务交路计划编制的优化模型与算法[J].铁道学报，2009，31（1）：15-19.