铁路编组站布局的双层规划方法研究

2011-07-13彭其渊

铁道运输与经济 2011年8期

殷勇，彭其渊

(西南交通大学交通运输与物流学院，四川成都 610031)

铁路特编点组和站自的然合集理散布规局律是，指正在确铁地路选网择上编按组车站流的位置，经济合理地确定其规模[1]。由于路网上编组站之间的分工相互关联，即每一处编组站的建设(新建或改扩建)，都会对路网上车流改编方式产生影响，因此编组站布局不能就点论点，而应该从路网整体优化的角度加以考虑。长期以来，由于缺乏有效的优化方法，现有的编组站布局决策基本上立足于经验判断。通过分析当前我国铁路编组站布局存在的主要问题，结合我国铁路车流的特点和变化，对未来编组站的合理布局及其发展方向进行了探讨[2-3]。近几年，随着车流组织研究的进一步深入，国内部分学者运用现代优化方法对编组站布局问题进行了研究，如尝试建立编组站布局规划优化模型[4]，研究技术站布局的双层规划优化方法[5]。因此，探讨运用双层规划方法提出编组站布局问题，建立编组站布局双层规划模型及求解算法，具有积极的意义。

1 编组站布局问题的描述

随车流量的增长及车流结构的变化，需要对路网编组站的位置和规模进行必要的调整，以适应车流不断变化的需求。一般而言，编组站布局问题可以描述为，在有限资金投入的条件下，选择最优投资策略，通过改进现有编组站的布局，包括新建编组站、扩大或减小现有编组站规模等，使路网中车流组织达到最优。编组站布局问题可以从建设投资费用和车流组织费用两个方面考虑。

编组站的建设投资费用主要取决于新建或改扩建编组站的建设规模；路网车流组织费用是对于给定的编组站布局方案，车流组织实现的最优费用。一方面，投资者通过投入大量资金，采用新建或改扩建等措施对既有编组站布局进行调整，以满足车流不断增长及其组织优化的需求；另一方面，运营部门通过调节路网上的车流组织方式，以适应给定的编组站布局状况。

编组站布局问题可用双层规划加以描述：上层规划表示决策者为了达到车流组织最优的目的而采取的最优投资策略，下层规划代表给定编组站布局方案条件下的车流组织优化。同时假设：对于任意给定的上层决策变量 (编组站布局方案)，都可以从下层规划中求得一个惟一的最优车流组织方案。上层决策通过设置不同的编组站布局方案影响下层决策，因而限制了下层决策的可行约束集，而下层决策行为又会通过车流组织方案对应的费用影响上层的目标函数。

2 编组站布局的双层规划模型

2.1 上层规划模型

对于一个给定的路网 (V，E)，这里 V 是所有备选编组站的集合，E 为路网上的边集。设 k 是路网上的某个备选编组站，引入 0-1 变量 xk，定义为：

首先，编组站的选择是有条件的，主要考虑在路网的交汇处而且有大量车流集散。因此，处于路网主要干线的交汇处而且有大量到发车流的节点构成备选编组站集合V，同时为减少可能的组合方案数量，可结合专家经验将 V 分为两类，即 V＝{V1，V2}。其中，V1表示必选编组站集合，相应的约束为：

V2表示可能设为编组站的集合，相应的约束为：

对于被选设的编组站，还需进一步确定其新建或改扩建方案。设 k 站被选设为编组站，相应的新建或改扩建方案有 P (k) 个 (包括维持既有编组站规模)，引入第2组 0-1 变量 xkp，定义为：

在路网上某个特定地点，若新建或改建既有编组站，可选择的方案很有限。我国铁路主要推荐的站型是：单向一级三场、二级四场、三级三场和双向三级六场，其他站型都是在此基础上派生出来的，因此 P(k) 是有限的。就 k 站而言，虽然有 P (k)个方案，但是在规划期内这些方案是互不相容的，且当 xk＝1 时，必有一个方案被选择，因此可以用方案互不相容约束来表达。

以编组站建设投资费用和路网上车流组织费用之和最小为目标函数，建立上层规划模型为：

式中：M 为规划年数；λ 为贴现率；β 为车小时的单价；Y (X ) 表示路网上的车流组织费用，其值为决策变量 X 的函数，不同的编组站布局方案，对应不同的车流组织费用。

2.2 下层规划模型

