Scheduling Trains with Priorities : a no-wait blocking parallel-machine job-shop scheduling model

The paper investigates train scheduling problems when prioritised trains and non-prioritised trains are simultaneously traversed in a single-line rail network. In this case, no-wait conditions arise because the prioritised trains such as express passenger trains should traverse continuously without any interruption. In comparison, non-prioritised trains such as freight trains are allowed to enter the next section immediately if possible or to remain in a section until the next section on the routing becomes available, which is thought of as a relaxation of no-wait conditions. With thorough analysis of the structural properties of the No-Wait Blocking Parallel-Machine Job-Shop-Scheduling (NWBPMJSS) problem that is originated in this research, an innovative generic constructive algorithm (called NWBPMJSS_Liu-Kozan) is proposed to construct the feasible train timetable in terms of a given order of trains. In particular, the proposed NWBPMJSS_Liu-Kozan constructive algorithm comprises several recursively-used sub-algorithms (i.e. Best-Starting-Time-Determination Procedure, Blocking-Time-Determination Procedure, Conflict-Checking Procedure, Conflict-Eliminating Procedure, Tune-up Procedure and Fine-tune Procedure) to guarantee feasibility by satisfying the blocking, no-wait, deadlock-free and conflict-free constraints. A two-stage hybrid heuristic algorithm (NWBPMJSS_Liu-Kozan-BIH) is developed by combining the NWBPMJSS_Liu-Kozan constructive algorithm and the Best-Insertion-Heuristic (BIH) algorithm to find the preferable train schedule in an efficient and economical way. Extensive computational experiments show that the proposed methodology is promising because it can be applied as a standard and fundamental toolbox for identifying, analysing, modelling and solving real-world scheduling problems.

Modelling and analysis of the crush zone of a typical Australian passenger train

In this paper, a three-dimensional nonlinear rigid body model has been developed for the investigation of the crashworthiness of a passenger train using the multibody dynamics approach. This model refers to a typical design of passenger cars and train constructs commonly used in Australia. The high-energy and low-energy crush zones of the cars and the train constructs are assumed and the data are explicitly provided in the paper. The crash scenario is limited to the train colliding on to a fixed barrier symmetrically. The simulations of a single car show that this initial design is only applicable for the crash speed of 35 km/h or lower. For higher speeds (e.g. 140 km/h), the crush lengths or crush forces or both the crush zone elements will have to be enlarged. It is generally better to increase the crush length than the crush force in order to retain the low levels of the longitudinal deceleration of the passenger cars.

Modelling and solving train scheduling problems under capacity constraints

