Combinatorial and Robust Optimisation Models and Algorithms for Railway Applications

This thesis deals with an investigation of combinatorial and robust optimisation models to solve railway problems. Railway applications represent a challenging area for operations research. In fact, most problems in this context can be modelled as combinatorial optimisation problems, in which the number of feasible solutions is finite. Yet, despite the astonishing success in the field of combinatorial optimisation, the current state of algorithmic research faces severe difficulties with highly-complex and data-intensive applications such as those dealing with optimisation issues in large-scale transportation networks. One of the main issues concerns imperfect information. The idea of Robust Optimisation, as a way to represent and handle mathematically systems with not precisely known data, dates back to 1970s. Unfortunately, none of those techniques proved to be successfully applicable in one of the most complex and largest in scale (transportation) settings: that of railway systems. Railway optimisation deals with planning and scheduling problems over several time horizons. Disturbances are inevitable and severely affect the planning process. Here we focus on two compelling aspects of planning: robust planning and online (real-time) planning.

Alta velocidad ferroviaria en California(USA): cuarta parte (IV) Fresno-Sacramento (Roseville) = High speed railway in California (USA): fourth part (IV) Fresno-Sacramento (Roseville)

Implantación de la Red de Alta velocidad Ferroviaria en California. Tramo Fresno-Sacramento. El presente articúlo es la cuarta parte de la serie "Alta Velocidad Ferroviaria en California (CHSRS)". Recoge la Alternativa "Stockton Arch", que el Proyecto FARWEST presenta a la prevista por la Authority (CHSRA), para la Línea HSR Fresno-Sacramento, en programación y en trazado. Éste discurre, desde la gran Terminal de Fresno (implantada en las afueras al suroeste de la ciudad) por el segmento sur del "mar interior" (que en el Terciario Superior ocupaba el actual Valle Central), hasta Stockton, y por el segmento norte, hasta Sacramento. El Paet de Ripperdan (~ pK 40) queda conectado por carretera con el PAET de Oroloma de la Línea HSR Fresno-San Francisco (Golden Gate Alternative). La última parte del trazado de la Línea HSR Fresno-Sacramento (Stockton Arch Alternative), coincide en alineación y rasante con la Línea HSR San Francisco-Sacramento (Crossing Bay Alternative) a la altura de Roseville, donde se emplaza la gran terminal norte de la red de California, desde la que se unirá ésta con la de Nevada, por Reno. This article forras the fourth part of the series entitled "High Speed Railway in California (CHSRS)". It addresses the "Stockton Arch" alternative, which the FARWESTProjectpresents in scheduling and in alignment as to that provided for by the Authority (CHSRA) for the Fresno-Sacramento HSR Line. The latter runs from the grand Fresno Terminal (located in the outskirts to the southwest ofthe city) through the south segment ofthe "inland sea" (which oceupied the current Central Valley in the Upper Tertiary) to Stockton and through the north segment to Sacramento. The Ripperdan TSAP (post ofpassing and stabling trains), — kilometer point 40, conneets with the Oroloma TSAP ofthe Fresno-San Francisco HSR Line (Golden Gate Alternative) by road. The last part of the Fresno-Sacramento HSR Line alignment (Stockton Arch Alternative), coincides in alignment and grade with the San Francisco-Sacramento HSR Line (Crossing Bay Alternative) at Roseville, where the great north terminal ofthe California network is located, from which the latter will be linked with Nevada s network through Reno.

Train scheduling in high speed railways: considering competitive effects

The railway planning problem is usually studied from two different points of view: macroscopic and microscopic. We propose a macroscopic approach for the high-speed rail scheduling problem where competitive effects are introduced. We study train frequency planning, timetable planning and rolling stock assignment problems and model the problem as a multi-commodity network flow problem considering competitive transport markets. The aim of the presented model is to maximize the total operator profit. We solve the optimization model using realistic probleminstances obtained from the network of the Spanish railwa operator RENFE, including other transport modes in Spain

Train scheduling and rolling stock assignment in high speed trains

