【作者】 赵军；

【导师】 彭其渊；

【作者基本信息】 西南交通大学 ， 交通运输规划与管理， 2013， 博士

【摘要】 技术站是铁路货物运输网络中的1类关键的节点,它的作业效率直接影响着整个铁路货物运输的可靠性和服务水平。技术站的日常运输工作由编制各种类型的作业计划来组织和调度,本文利用现代数学规划理论与方法探讨优化编制铁路技术站作业计划理论体系中的几个关键的科学问题,包括配流问题、进路调度问题和编组调车问题,主要的研究工作如下：第2章探讨了配备有1台解体调机和1台编组调机的区段站的配流问题,该问题在于确定各列出发列车的编组内容及其车流来源,并调度各台解体和编组调机的任务,以使得各列出发列车满足满轴、正点和不违编的编组要求,且衡量配流效率的车辆在站总停留时间最小。本章首先借助于单机器调度问题的基于时刻索引变量的经典模型将该问题构建为1个囊括所有决策任务的混合整数线性规划模型,然后利用构建的模型的结构和探讨问题的特点提出了3个有效的求解算法,包括1个拉格朗日松弛算法、1个启发式算法和1个基于整数编码的遗传算法。以1个来源于实际的数值算例来测试了所提出方法的效果和效率,测试结果显示了所设计的求解方法都能快速地将实际问题求解到最优或近似最优,且它们的计算结果明显地优于由调度员在现场的实时决策环境中使用的基于先到先服务规则的经验方法找到的结果。第3章探讨了分别为到达列车的解体作业和出发列车的编组作业配备多台解体调机和多台编组调机的单向编组站的配流问题,该问题研究的是确定各列出发列车的编组内容及其车流来源,指派并调度各台解体和编组调机的任务,以使得各列出发列车满足满轴、正点和不违编的要求,各台调机任务不冲突。利用并行机调度问题的基于时刻索引变量的模型来建模调机的指派和调度,本章首先构建了该问题的1个以车辆在站总停留时间最小为目标的混合整数线性规划模型,该模型使用1个连接约束将列车组成问题和解编排序问题纳入同一个优化体系,然后根据问题的结构和特点设计了1个精确算法和2个启发式算法,其中,精确算法为CPLEX精确求解所构建的优化模型的求解方法,启发式算法包括1个拉格朗日松弛算法和1个有偏随机键遗传算法。1个切实且大型的数值案例被用来测试了所提出的求解方法的效果和效率,测试结果显示了所提出的精确算法和有偏随机键遗传算法都能在限制的时间内获得实际问题的最优误差不高于1%的近似最优解,且由所提出的求解方法找到的解都不差于由现场的经验方法找到的解。第4章探讨了具有两个改编系统且系统间存在车辆交换的双向编组站的配流问题,该问题在于确定各列出发列车和交换列车的编组内容及其车流来源,指派并调度各台解体和编组调机的任务,以使得各列出发列车符合开行规定,各列交换列车满足编组要求,且各台调机的任务不冲突。本章将该问题构建为1个以车辆在站总停留时间最小为目标且包含所有决策的混合整数线性规划模型,其中,有关调机运用的子问题采用并行机调度问题的基于时刻索引的经典模型进行建模。利用问题易被分解的特性,本章开发了2个有效的近似算法,包括1个使用所构建的优化模型的拉格朗日松弛算法和1个不使用所构建的优化模型的有偏随机键遗传算法。为了验证所提出方法对于实际问题的效果和效率,计算测试采用了1个切实且大型的数值案例。计算结果显示了所提出的有偏随机键遗传算法能够在不到100s内的时间内获得实际问题的接近最优的解,其最优误差接近1%,拉格朗日松弛算法也能在规定的计算时间末找到最优误差不高于3%的满意解,更为重要的是,它们的解明显地优于调度员采用的人工方法确定的解。第5章探讨了具有多类型的作业且作业问存在复杂约束的技术站进路调度问题,该问题在于为各项行车和调车作业同时指派并调度进路,以使得所有作业在时间和空间上都无冲突,且定义的作业间的一致性约束能得到满足。本章引入车间调度问题中的工作和活动的概念来描述调度作业,并定义可囊括所有的路径选项和有限的时刻选项的进路模式的概念来表示决策变量,进而将原本包含多项决策任务的进路调度问题转换为1个只需指派提前生成的进路模式给活动的约束指派问题。本章将所定义的约束指派问题构建为1个最小化总晚点和走行时间,且满足唯一性约束、一致性约束和相容性约束的0-1线性规划模型,在建模时间-致性约束和道岔相容性约束时,基于图论的极大关联技术被用来代替传统的两两关联技术,以加强生成约束的定界质量。本章还讨论了如何拓展标准约束指派模型,以使得它能满足更多的运营要求,且从1个单一的路径模型转换为1个复合的路径和调度模型,对于标准模型的不可行问题,提出了1个迭代算法通过求解有限个辅助模型来构造可获得可行解的候选进路模式集。最后,1个真实案例的计算结果显示了相比于两两关联技术,极大关联技术可极大地减少生成的约束数,且所提出的标准模型使用的动态列车-站线-指派策略在求解质量上优于车站调度员的经验方法使用的静态列车-站线-指派策略。第6章探讨了产生于技术站实时调度中的调车线受限的编组调车问题。给定待编车列和可使用调车线集合,该问题在于确定调车作业次数以及待编车列中的各个车辆在各次调车作业中的调动路径,以使得在不违背调车线的数量和能力约束的情况下,各列编成车列都能被实现为站顺的顺序,并需要最少的连挂钩数、调动车数、占用调车线数和溜放钩数。本章首先考虑了将1列待编车列编顺为1列编成车列的简单编组调车问题,开发了1类新的使用0-1矩阵编码编组调车方案的位串法,通过定义不同的调车线连挂原则,分别提出了1个连挂全部调车线的全线位串法和1个单独预留1条调车线给编成车列的留线位串法,1个包含迭代优化和局部搜索进程的两阶段迭代搜索算法被开发来实施这两个位串法,其中,第-阶段通过求解一系列的0-1线性规划模型来寻找需要的0-1矩阵,该矩阵再由第二阶段定义的搜索规则进行局部优化,最终获得的编组调车方案可按字典序优化拟定的连挂钩数、调动车数、占用调车线数和溜放钩数。本章还将拓展的全线和留线位串法运用于解决更具有挑战性的将多列待编车列同时组合为多列编成车列的批量编组调车问题。最后,切实的随机案例被用来体现了所提出的两个位串法都能有效地求解调车线受限的简单和批量编组调车问题,它们快速的计算时间准许将它们同时运用于解决大规模的问题实例。更多还原