Many large coal mining operations in Australia rely heavily on the rail network to transport coal from mines to coal terminals at ports for shipment. Over the last few years, due to the fast growing demand, the coal rail network is becoming one of the worst industrial bottlenecks in Australia. As a result, this provides great incentives for pursuing better optimisation and control strategies for the operation of the whole rail transportation system under network and terminal capacity constraints. This PhD research aims to achieve a significant efficiency improvement in a coal rail network on the basis of the development of standard modelling approaches and generic solution techniques. Generally, the train scheduling problem can be modelled as a Blocking Parallel- Machine Job-Shop Scheduling (BPMJSS) problem. In a BPMJSS model for train scheduling, trains and sections respectively are synonymous with jobs and machines and an operation is regarded as the movement/traversal of a train across a section. To begin, an improved shifting bottleneck procedure algorithm combined with metaheuristics has been developed to efficiently solve the Parallel-Machine Job- Shop Scheduling (PMJSS) problems without the blocking conditions. Due to the lack of buffer space, the real-life train scheduling should consider blocking or hold-while-wait constraints, which means that a track section cannot release and must hold a train until the next section on the routing becomes available. As a consequence, the problem has been considered as BPMJSS with the blocking conditions. To develop efficient solution techniques for BPMJSS, extensive studies on the nonclassical scheduling problems regarding the various buffer conditions (i.e. blocking, no-wait, limited-buffer, unlimited-buffer and combined-buffer) have been done. In this procedure, an alternative graph as an extension of the classical disjunctive graph is developed and specially designed for the non-classical scheduling problems such as the blocking flow-shop scheduling (BFSS), no-wait flow-shop scheduling (NWFSS), and blocking job-shop scheduling (BJSS) problems. By exploring the blocking characteristics based on the alternative graph, a new algorithm called the topological-sequence algorithm is developed for solving the non-classical scheduling problems. To indicate the preeminence of the proposed algorithm, we compare it with two known algorithms (i.e. Recursive Procedure and Directed Graph) in the literature. Moreover, we define a new type of non-classical scheduling problem, called combined-buffer flow-shop scheduling (CBFSS), which covers four extreme cases: the classical FSS (FSS) with infinite buffer, the blocking FSS (BFSS) with no buffer, the no-wait FSS (NWFSS) and the limited-buffer FSS (LBFSS). After exploring the structural properties of CBFSS, we propose an innovative constructive algorithm named the LK algorithm to construct the feasible CBFSS schedule. Detailed numerical illustrations for the various cases are presented and analysed. By adjusting only the attributes in the data input, the proposed LK algorithm is generic and enables the construction of the feasible schedules for many types of non-classical scheduling problems with different buffer constraints. Inspired by the shifting bottleneck procedure algorithm for PMJSS and characteristic analysis based on the alternative graph for non-classical scheduling problems, a new constructive algorithm called the Feasibility Satisfaction Procedure (FSP) is proposed to obtain the feasible BPMJSS solution. A real-world train scheduling case is used for illustrating and comparing the PMJSS and BPMJSS models. Some real-life applications including considering the train length, upgrading the track sections, accelerating a tardy train and changing the bottleneck sections are discussed. Furthermore, the BPMJSS model is generalised to be a No-Wait Blocking Parallel- Machine Job-Shop Scheduling (NWBPMJSS) problem for scheduling the trains with priorities, in which prioritised trains such as express passenger trains are considered simultaneously with non-prioritised trains such as freight trains. In this case, no-wait conditions, which are more restrictive constraints than blocking constraints, arise when considering the prioritised trains that should traverse continuously without any interruption or any unplanned pauses because of the high cost of waiting during travel. In comparison, non-prioritised trains are allowed to enter the next section immediately if possible or to remain in a section until the next section on the routing becomes available. Based on the FSP algorithm, a more generic algorithm called the SE algorithm is developed to solve a class of train scheduling problems in terms of different conditions in train scheduling environments. To construct the feasible train schedule, the proposed SE algorithm consists of many individual modules including the feasibility-satisfaction procedure, time-determination procedure, tune-up procedure and conflict-resolve procedure algorithms. To find a good train schedule, a two-stage hybrid heuristic algorithm called the SE-BIH algorithm is developed by combining the constructive heuristic (i.e. the SE algorithm) and the local-search heuristic (i.e. the Best-Insertion- Heuristic algorithm). To optimise the train schedule, a three-stage algorithm called the SE-BIH-TS algorithm is developed by combining the tabu search (TS) metaheuristic with the SE-BIH algorithm. Finally, a case study is performed for a complex real-world coal rail network under network and terminal capacity constraints. The computational results validate that the proposed methodology would be very promising because it can be applied as a fundamental tool for modelling and solving many real-world scheduling problems.

Modeling train delays in urban networks

The reliability of urban passenger trains is a critical performance measure for passenger satisfaction and ultimately market share. A delay to one train in a peak period can have a severe effect on the schedule adherence of other trains. This paper presents an analytically based model to quantify the expected positive delay for individual passenger trains and track links in an urban rail network. The model specifically addresses direct delay to trains, knock-on delays to other trains, and delays at scheduled connections. A solution to the resultant system of equations is found using an iterative refinement algorithm. Model validation, which is carried out using a real-life suburban train network consisting of 157 trains, shows the model estimates to be on average within 8% of those obtained from a large scale simulation. Also discussed, is the application of the model to assess the consequences of increased scheduled slack time as well as investment strategies designed to reduce delay.

Lateral impact derailment mechanisms, simulation and analysis