The Train Timetabling Problem (TTP) has been widely studied for freight and passenger rail systems. A lesser effort has been devoted to the study of high-speed rail systems. A modeling issue that has to be addressed is to model departure time choice of passengers on railway services. Passengers who use these systems attempt to travel at predetermined hours due to their daily life necessities (e.g., commuter trips). We incorporate all these features into TTP focusing on high-speed railway systems. We propose a Rail Scheduling and Rolling Stock (RSch-RS) model for timetable planning of high-speed railway systems. This model is composed of two essential elements: i) an infrastructure model for representing the railway network: it includes capacity constraints of the rail network and the Rolling-Stock constraints; and ii) a demand model that defines how the passengers choose the departure time. The resulting model is a mixed-integer programming model which objective function attempts to maximize the profit for the rail operator

A Constructive Genetic Algorithm for permutation flowshop scheduling

The general flowshop scheduling problem is a production problem where a set of n jobs have to be processed with identical flow pattern on in machines. In permutation flowshops the sequence of jobs is the same on all machines. A significant research effort has been devoted for sequencing jobs in a flowshop minimizing the makespan. This paper describes the application of a Constructive Genetic Algorithm (CGA) to makespan minimization on flowshop scheduling. The CGA was proposed recently as an alternative to traditional GA approaches, particularly, for evaluating schemata directly. The population initially formed only by schemata, evolves controlled by recombination to a population of well-adapted structures (schemata instantiation). The CGA implemented is based on the NEH classic heuristic and a local search heuristic used to define the fitness functions. The parameters of the CGA are calibrated using a Design of Experiments (DOE) approach. The computational results are compared against some other successful algorithms from the literature on Taillard`s well-known standard benchmark. The computational experience shows that this innovative CGA approach provides competitive results for flowshop scheduling; problems. (C) 2007 Elsevier Ltd. All rights reserved.

Experimental investigation on the dynamic behaviour of a railway vehicle travelling through a turnout

Track critical locations with respect to the railway vehicle safety are the passages through the turnouts. The purpose of this investigation is to evaluate the safety of a railway vehicle crossing a turnout. In this study, the topography of a track turnout lay-out has been experimentally measured, and its geometric properties were synthesised. Results show that a constant wavelength vehicle oscillation occurs on the switches in the turnout and that the maximum lateral force at 65 km/h is almost 65% greater than those at low speeds (under 30 km/h).

Safety of a railway wheelset - derailment simulation with increasing lateral force

The motivation for this research is to make a comparison between dynamic results of a free railway wheelset derailment and safety limits. For this purpose, a numerical simulation of a wheelset derailment submitted to increasing lateral force is used to compare with the safety limit, using different criteria. A simplified wheelset model is used to simulate derailments with different adhesion conditions. The contact force components, including the longitudinal and spin effects, are identified in a steady-state condition on the verge of a derailment. The contact force ratios are used in a three-dimensional (3D) analytical formula to calculate the safety limits. Simulation results obtained with two contact methods were compared with the published results and the safety limit was identified with the two criteria. Results confirm Nadal`s conservative aspect and show that safety 3D analytical formula presents slightly higher safety limits for lower friction coefficients and smaller limits for high friction, in comparison with the simulation results with Fastsim.

A novel continuous time representation for the scheduling of pipeline systems with pumping yield rate constraints

Pipeline systems play a key role in the petroleum business. These operational systems provide connection between ports and/or oil fields and refineries (upstream), as well as between these and consumer markets (downstream). The purpose of this work is to propose a novel MINLP formulation based on a continuous time representation for the scheduling of multiproduct pipeline systems that must supply multiple consumer markets. Moreover, it also considers that the pipeline operates intermittently and that the pumping costs depend on the booster stations yield rates, which in turn may generate different flow rates. The proposed continuous time representation is compared with a previously developed discrete time representation [Rejowski, R., Jr., & Pinto, J. M. (2004). Efficient MILP formulations and valid cuts for multiproduct pipeline scheduling. Computers and Chemical Engineering, 28, 1511] in terms of solution quality and computational performance. The influence of the number of time intervals that represents the transfer operation is studied and several configurations for the booster stations are tested. Finally, the proposed formulation is applied to a larger case, in which several booster configurations with different numbers of stages are tested. (C) 2007 Elsevier Ltd. All rights reserved.

