A tabu search algorithm to solve the integrated planning of container on an inter-terminal network connected with a hinterland rail network

Transport demand for containers has been increasing for decades, which places pressure on road transport. As a result, rail transport is stimulated to provide better intermodal freight transport services. This paper investigates mathematical models for the planning of container movements in a port area, integrating the inter-terminal transport of containers (ITT, within the port area) with the rail freight formation and transport process (towards the hinterland). An integer linear programming model is used to formulate the container transport across operations at container terminals, the network interconnecting them, railway yards and the railway networks towards the hinterland. A tabu search algorithm is proposed to solve the problem. The practical applicability of the algorithm is tested in a realistic infrastructure case and different demand scenarios. Our results show the degree by which internal (ITT) and external (hinterland) transport processes interact, and the potential for improvement of overall operations when the integrated optimization proposed is used. Instead, if the planning of containers in the ITT system is optimized as a stand-alone problem, the railway terminals may suffer from longer delay times or additional train cancellations. When planning the transport of 4060 TEU containers within one day, the benefits of the ITT planning without considering railway operations account for 17% ITT cost reduction but 93% railway operational cost growth, while the benefits of integrating ITT and railway account for a reduction of 20% in ITT cost and 44% in railway operational costs.     

Macroscopic multiple-station short-turning model in case of complete railway blockages

In case of railway disruptions, traffic controllers are responsible for dealing with disrupted traffic and reduce the negative impact for the rest of the network. In case of a complete blockage when no train can use an entire track, a common practice is to short-turn trains. Trains approaching the blockage cannot proceed according to their original plans and have to short-turn at a station close to the disruption on both sides. This paper presents a Mixed Integer Linear Program that computes the optimal station and times for short-turning the affected train services during the three phases of a disruption. The proposed solution approach takes into account the interaction of the traffic between both sides of the blockage before and after the disruption. The model is applied to a busy corridor of the Dutch railway network. The computation time meets the real-time solution requirement. The case study gives insight into the importance of the disruption period in computing the optimal solution. It is concluded that different optimal short-turning solutions may exist depending on the start time of the disruption and the disruption length. For periodic timetables, the optimal short-turning choices repeat due to the periodicity of the timetable. In addition, it is observed that a minor extension of the disruption length may result in less delay propagation at the cost of more cancellations.     

Solving train formation problem using simulated annealing algorithm in a simplex framework

The train formation plan (TFP) determines the train services and their frequencies and assigns the demands. The TFP models are often formulated as a capacitated service network design problem, and the optimal solution is normally difficult to find. In this paper, a hybrid algorithm of the Simplex method and simulated annealing is proposed for the TFP problem. The basic idea of the proposed algorithm is to use a simulated annealing algorithm to explore the solution space, where the revised Simplex method evaluates, selects, and implements the moves. In the proposed algorithm, the neighborhood structure is based on the pivoting rules of the Simplex method that provides an efficient method to reach the neighbors of the current solution. A state‐of‐the‐art method is applied for parameters tuning by using the design of experiments approach. To evaluate the proposed model and the solution method, 25 test problems have been simulated and solved. The results show the efficiency and the effectiveness of the proposed approach. The proposed approach is implemented to develop the TFP in the Iranian railway as a case study. It is possible to save significant time and cost through solving the TFP problem by using the proposed algorithm and developing the efficient TFP plan in the railway networks. Copyright © 2012 John Wiley & Sons, Ltd.     

Optimizing train stopping patterns and schedules for high-speed passenger rail corridors

High-speed railway (HSR) systems have been developing rapidly in China and various other countries throughout the past decade; as a result, the question of how to efficiently operate such large-scale systems is posing a new challenge to the railway industry. A high-quality train timetable should take full advantage of the system’s capacity to meet transportation demands. This paper presents a mathematical model for optimizing a train timetable for an HSR system. We propose an innovative methodology using a column-generation-based heuristic algorithm to simultaneously account for both passenger service demands and train scheduling. First, we transform a mathematical model into a simple linear programming problem using a Lagrangian relaxation method. Second, we search for the optimal solution by updating the restricted master problem (RMP) and the sub-problems in an iterative process using the column-generation-based algorithm. Finally, we consider the Beijing–Shanghai HSR line as a real-world application of the methodology; the results show that the optimization model and algorithm can improve the defined profit function by approximately 30% and increase the line capacity by approximately 27%. This methodology has the potential to improve the service level and capacity of HSR lines with no additional high-cost capital investment (e.g., the addition of new tracks, bridges and tunnels on the mainline and/or at stations).     

Techniques for inserting additional trains into existing timetables