【Abstract】 Technical station is a critical node in the railroad freight transportation network, and its operation efficiency directly influences the robustness and service level of the total railroad freight transportation. Nowadays, the ordinary transportation work of technical station is organized and scheduled by various types of operation plans. This thesis focuses on several important theoretical problems including the railcar allocation problem, the route scheduling problem and the assembly shunting problems for optimally establishing the operation plan of railroad technical station, our main research works are as follows:Chapter2investigates the railcar allocation problem at railroad district stations with single switch engine and single yard engine. The problem is to determine the composition of each outbound train, and schedule the task for each switch engine and yard engine, such that each outbound train satisfies the assembly requirements while the total dwell time of railcars staying at the station is minimized. We formulate the problem as a mixed integer linear programming model incorporating all decisions by utilizing the time-indexed conventional formulation for the single machine scheduling problems, and present three efficient solution approaches including a Lagrangian relaxation algorithm, a heuristic and an integer-based encoding genetic algorithm by exploiting the structure of the presented formulation and the characteristic of the problem. A numerical example coming from the practical situation is used to test the effectiveness and efficiency of the proposed approaches. Computational results show that our approaches can quickly solve the practical problem to optimality or approximate optimality, and their results are obviously better than that found by the first-come-first-served based empirical method adopted by the station dispatcher in the real-time decision environment.Chapter3investigates the railcar allocation problem at railroad single-directional marshalling station with multiple switch engines and multiple yard engines. The problem lies on determining the composition of each outbound train, and assigning and scheduling the task of each switch engine and each yard engine, such that each outbound train satisfies the assembly rules and each engine is conflict-free. Utilizing the time-indexed based formulation of the parallel machine scheduling problems to model the assignment and schedule of engines, we firstly present the problem a mixed integer linear programming model to minimize the total dwell time of railcars staying at the station, which incorporates the train composition sub-problem and the engine scheduling sub-problem into the same optimization framework by using a linking constraints, and then design an exact algorithm and two heuristics according to the structure and characteristic of the problem, in which the exact algorithm is to use CPLEX to exactly solve the proposed optimization model, and the heuristics includes a Lagrangian relaxation algorithm and a biased random-key genetic algorithm. A realistic and large-scale numerical example is used to test the effectiveness and efficiency of the proposed approaches. Computational results show that our exact algorithm and biased random-key genetic algorithm can obtain approximately optimal solution with optimality gap less than1%for practical problems within the restricted computation time, and the solutions found by our approaches are not worse than that found by the empirical method used in practice.Chapter4investigates the railcar allocation problem at railroad double-directional marshalling station with two operation systems and railcar transfer between systems. The problem consists of determining the composition of each outbound train and each transfer train, and assigning and scheduling the task of each switch engine and each yard engine, such that each outbound train meets the departure rules, each transfer train satisfies the assembly requirements, and each engine receives conflict-free tasks. We formulate the problem as a mixed integer linear programming model to minimize the total dwell time of railcars staying at the station with all decisions, in this model, the engine scheduling sub-problem is modeled by using the time-indexed classical formulation for the parallel machine scheduling problems. By utilizing the easy to be decomposed structure of the problem, we design two effective heuristics including a Lagrangian relaxation algorithm with using the proposed optimization model and a biased random-key genetic algorithm without using the proposed optimization model. To validate the effectiveness and efficiency of our proposed approaches for practical problems, computational test is conducted on a realistic and large-scale numerical example. Computational results show that our biased random-key genetic algorithm can obtain near-optimal solution with optimality gap approaching1%within the computation time less than100s, and our Lagrangian relaxation algorithm can find good solution with optimality gap not greater than3%at the end of the restricted time. More importantly, their solutions are obviously better than those determined by the manual method used by the station dispatcher.Chapter5investigates the route scheduling problem with multiple types of operations and complicated constraints among operations at railroad technical station. This problem is to simultaneously assign and schedule route for each train and engine operation, such that all operations are conflict-free in time and space, and the defined consistency constraints are satisfied. We introduce the concept of task and activity in the job shop scheduling problem to describe the scheduling operations, and define the concept of route pattern which can incorporate all routing alternatives and partial timing alternatives to represent the decision variables, based on which we transform the original route scheduling problem with multiple decision tasks to a constrained assignment problem which only has to assign pre-computed route patterns to activities. We formulate the defined constrained assignment problem as a0-1linear programming model which minimizes the total delay and travel time and satisfies the uniqueness, consistency and compatible constraints. In modeling the time consistency and switch compatible constraints, graph based maximal correspondence technique is used to replace the traditional pair-wise correspondence technique to strength the bounding efficiency of the generated constraints. We also discuss how to extend the standard constrained assignment problem, so as to enable it to satisfy more operational requirements and transform from a single routing model to an integrated routing and scheduling model. For the infeasible issue of the standard problem, an iteration algorithm is proposed to generate candidate route patterns which can obtain feasible solutions by solving a sequence of auxiliary models. At last, computational results of a realistic example show that the maximal technique can significantly decrease the number of generated constraints compared with the pair-wise technique, and the dynamic train-to-track-assignment strategy used in our approach is better than the static train-to-track-assignment strategy used in dispatchers’empirical method in terms of solution quality.Chapter6investigates the track capacitated train assembly shunting problem (TASP) in the real-time scheduling of railroad technical station. Given the inbound trains and shunting tracks, this problem lies on determining the number of shunting operations and the routes of each railcar of the inbound trains in each shunting operation, such that each outbound train can be realized in the correct station-based order without violating the tracks’number and capacity, while requiring minimal number of pulled-outs, shunted railcars, occupied tracks and rolled-ins. We first consider a simple TASP which assembles single inbound train into single outbound train. Using0-1matrixes to encode the assembly shunting plan, a novel bitstring method is developed for the problem. By defining different track pulled-out principles, we propose a total bitstring method and a partial bitstring method which pulls-out all tracks and especially reserves a track for the outbound train, respectively. A two-stage iteration search algorithm incorporating an iteration optimization procedure and a local search procedure is developed to implement these two methods. The first stage is to find the required0-1matrixes by solving a sequence of0-1linear programming model, which is further improved by several local rules defined in the second stage. The obtained plan can minimize the number of pulled-outs, shunted railcars, occupied tracks and rolled-ins in the lexicographical order. We also apply our extended total and partial bitstring methods to solve the more challenging batch TASP which has to simultaneously assembly multiple inbound trains into multiple outbound trains. At last, several realistic instances are used to show that our bitstring method can effectively solve the simple and batch TASP, and their fast computation time allows us to simultaneously apply them to tackle large-scale problem instances.更多还原