Model And Algorithm For The Optimal Operation Plan Of Railroad Technical Station

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.