Lateral collisions between heavy road vehicles and passenger trains at level crossings and the associated derailments are serious safety issues. This paper presents a detailed investigation of the dynamic responses and derailment mechanisms of trains under lateral impact using a multi-body dynamics simulation method. Formulation of a three-dimensional dynamic model of a passenger train running on a ballasted track subject to lateral impact caused by a road truck is presented. This model is shown to predict derailment due to wheel climb and car body overturning mechanisms through numerical examples. Sensitivities of the truck speed and mass, wheel/rail friction and the train suspension to the lateral stability and derailment of the train are reported. It is shown that improvements to the design of train suspensions, including secondary and inter-vehicle lateral dampers have higher potential to mitigate the severity of the collision-induced derailments.

Minimising lateral impact derailment potential at level crossings through guard rails

Derailments due to lateral collisions between heavy road vehicles and passenger trains at level crossings (LCs) are serious safety issues. A variety of countermeasures in terms of traffic laws, communication technology and warning devices are used for minimising LC accidents; however, innovative civil infrastructure solution is rare. This paper presents a study of the efficacy of guard rail system (GRS) to minimise the derailment potential of trains laterally collided by heavy road vehicles at LCs. For this purpose, a three-dimensional dynamic model of a passenger train running on a ballasted track fitted with guard rail subject to lateral impact caused by a road truck is formulated. This model is capable of predicting the lateral collision-induced derailments with and without GRS. Based on dynamic simulations, derailment prevention mechanism of the GRS is illustrated. Sensitivities of key parameters of the GRS, such as the flange way width, the installation height and contact friction, to the efficacy of GRS are reported. It is shown that guard rails can enhance derailment safety against lateral impacts at LCs.

Quantitative evaluation of route allocation solutions at large-scale passenger stations

Routing trains within passenger stations in major cities is a common scheduling problem for railway operation. Various studies have been undertaken to derive and formulate solutions to this route allocation problem (RAP) which is particularly evident in mainland China nowadays because of the growing traffic demand and limited station capacity. A reasonable solution must be selected from a set of available RAP solutions attained in the planning stage to facilitate station operation. The selection is however based on the experience of the operators only and objective evaluation of the solutions is rarely addressed. In order to maximise the utilisation of station capacity while maintaining service quality and allowing for service disturbance, quantitative evaluation of RAP solutions is highly desirable. In this study, quantitative evaluation of RAP solutions is proposed and it is enabled by a set of indices covering infrastructure utilisation, buffer times and delay propagation. The proposed evaluation is carried out on a number of RAP solutions at a real-life busy railway station in mainland China and the results highlight the effectiveness of the indices in pinpointing the strengths and weaknesses of the solutions. This study provides the necessary platform to improve the RAP solution in planning and to allow train re-routing upon service disturbances.

Technology-mediated tools for shaping experiences in urban commuter trains

This thesis presents the results of a study into ways that technology can be appropriated and designed to support urban rail commuters in their daily journeys. The study evaluated a mobile application prototype deployed along the Brisbane passenger rail network. This prototype was designed to support social interaction between passengers sharing the same trains. This thesis provides a step forward in showing the relevance of increasingly creating solutions that contribute to a more enjoyable and attractive public transport service.

Sounds of the suburb

Sounds of the Suburb was a commissioned public art proposal based upon a brief set by Queensland Rail for the major redevelopment at their Brunswick Street Railway Station, Fortitude Valley, Brisbane. I proposed a large scale, electronic artwork to be distributed across the glass fronted structure of their station’s new concourse building. It was designed as a network of LED based ‘tracking’ - along which would travel electronically animated, ‘trains’ of text synchronised to the actual train timetables. Each message packet moved endlessly through a complex spatial network of ‘tracks’ and ‘stations’ set both inside, outside and via the concourse. The design was underpinned by large scale image of sound waves etched onto the architecture’s glass and was accompanied by two inset monitors each presenting ghosted images of passenger movements within the concourse, time-delay recorded and then cross-combined in realtime to form new composites.----- Each moving, reprogrammable phrase was conceived as a ‘train of thought’ and ostensibly contained an idea or concept about popular cultures surrounding contemporary music – thereby meeting the brief that the work should speak to the diverse musical cultures central to Fortitude Valley’s image as an entertainment hub. These cultural ‘memes’, gathered from both passengers and the music press were situated alongside quotes from philosophies of networking, speed and digital ecologies. These texts would continually propagate, replicate and cross fertlise as they moved throughout the ‘network’, thereby writing a constantly evolving ‘textual soundcape’ of that place. This idea was further cemented through the pace, scale and rhythm of passenger movements continually recorded and re-presented on the smaller screens.