Scheduling in a two-machine flowshop for the minimization of the mean absolute deviation from a common due date

This paper addresses the minimization of the mean absolute deviation from a common due date in a two-machine flowshop scheduling problem. We present heuristics that use an algorithm, based on proposed properties, which obtains an optimal schedule fora given job sequence. A new set of benchmark problems is presented with the purpose of evaluating the heuristics. Computational experiments show that the developed heuristics outperform results found in the literature for problems up to 500 jobs. (C) 2007 Elsevier Ltd. All rights reserved.

Minimizing total tardiness in a stochastic single machine scheduling problem using approximate dynamic programming

This paper addresses the non-preemptive single machine scheduling problem to minimize total tardiness. We are interested in the online version of this problem, where orders arrive at the system at random times. Jobs have to be scheduled without knowledge of what jobs will come afterwards. The processing times and the due dates become known when the order is placed. The order release date occurs only at the beginning of periodic intervals. A customized approximate dynamic programming method is introduced for this problem. The authors also present numerical experiments that assess the reliability of the new approach and show that it performs better than a myopic policy.

The single machine earliness and tardiness scheduling problem: lower bounds and a branch-and-bound algorithm

This paper addresses the single machine scheduling problem with a common due date aiming to minimize earliness and tardiness penalties. Due to its complexity, most of the previous studies in the literature deal with this problem using heuristics and metaheuristics approaches. With the intention of contributing to the study of this problem, a branch-and-bound algorithm is proposed. Lower bounds and pruning rules that exploit properties of the problem are introduced. The proposed approach is examined through a computational comparative study with 280 problems involving different due date scenarios. In addition, the values of optimal solutions for small problems from a known benchmark are provided.

Optimized harvest scheduling in eucalyptus plantations under operational, spatial and climatic constraints

The representation of sustainability concerns in industrial forests management plans, in relation to environmental, social and economic aspects, involve a great amount of details when analyzing and understanding the interaction among these aspects to reduce possible future impacts. At the tactical and operational planning levels, methods based on generic assumptions usually provide non-realistic solutions, impairing the decision making process. This study is aimed at improving current operational harvesting planning techniques, through the development of a mixed integer goal programming model. This allows the evaluation of different scenarios, subject to environmental and supply constraints, increase of operational capacity, and the spatial consequences of dispatching harvest crews to certain distances over the evaluation period. As a result, a set of performance indicators was selected to evaluate all optimal solutions provided to different possible scenarios and combinations of these scenarios, and to compare these outcomes with the real results observed by the mill in the study case area. Results showed that it is possible to elaborate a linear programming model that adequately represents harvesting limitations, production aspects and environmental and supply constraints. The comparison involving the evaluated scenarios and the real observed results showed the advantage of using more holistic approaches and that it is possible to improve the quality of the planning recommendations using linear programming techniques.

An evaluation of a suburban railway pedestrian crossing safety programme

This study evaluated a programme of educational and environmental (access prevention) interventions designed to reduce the incidence of illegal and unsafe crossing of the rail corridor at a suburban station in Auckland, New Zealand. Immediately after the programme of interventions, the proportion of those crossing the rail corridor by walking across the tracks directly rather than using the nearby overbridge had decreased substantially. Three months later, the decrease was even greater. However, the educational and environmental interventions were introduced simultaneously so that the effects of each could not be separated, nor could other unmeasured factors be ruled out. Anonymous surveys administered immediately before and 3 months after the interventions indicated that while awareness of the illegality of walking across the tracks had increased slightly, perception of risk had not changed. This suggests that the educational interventions may have had less effect than the access prevention measures. (C) 2001 Elsevier Science Ltd. All rights reserved.