下层规划是针对不同的编组站布局方案，求相应路网上的车流组织优化问题，即列车编组计划(简称TFP) 问题。关于 TFP 的研究，特别是技术站单组列车的编组计划，很多学者和专家都已进行了长时间的系统研究和探索，得出了一些重要结论，建立了较为完善的规划模型。其中比较著名的有混合整数规划模型、线性 0-1 规划模型、二次 0-1 规划模型、网络优化模型、有利去向模型、阶跃函数模型及高次 0-1 规划模型等[6-8]。

研究车流组织优化问题，考虑其编组站布局规划方案是变化的，但对于给定的一组编组站布局方案，则与原 TFP 问题完全一致，借鉴TFP 的网络优化方法构建下层规划模型 (这里约定车流组织以给定的车流径路为前提)。

对于某一编组站选址和规模方案 X，其中编组站集 SX＝{s(1)，s(2)，…，s(n)}，全体可能的编组去向集 AX＝{a(i,j)：s(i),s( j)∈SX}，必开编组去向集，禁开编组去向集，改编能力UX＝{u(i)：s(i)∈SX}、编组去向车流下限VX＝{v(i,j)：a(i,j)∈AX}、编组去向数上限WX＝{w(i)：s(i)∈SX}、集结车小时CX＝{c(i,j):a(i,j)∈AX}、改编车小时消耗TX＝{t(i)：s(i)∈SX}、车流量FX＝{f (i,j)：s(i)，s ( j)∈SX}，车流径路LX＝{L(x,y)：x,y＝1,2,…, n}，编组去向集为Bx，则建立模型：

3 模型的算法研究

一般双层规划问题的求解都是非常复杂的，即使是很简单的双层线性规划问题也是NP-hard问题，不存在多项式求解算法[9]。求解双层规划问题的关键是找到反应函数的具体形式，对于连续变量情况，可以通过灵敏度分析方法得出变量之间的导数关系，继而可以利用泰勒展开式对反应函数进行近似求解[10]。本文建立的双层规划模型上层是一个离散变量的非线性优化，下层是一个大规模的组合优化，此时的双层规划问题更加复杂，用传统的数值算法很难求解。

遗传算法 (GA) 提供了一种求解复杂系统优化问题的通用框架，以其具有的并行搜索能力、自适应性和可直接应用等优点，适合于求解大规模任意目标函数的全局优化问题。但简单的遗传算法在许多情况下不是十分有效，容易产生早熟现象及局部寻优能力较差等问题，而将遗传算法与问题的特有知识集成到一起，或者在遗传算法中融合其他算法的思想和方法，构成一种混合遗传算法，则求解性能有可能达到极佳[11]。一般有两种混合策略：①把遗传算法和原有算法有效结合，设计一个新的混合算法；②采用原有算法的编码或把原有算法中的一系列变换结合到混合遗传算法中。混合GA 最常见的形式是在 GA 典型的重组选择循环中嵌入一块附加的局部优化模块。结合本文的模型特点，将遗传算法与求解车流组织优化问题相结合，从而构造出适合求解编组站布局双层规划模型的混合遗传算法。

关于 Y (X ) 的计算，有关研究通过分析模型的不同特点，提出了多种有针对性的算法，除传统的以手工操作为主的绝对计算法和表格分析法以外，还成功地运用单纯形算法、分枝定界算法、拉格朗日松弛算法等进行计算机求解，并且发展了诸如有序组合树算法、网络拓扑变换法、二次0-1 规划法等。值得指出的是，20 世纪 80 年代以来，国内外学者运用现代新兴的智能优化方法，如遗传算法、模拟退火、禁忌搜索及人工神经网络等方法解决车流组织优化问题，在实现大规模、多约束、非线性车流组织优化方面表现了良好的性能。编组站布局双层规划模型的混合遗传算法框架如图1所示。按照模型的详细计算过程[12]，根据计算结果并结合其他的编组站布局影响因素，提出我国铁路编组站布局的调整方案。

4 结束语

编组站的合理布局与分工，对提高铁路运输生产效率和水平、确保路网的安全畅通、加速机车车辆周转、缩短货物送达时间、提高经济效益和社会效益、促进铁路运输业协调可持续发展十分重要。通过分析建立模型，将求解车流组织费用的计算模块与 GA 结合，构建了求解编组站布局双层规划模型的混合遗传算法，适用于实际路网中的编组站布局问题决策。研究结果表明，应用双层规划方法解决编组站布局问题是合适的，建立的编组站布局双层规划模型能够贴切地描述编组站布局方案和车流组织优化的关联关系。