A study of Chinese private passenger cars based on BP neural network

This study employs BP neural network to simulate the development of Chinese private passenger cars. Considering the uncertain and complex environment for the development of private passenger cars, indicators of economy, population, price, infrastructure, income, energy and some other fields which have major impacts on it are selected at first. The network is proved to be operable to simulate the progress of chinese private passenger cars after modeling, training and generalization test. Based on the BP neural network model, sensitivity analysis of each indicator is carried on and shows that the sensitivity coefficients of fuel price change suddenly. This special phenomenon reveals that the development of Chinese private passenger cars may be seriously affected by the recent high fuel price. This finding is also consistent with facts and figures

Modeling study on transport organization methods choice of highway rapid passenger transport in China

Some new types of mathematical model among four key techno - economic indexes of highway rapid passenger through transportation were established based on the principles of transportation economics. According to the research on the feasible solutions to the associated parameters which were then compared to the actual value, found some limitation in the existing transport organization method. In order to conquer that, two new types of transport organization method, namely CD (Collecting and Distributing) Method and Relay Method were brought forward. What’s more, a further research was down to estimate their characteristics, such as feasibilities, operation flows, applicability fields, etc. This analysis proves the two methods can offset the shortage of rapid passenger through transportation. To ensure highway rapid passenger transport develop harmoniously, a three-stage development targets was suggested to fuse different organization methods.

The potential for a web based intervention to improve young adult passenger safety

Young drivers aged 17-24 are consistently overrepresented in motor vehicle crashes. Research has shown that a young driver’s crash risk increases when carrying similarly aged passengers, with fatal crash risk increasing two to three fold with two or more passengers. Recent growth in access to and use of the internet has led to a corresponding increase in the number of web based behaviour change interventions. An increasing body of literature describes the evaluation of web based programs targeting risk behaviours and health issues. Evaluations have shown promise for such strategies with evidence for positive changes in knowledge, attitudes and behaviour. The growing popularity of web based programs is due in part to their wide accessibility, ability for personalised tailoring of intervention messages, and self-direction and pacing of online content. Young people are also highly receptive to the internet and the interactive elements of online programs are particularly attractive. The current study was designed to assess the feasibility for a web based intervention to increase the use of personal and peer protective strategies among young adult passengers. An extensive review was conducted on the development and evaluation of web based programs. Year 12 students were also surveyed about their use of the internet in general and for health and road safety information. All students reported internet access at home or at school, and 74% had searched for road safety information. Additional findings have shown promise for the development of a web based passenger safety program for young adults. Design and methodological issues will be discussed.

Scheduling trains as a blocking parallel-machine job shop scheduling problem

In this paper, the train scheduling problem is modelled as a blocking parallel-machine job shop scheduling (BPMJSS) problem. In the model, trains, single-track sections and multiple-track sections, respectively, are synonymous with jobs, single machines and parallel machines, and an operation is regarded as the movement/traversal of a train across a section. Due to the lack of buffer space, the real-life case should consider blocking or hold-while-wait constraints, which means that a track section cannot release and must hold the train until next section on the routing becomes available. Based on literature review and our analysis, it is very hard to find a feasible complete schedule directly for BPMJSS problems. Firstly, a parallel-machine job-shop-scheduling (PMJSS) problem is solved by an improved shifting bottleneck procedure (SBP) algorithm without considering blocking conditions. Inspired by the proposed SBP algorithm, feasibility satisfaction procedure (FSP) algorithm is developed to solve and analyse the BPMJSS problem, by an alternative graph model that is an extension of the classical disjunctive graph models. The proposed algorithms have been implemented and validated using real-world data from Queensland Rail. Sensitivity analysis has been applied by considering train length, upgrading track sections, increasing train speed and changing bottleneck sections. The outcomes show that the proposed methodology would be a very useful tool for the real-life train scheduling problems

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 metaheuristic 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.