1 铁路网车流径路优化模型及算法研究

车流径路选择的优劣，将直接影响到整个铁路网的运输效率和效益i 。

对铁路既有货运产品列车径路的优化问题，就是在给定的空间内，将O-D 车流更科学的分配到具体的铁路网络上，在保证符合规定径路及通过能力的前提条件下，使车流输送所消耗的广义费用指标最小，费用指标包括运输距离、运输时间和运输成本等综合性指标。

在此，以直接应用于铁路列车径路优化调整为目的，设计了路网车流径路优化模型，采取更适用且有效的求解方法，使路网车流能够快速、有效的进行分配和调整，以提高铁路货物运输工作的效率。

1、路网的数学描述将铁路网的分界点和线路抽象为网络中的节点和有向弧，并保留二度以上的节点。

这样铁路运输网络可以表示为G =（V ，E ，W ，B ），其中V 表示路网上相关车站集合，E 表示有向弧集，E ={e ij |节点i 与j 相邻}，W 表示有向弧上的广义费用（包括时间消耗、运输距离和运输成本三部分），B 表示有向弧的能力约束集。

同时，假设任意两个节点间的车流量是完全确定的；各节点的能力均能适应任意车流强度的要求，车流途经各区段的可利用能力也均已确定；对于具有唯一O-D 的某支车流，其所有组成必须具有共同的径路。

2、变量及相关参数的定义从节点i 始发、终到节点j 的车流，可能的径路集合为{1,2,...,(,)}k ij ij R k i j ρλ==（一般将G 中节点i 与j 之间的K -短路作为允许径路而形成R ij ），k ij ρ表示从i 点到j 点的第k 短路。

定义弧-路关联矩阵mk ij m i j k a ⎧=⎨⎩1 如果第条弧在到的第短路上 （1）0 否则从节点i 始发、终到节点j 的重车流量记为n ij ，定义0-1决策变量kij ijn i j k x ⎧=⎨⎩1 如果车流选择到的第短路（2）0 否则3、模型的建立 （1）目标函数以所有重车流在路网上耗费的时间（车小时）最小为目标，则有1min k kij ij ij ijZ n T x =∑∑（3）式中，k ij T 为重车流n ij 选择第k 条径路时的时间消耗。

以所有重车流在路网上走行距离（车公里）最短为目标，则有2min k k ij ij ij ijZ n L x =∑∑（4）式中，kij L 为重车流n ij 选择第k 条径路时的走行距离。

以所有重车流在路网上发生的费用（运营成本）最少为目标，则有3min k k ij ij ij ijZ n C x =∑∑（5）式中，kij C 为重车流n ij 选择第k 条径路时产生的单位运量成本。

最优径路就是使得总车小时、总车公里和总运输成本三者达到综合最优的径路。

这里所指的综合最优包括以下含义：①综合最优的径路方案，可能对其中某个单独的子目标来讲，并不是最优的，但对综合目标来讲则是最优的。

这也说明三者的综合最优需要一定的方法进行评价和确定。

②综合最优是对于整个路网中所有不同O-D 车流的径路选择上的整体最优，而对于子目标是分别按照一定的径路进行比较确定的。

从整体上考虑时，则需要达到径路总体上的综合最优。

可见，综合最优是关于各子目标之间、各条径路之间、不同O-D 车流之间，以及车流与径路之间相互匹配等四个方面的协同优化。

（2）约束条件①共同径路约束。

对于铁路运输来说，一支车流不宜拆分成若干支车流运行，故对于任意O-D 流，有下列的径路唯一性约束条件。

=1 kijkx∑（6）②能力约束。

所有经弧em 的车流对能力的占用总量不应超过em 提供的能力。

mkk ijij ij m ijn ax B ≤∑∑（7）式中，B m 为弧e m 提供的能力上限。

（3）模型的整体结构根据上述分析，可得到车流径路多目标规划的数学模型 CFP1min k kij ij ij ijZ n T x =∑∑2min k k ij ij ij ijZ n L x =∑∑3min k k ij ij ij ijZ n C x =∑∑s. t.=1 ,kijk xi j ∀∑mk k ijijij m ijn ax B m ≤∀∑∑{0,1} ,,kij x i j k ∈∀应说明的是，对于给定的路网（V ，E ，W ，B ）和车流O-D 矩阵[n ij ]，当存在路网“瓶颈”时，由上述约束条件构成的解空间会出现空集的现象，使得模型无解。

对此一般的处理方法是舍弃某些O-D 流，同时对每一支车流设置一条虚拟径路00kij ij k ρρ=(,)，并设其对应的消耗0()ij W L 、0()ij W T 和0()ij p W E 均为一个充分大的正数，而与之对应的B m 为0。

这样，对给定的路网结构和任意车流矩阵，总可以保证模型的解空间不为空，从而可以得到径路优化选择的多目标线性规划模型M1。

M1 31.()k pi j p Z o p tZ x =⎧⎫⎪⎪=∈Ω⎨⎬⎪⎪⎩⎭式中，Ω为M1的解空间。

若在M1的最优解中有01ijx =，则说明n ij 由于运能的原因无法送达。

4、模型的求解 （1）求解方法采用线性加权和法。

线性加权和法是一种基本的评价函数法，它根据子目标在模型中的重要程度，分别赋予其一个权数，并把这个权数作为子目标的系数，然后把这些带系数的目标相加构造成评价函数，对评价函数求极小值，其最优解即为原多目标规划极小化问题的解。