In this paper techniques for scheduling additional train services (SATS) are considered as is train scheduling involving general time window constraints, fixed operations, maintenance activities and periods of section unavailability. The SATS problem is important because additional services must often be given access to the railway and subsequently integrated into current timetables. The SATS problem therefore considers the competition for railway infrastructure between new services and existing services belonging to the same or different operators. The SATS problem is characterised as a hybrid job shop scheduling problem with time window constraints. To solve this problem constructive algorithm and meta-heuristic scheduling techniques that operate upon a disjunctive graph model of train operations are utilised. From numerical investigations the proposed framework and associated techniques are tested and shown to be effective.     

A Value-at-Risk (VAR) approach to routing rail hazmat shipments

Hazardous materials (hazmat) accidents are rare though the consequences could be disastrous. Given the possibility of low probability – high consequence event, a risk-averse routing hazmat shipment is necessary. We propose a value-at-risk (VaR) approach to route rail hazmat shipments, using the best train configuration, over a given railroad network with limited number of train services such that the transport risk as measured by VaR is minimized. Freight train derailment reports of the Federal Railroad Administration were analyzed to develop expressions that would incorporate characteristics of railroad accidents, and then to estimate the different inputs. The proposed methodology was used to study several problem instances generated using the realistic network of a railroad operator, and to demonstrate that it is possible to develop different routes for shipments depending on the risk preference of the decision maker.     

Scheduling railway freight delivery appointments using a bid price approach

This paper proposes a method for establishing aggressive but achievable delivery appointment times for railroad shipments, taking into account individual customer needs and forecasted available train capacity. The concept of scheduling appointment times is directly patterned after current motor carrier industry practice, so that customers can plan for rail or truck deliveries in the same way.A shipment routing problem is decomposed into a deterministic “dynamic car scheduling” (DCS) process for shipments already accepted and a stochastic “train segment pricing” (TSP) process for forecasting future demands which have not yet called in and for which delivery appointments have yet to be scheduled. Both are formulated as multi-commodity network flow (MCNF) problems, where each shipment is treated as a separate commodity. Gain coefficients represent recapture probabilities that a specific customer will accept a carrier’s service offer.A comparison with a widely used revenue management formulation is given. A Lagrangian heuristic for obtaining a primal solution is also described. The problem is solved within a 1% gap using the subgradient algorithm.     

Ant colony optimization for the real-time train routing selection problem

This paper deals with the real-time problem of scheduling and routing trains in a railway network. In the related literature, this problem is usually solved starting from a subset of routing alternatives and computing the near-optimal solution of the simplified routing problem. We study how to select the best subset of routing alternatives for each train among all possible alternatives. The real-time train routing selection problem is formulated as an integer linear programming formulation and solved via an algorithm inspired by the ant colonies’ behavior. The real-time railway traffic management problem takes as input the best subset of routing alternatives and is solved as a mixed-integer linear program. The proposed methodology is tested on two practical case studies of the French railway infrastructure: the Lille terminal station area and the Rouen line. The computational experiments are based on several practical disturbed scenarios. Our methodology allows the improvement of the state of the art in terms of the minimization of train consecutive delays. The improvement is around 22% for the Rouen instances and around 56% for the Lille instances.     

An improved car‐following model for railway traffic

In this paper, we propose an improved traffic model for simulating train movement in railway traffic. The proposed model is based on optimal velocity car‐following model. In order to test the proposed model, we use it to simulate the train movement with fixed‐block system. In simulations, we analyze and discuss the space–time diagram of railway traffic flow and the trajectories of train movement. Simulation results demonstrate that the proposed model can be successfully used for simulating the train movement in railway traffic. From the space–time diagram, we find some complex phenomena of train flow, which are observed in real railway traffic, such as train delays. By analyzing the trajectories of train movement, some dynamic characteristics of trains can be reproduced. Copyright © 2011 John Wiley & Sons, Ltd.     

Conflict Resolution through Negotiation in a Railway Open Access Market: a Multi-agent System Approach

Abstract

Open access reforms to railway regulations allow multiple train operators to provide rail services on a common infrastructure. As railway operations are now independently managed by different stakeholders, conflicts in operations may arise, and there have been attempts to derive an effective access charge regime so that these conflicts may be resolved. One approach is by direct negotiation between the infrastructure manager and the train service providers. Despite the substantial literature on the topic, few consider the benefits of employing computer simulation as an evaluation tool for railway operational activities such as access pricing. This article proposes a multi-agent system (MAS) framework for the railway open market and demonstrates its feasibility by modelling the negotiation between an infrastructure provider and a train service operator. Empirical results show that the model is capable of resolving operational conflicts according to market demand.     

