详情

原文传递铁路车流分配优化模型与拉格朗日松弛算法求解研究

论文题名：	铁路车流分配优化模型与拉格朗日松弛算法求解研究
关键词：	铁路货运;铁路车流组织;运输需求匹配;车流分配优化;拉格朗日松弛算法
摘要：	随着我国高速铁路网的建设与运营，既有铁路通道中部分客流逐步向高铁转移，使得既有线货运能力不足的局面得到了一定的缓解，为铁路运输部门优化运力资源配置、铁路货运开发更多的铁路产品提供了先决条件。在新的路网环境下铁路车流分配及车流径路需要结合点、线能力进行统筹优化，实现线路能力与运输需求匹配。此外，近年来货物运输市场竞争日益激烈，铁路车流结构变动幅度较大、变化速度加快，故而铁路车流分配方案也需要做到可以实时调整，以便于车流径路方案的短周期更新。　　本文借鉴多商品网络流思想、结合我国铁路运输组织特点研究铁路网车流分配优化模型及求解算法。论文研究一方面进一步完善铁路车流分配优化模型和求解算法方面的理论研究，为铁路运力资源优化配置、车流径路方案的短周期的调整提供一定的理论基础;另一方面也为改善运营组织方案、铁路网投资规划提供一定的理论指导和参考依据。论文研究工作主要包括如下几个部分: 　　(1)阐述铁路车流分配及车流径路相关的基础理论。包括概括车流分配、车流径路的内涵以及影响因素;分析铁路车流径路方案与货物列车编组计划之间的关系;归纳总结铁路车流优化分配方法。　　(2)研究符合单支车流不可以拆分原则的铁路车流分配优化问题。首先基于单支车流不可以拆分运输的要求，结合多商品网络流思想建立了符合单支车流不可拆分原则的铁路车流分配优化模型(RCF)。然后，针对可能出现的不可行流问题借鉴虚拟弧和剩余不可行流思想，通过设置超级弧段的方式处理无法满足的运输需求，进而提出了考虑不可行流问题的铁路车流分配优化改进模型(RCF-modified)。最后通过算例验证最终构建的改进模型可以有效进行铁路车流的优化分配，即模型优化结果可以直接获取路段上流量的分布以及所有车流的走行径路;当出现不可行流时模型可以进行有效处理，在保证车流损失最小的同时实现不可行流精确计算和定位。　　(3)分析并改进既有铁路车流树形径路优化模型。首先分析铁路车流的树状径路结构特点以及形成机理、介绍既有的铁路车流树形径路优化模型(C-RCFT)。该模型是一个非线性数学规划模型，其目标函数及约束条件中包含的高阶项极大增加了模型的求解难度。然后，通过引入两组新的变量将原模型的变量进行了等价替换，提出了一个铁路车流树形径路优化改进模型(C-RCFT-modified)。最后通过算例验证了改进模型的有效性。　　(4)在研究内容(3)的基础上针对改进后模型的优化结果仍然无法直接获取车流走行径路的局限性，结合多商品网络流思想提出了一个具有树状路径结构特点的铁路车流分配优化新模型(RCFT)，该模型是一个混合整数规划模型。模型在符合单支车流径路唯一的基础上，还满足同一终到站的车流具有“合而不分”的树状特点。类似地，针对不可行流问题通过引入超级弧和超级变量的方式对该模型进行了改进并提出了改进模型(RCFT-modified)。最后，通过算例验证该改进模型的优化结果可以同时获取弧段的流量分布和每股车流的走行路径;同一到站车流的走行路径呈树状样式;对不可行流问题可以进行有效处理和精确定位。　　(5)针对研究内容(2)和(4)中提出的两个具有铁路运输组织特点的铁路车流分配优化混合整数规划模型分别设计了拉格朗日松弛启发式算法进行求解。首先均通过引入拉格朗日松弛乘子向量松弛掉原模型中的点、线能力约束得到松弛问题，进而为降低求解难度将松弛问题分解为多个容易求解的子问题，并采用传统的次梯度优化算法求解拉格朗日对偶问题更新乘子并得到原问题的下界。在上界求解方面，结合两个模型特点分别设计了启发式算法进行解的可行化并得到上界。特别地，针对符合单支车流不可以拆分原则的铁路车流分配优化模型(RCF-modified)，基于变量之间的逆推关系和车流排序设计了可行解的启发式求解方法;针对具有树状径路结构的铁路车流分配优化模型(RCFT-modified)则基于树状径路约束、变量之间逆推关系和车流排序设计了具有树形结构的可行解的求解方法。最后的算例分别说明了本文设计的拉格朗日松弛启发式算法可以有效求解所构建的模型，且通过设置解的误差范围实现了计算质量和计算时间的较好折中，有利于实现车流分配和径路方案的实时调整。
作者：	温旭红
专业：	系统分析与集成
导师：	林柏梁
授予学位：	博士
授予学位单位：	北京交通大学
学位年度：	2016
正文语种：	中文