对于模型给定一组与子目标p Z 对应的非负数(1,...,)p p P ω=，其中p ω代表相应目标p Z 在模型中的重要程度，p ω越大表示p Z 在模型中越重要。

将(1,...,)p p Z p P ω=求和并做出评价函数，极小化该函数后进行求解，具体步骤如下：STEP 1：给出权系数。

按目标(1,...,)p Z p P =在模型中的重要程度，给出一组对应的权系数1,...,p ωω（要求10,1, (1)p p p p P ωω=≥==∑和）。

STEP 2：极小化线性加权和函数。

通过线性加权和评价函数把模型归为求解数值极小化问题1min () Pp p x Xp Z x ω∈=∑（8）得到最优解*x ，当0p ω>时*x 为模型的有效解，当0p ω≥时*x 为模型的弱有效解。

（2）模型的转换将模型CFP 按照线性加权和法转换为数值极小化问题。

不难发现，模型CFP 中的目标函数可表示为112233123()k k k kij ij ij ij ij ijZ Z Z n x T L C ωωωωωω++=++∑∑当i 、j 点的车流经过第k 条径路时，k ij T 、k ij L 、k ij C 均为定值，考虑到权系数1ω、2ω、3ω是事先给定的常数，故可引进广义费用参数k ij λ，其定义为123 k k k k ij ij ij ij T L C λωωω=++（9）这样，多目标规划模型CFP 可转化为如下单目标求数值极小化问题的模型 CFP1min k k ij ij ij ijn x λ∑∑s. t.=1 ,kijk xi j ∀∑mk k ijijij m ijn ax B m ≤∀∑∑{0,1} ,,k ij x i j k ∈∀（3）权系数的确定采用专家打分法。

专家打分法是一种凭借专家经验、结合统计结果确定权系数的方法。

首先挑选一批对所研究的问题有充分见解的L 位专家，请他们各自独立地对问题中要确定P 个事项S p （p =1，…，P ）按重要程度分别给出相应的权系数。

设第q （q =1，…，L ）位专家所提供的权系数为1q ω，2q ω，…，pq ω，汇总这些数值后可列出权系数表。

表中最后一行是L 个权系数均值11,1,,Lp pq q p P L ωω===⋅⋅⋅∑。

表中最后一列是各专家所提供的权系数和权系数均值的偏差211() 1,2,,1Pq pq p p D q L L ωω==-=⋅⋅⋅-∑ 设给定允许误差0ε>，检验各方差估值，若方差估值的最大者不超过规定的ε，即1max{}q q LD ε≤≤≤，说明各专家所提供的方案没有显著的差别，是可以接受的。

针对模型涉及到的时间权系数1ω、运距权系数2ω和费用权系数3ω，聘请有经验的工程师和专家学者根据各人的经验和判断，提供pq ω的值如表1所示。

从表1可见偏差均小于0.0005，各专家提供的方案相近，权系数结果是可以采纳的。

表1 专家法确定的权系数1ω2ω3ω偏差 专家1 0.35 0.33 0.32 0.000 1 专家2 0.32 0.34 0.34 0.000 1 专家3 0.33 0.35 0.32 0.000 1 专家4 0.32 0.37 0.31 0.000 2 专家5 0.33 0.31 0.36 0.000 4 均值0.330.340.33（4）CFP1模型的求解CFP1是0-1规划模型，属于NP 问题，采用启发式算法。

在此设计了CFP1模型的阻尼系数法，其基本思路是：根据O-D 数据对路网进行流量分配的常用方法是最短路算法，按照O-D 对之间的最短路将流量分配到对应径路的各区段上。

但由于路网中各区段的能力是有限的，有的区段能力不足无法负担过多的流量，因此考虑在区段能力有约束的情况下分配O-D流量。

阻尼系数法对能力紧张区段加入阻尼系数r∆，则该区段的里程长度变为原来的r∆倍，从而改变原有最短径路，使O-D流量重新分配到其它能力剩余的区段。

具体步骤如下：STEP 1：按照最短路分配O-D流量，计算各区段所获得的流量；STEP 2：根据区段的能力负荷，对比上一步分配的流量，检查是否能力不足；STEP 3：对能力不足的区段增加阻尼系数r∆，使该区段虚拟里程增加；STEP 4：在加入阻尼系数的路网上重新进行流量分配；STEP 5：检查相关区段的车流量是否符合能力利用的预期（包括负荷大于能力或负荷远小于能力）；STEP 6：若区段车流量符合能力利用的预期，则结束并输出方案；否则，返回STEP 3。

（5）算法复杂度分析主要分析算法的时间复杂度。

一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用()T n表示，若有某个辅助函数()f n，使得当n趋近于无穷大时，()/()T n的同数量级函数，记作T n f n的极限值为不等于零的常数，则称()f n是()=，称(())T n O f n()(())O f n为算法的渐进时间复杂度，简称时间复杂度。

在此利用最短径路算法进行流量分配，从而实现模型的求解。

对于由n个节点构成的路网而言，计算从一点到另一点的最短径路，其时间复杂度为平方阶2O n。

本()模型需要计算路网上所有节点之间的最短径路，因此算法的时间复杂度为立方阶3()O n。

需要说明的是，该结论以路网相邻节点间都有线路连通为前提，而实际路网并非如此，所以上述结果仅为模型时间复杂度的上界。