A comparison of different container sorting systems in modern rail-rail transshipment yards

Rail-rail transshipment yards act as central hub nodes within a railway network and enable a rapid consolidation of containers between different freight trains. To avoid an excessive movement of gantry cranes when transferring a container from one train to another, modern yards apply sorting systems where shuttle cars move containers horizontally along the spread of the yard. This paper compares four elementary sorting systems. Specifically, we compare rubber-tired and rail-mounted shuttles and differentiate whether a pure shuttle system or a lift & shuttle system is applied. In pure shuttle systems, a shuttle receives a container from a crane and transports it towards the destination crane, where it serves as a storage device until being unloaded. A lift & shuttle system applies shuttles with an integrated lifting platform, so that they are able to autonomously store and receive containers from a separate storage rack. Both alternatives exist in rubber-tired and rail-mounted versions. As the shuttles are the main driver of the investment costs, we compare the required fleet size for timely supplying given gantry crane schedules within all four systems. For this purpose, we derive suited scheduling procedures. This way, decision support for yard managers having to identify a suited sorting system and to layout a new terminal is provided.     

Goods transportation by the French National Railway (SNCF): The measurement and marketing of reliability

Rail transportation that is timely and dependable can compete with the trucking mode for Just-In-Time (JIT) deliveries. SNCF, the French National Railway, has a number of such offerings that emphasize reliability of freight shipments. We describe several of these SNCF products. They have in common the nature of regularly-scheduled service: planned connections to specific trains at classification yards. We discuss ways that SNCF can measure reliability, monitor it, and market it. Third-party logistics services of the SNCF are summarized, as is marketing research by SNCF to update their product line in goods transportation. We conclude with possibilities for future research.     

An appraisal of a column-generation-based algorithm for centralized train-conflict resolution on a metropolitan railway network

In practice, a train-conflict resolution is decentralized around dispatchers each of whom controls a few segments in a global railway network with her rule-of-thumb to operational data. Conceptually, the global sub-optimality or infeasibility of the decentralized system is resolved by a network controller who coordinates the dispatchers and train operators at the lower layers on a real-time basis. However, such notion of a multi-layer system cannot be effectual unless the top layer is able to provide a global solution soon enough for the dynamic lower layers to adapt in a seamless manner. Unfortunately, a train-conflict resolution problem is NP-hard as formally established in this paper and an effective solution method traded off between computation time and solution quality has been lacking in literature. Thus, we propose a column-generation-based algorithm that exploits the separability of the problem. A key ingredient of the algorithm is an efficient heuristic for the pricing subproblem for column generation. Tested on the real data from the Seoul metropolitan railway network, the algorithm provides near-optimal conflict-free timetables in a few seconds for most cases. The performance of the proposed algorithm is compared to the ones of the previous MIP-based heuristic by Törnquist and Persson (2007) and the priority-based heuristic by Sahin (1999).     

Development and Impact of the Modern High‐speed Train: A Review

Abstract

The inauguration of the Shinkansen high‐speed train service between Tokyo and Osaka, Japan, at 210 kph maximum operating speed some 40 years ago marked the comeback of the train as an important passenger mode of transport. Since then high‐speed train (HST) services have been introduced in many countries and are planned in many more, and the train has once more become the dominant mode of transport on many routes. This review summarizes the different elements of HST operation with the aim of characterizing HST operation and putting in context its impact in terms of what it is best designed for and what it can deliver. The review concludes that the HST is best designed to substitute conventional railway services on routes where much higher capacity is required and to reduce travel time, further improving the railway service, also against other modes, therefore leading to mode substitution. However, the high investment in HST infrastructure could not be justified based on its economic development benefits since these are not certain. Finally, the following definition for HST services is suggested: high capacity and frequency railway services achieving an average speed of over 200 kph.     

Solutions to the optimal network design problem with shipments related to transportation cost

Two versions of an optimal network design problem with shipments proportional to transportation costs are formulated. Extensions of an algorithm developed in prior research for solving these problems are proposed and tested. The performance of the algorithms is found to improve substantially as the dependence of shipments on costs is increased. Moreover, the optimal solutions obtained are unexpectedly robust with respect to a wide range of transportation cost assumptions. These findings could have important computational and policy implications if applicable to larger networks.     

An optimization model for integrated planning of railway traffic and network maintenance

Railway transportation systems are important for society and have many challenging and important planning problems. Train services as well as maintenance of a railway network need to be scheduled efficiently, but have mostly been treated as two separate planning problems. Since these activities are mutually exclusive they must be coordinated and should ideally be planned together. In this paper we present a mixed integer programming model for solving an integrated railway traffic and network maintenance problem. The aim is to find a long term tactical plan that optimally schedules train free windows sufficient for a given volume of regular maintenance together with the wanted train traffic. A spatial and temporal aggregation is used for controlling the available network capacity. The properties of the proposed model are analyzed and computational experiments on various synthetic problem instances are reported. Model extensions and possible modifications are discussed as well as future research directions.     

Performability evaluation of the ERTMS/ETCS – Level 3

Level 3 of the ERTMS/ETCS improves the capacity of railways by replacing fixed-block signalling, which prevents a train to enter a block occupied by another train, with moving block signalling, which allows a train to proceed as long as it receives radio messages ensuring that the track ahead is clear of other trains. If messages are lost, a train must stop for safety reasons within a given deadline, even though the track ahead is clear, making the availability of the communication link crucial for successful operation.We combine analytic evaluation of failures due to burst noise and connection losses with numerical solution of a non-Markovian model representing also failures due to handovers between radio stations. In so doing, we show that handovers experienced by a pair of chasing trains periodically affect the availability of the radio link, making behavior of the overall communication system recurrent over the hyper-period of periodic message releases and periodic arrivals at cell borders. As a notable aspect, non-Markovian transient analysis within two hyper-periods is sufficient to derive an upper bound on the first-passage time distribution to an emergency brake, permitting to achieve a trade-off between railway throughput and stop probability. A sensitivity analysis is performed with respect to train speed and headway distance, permitting to gain insight into the consequences of system-level design choices.     

A maximum entropy-least squares estimator for elastic origin-destination trip matrix estimation

In transportation subnetwork-supernetwork analysis, it is well known that the origin-destination (O-D) flow table of a subnetwork is not only determined by trip generation and distribution, but also a result from traffic routing and diversion, due to the existence of internal-external, external-internal and external-external flows. This result indicates the variable nature of subnetwork O-D flows. This paper discusses an elastic O-D flow table estimation problem for subnetwork analysis. The underlying assumption is that each cell of the subnetwork O-D flow table contains an elastic demand function rather than a fixed demand rate and the demand function can capture all traffic diversion effect under various network changes. We propose a combined maximum entropy-least squares estimator, by which O-D flows are distributed over the subnetwork in terms of the maximum entropy principle, while demand function parameters are estimated for achieving the least sum of squared estimation errors. While the estimator is powered by the classic convex combination algorithm, computational difficulties emerge within the algorithm implementation until we incorporate partial optimality conditions and a column generation procedure into the algorithmic framework. Numerical results from applying the combined estimator to a couple of subnetwork examples show that an elastic O-D flow table, when used as input for subnetwork flow evaluations, reflects network flow changes significantly better than its fixed counterpart.     

Rail track infrastructure ownership: investment and operational issues

As privatisation of railway systems reach the political agendas in a number of countries, the separation of track infrastructure from train operations is seen as providing the vehicle which will improve profitability within the rail industry. This paper deals with three main issues related to such separation within a freight railway focus, namely: investment appraisal; track standards and maintenance; and train operating performance. The conflicts of interest between the owners of track and their client operators are discussed in detail. Costs related to track capacity and congestion need to be taken into account, given that additional trains are likely to lead to increased risk of delays to existing services. The paper discusses the use of a travel time reliability model to estimate the additional costs imposed on the system through the introduction of specific train services.It is concluded that investment in individual elements of railway infrastructure must be integrated with the overall financial and customer service strategies of both operators and owners. As an alternative to current practices, a hybrid model of track ownership is put forward here. Under such a model, a joint-venture company with equity from the main ÒplayersÓ would be owner of track. This would allow some of the benefits of vertical integration to be retained, whilst providing fair access to new operators.     

Estimation of rail passenger flow and system utilization with ticket transaction and gate data

Capturing the dynamics in passenger flow and system utilization over time and space is extremely important for railway operators. Previous studies usually estimated passenger flow using automatic fare collection data, and their applications are limited to a single stopping pattern and/or a single type of ticket. However, the conventional railway in Taiwan provides four types of ticket and five types of train service with a number of stopping patterns. This study develops a comprehensive framework and corresponding algorithms to map passenger flow and evaluate system utilization. A multinomial logit model is constructed and incorporated in the algorithms to estimate passenger train selection behavior. Results from the empirical studies demonstrate that the developed framework and algorithms can successfully match passengers with train services. With this tool, operators can efficiently examine passenger flow and service utilization, thereby quickly adjusting their service strategies accordingly to improve system performance.