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.

A sequencing approach for creating new train timetables

Train scheduling is a complex and time consuming task of vital importance. To schedule trains more accurately and efficiently than permitted by current techniques a novel hybrid job shop approach has been proposed and implemented. Unique characteristics of train scheduling are first incorporated into a disjunctive graph model of train operations. A constructive algorithm that utilises this model is then developed. The constructive algorithm is a general procedure that constructs a schedule using insertion, backtracking and dynamic route selection mechanisms. It provides a significant search capability and is valid for any objective criteria. Simulated Annealing and Local Search meta-heuristic improvement algorithms are also adapted and extended. An important feature of these approaches is a new compound perturbation operator that consists of many unitary moves that allows trains to be shifted feasibly and more easily within the solution. A numerical investigation and case study is provided and demonstrates that high quality solutions are obtainable on real sized applications.

Maintaining nutrition in aged care residents with a train-the-trainer intervention and nutrition coordinator

Objective: To investigate the impact of a train-the-trainer program on the nutritional status of older people in residential care. ----- Design: Prospective, randomized controlled study. Setting: Eight nursing homes in Southeast Queensland, Australia. ----- Participants: A total of 352 residents participated - 245 were female (69.6%). The mean age was 84.2 years and the majority (79.4%) were classified as high dependency. ----- Intervention: Residents from four nursing homes were randomly selected for a nutrition education program coordinated by Nutrition Coordinators. Residents from the other four nursing homes (control) received usual care. ----- Measurements: The Subjective Global Assessment was used to determine prevalence of malnutrition at baseline and six months post intervention. The Resident Classification Scale measured functional dependency. Prescribed diet, fluids, oral hygiene status and allied health referrals were obtained by chart audit. ----- Results: Approximately half the residents were well nourished with 49.4% moderately or severely malnourished. Residents in the intervention group were more likely to maintain or improve their nutritional status compared with the control group who were more likely to experience a deterioration (P=0.027). The odds of the control group being malnourished post test was 1.6 times more likely compared with the intervention group but this did not reach statistical significance (P=0.1). ----- Conclusion: The results of the study encourage the implementation of a Nutrition Coordinator program to maintain nutritional status of aged care residents. Nevertheless, malnutrition rates continue to be unacceptably high. In a rapidly aging society, the aged care sector needs to confront malnutrition and provide better resources for staff to take measures against this problem.

Flexible high-power multi DC-DC converters for train systems

This thesis reports on the investigations, simulations and analyses of novel power electronics topologies and control strategies. The research is financed by an Australian Research Council (ARC) Linkage (07-09) grant. Therefore, in addition to developing original research and contributing to the available knowledge of power electronics, it also contributes to the design of a DC-DC converter for specific application to the auxiliary power supply in electric trains. Specifically, in this regard, it contributes to the design of a 7.5 kW DC-DC converter for the industrial partner (Schaffler and Associates Ltd) who supported this project. As the thesis is formatted as a ‘thesis by publication’, the contents are organized around published papers. The research has resulted in eleven papers, including seven peer reviewed and published conference papers, one published journal paper, two journal papers accepted for publication and one submitted journal paper (provisionally accepted subject to few changes). In this research, several novel DC-DC converter topologies are introduced, analysed, and tested. The similarity of all of the topologies devised lies in their ‘current circulating’ switching state, which allows them to store some energy in the inductor, as extra inductor current. The stored energy may be applied to enhance the performance of the converter in the occurrence of load current or input voltage disturbances. In addition, when there is an alternating load current, the ability to store energy allows the converter to perform satisfactorily despite frequently and highly varying load current. In this research, the capability of current storage has been utilised to design topologies for specific applications, and the enhancement of the performance of the considered applications has been illustrated. The simplest DC-DC converter topology, which has a ‘current circulating’ switching state, is the Positive Buck-Boost (PBB) converter (also known as the non-inverting Buck-Boost converter). Usually, the topology of the PBB converter is operating as a Buck or a Boost converter in applications with widely varying input voltage or output reference voltage. For example, in electric railways (the application of our industrial partner), the overhead line voltage alternates from 1000VDC to 500VDC and the required regulated voltage is 600VDC. In the course of this research, our industrial partner (Schaffler and Associates Ltd) industrialized a PBB converter–the ‘Mudo converter’–operating at 7.5 kW. Programming the onboard DSP and testing the PBB converter in experimental and nominal power and voltage was part of this research program. In the earlier stages of this research, the advantages and drawbacks of utilization of the ‘current circulating’ switching state in the positive Buck-Boost converter were investigated. In brief, the advantages were found to be robustness against input voltage and current load disturbances, and the drawback was extra conduction and switching loss. Although the robustness against disturbances is desirable for many applications, the price of energy loss must be minimized to attract attention to the utilization of the PBB converter. In further stages of this research, two novel control strategies for different applications were devised to minimise the extra energy loss while the advantages of the positive Buck-Boost converter were fully utilized. The first strategy is Smart Load Controller (SLC) for applications with pre-knowledge or predictability of input voltage and/or load current disturbances. A convenient example of these applications is electric/hybrid cars where a master controller commands all changes in loads and voltage sources. Therefore, the master controller has a pre-knowledge of the load and input voltage disturbances so it can apply the SLC strategy to utilize robustness of the PBB converter. Another strategy aiming to minimise energy loss and maximise the robustness in the face of disturbance is developed to cover applications with unexpected disturbances. This strategy is named Dynamic Hysteresis Band (DHB), and is used to manipulate the hysteresis band height after occurrence of disturbance to reduce dynamics of the output voltage. When no disturbance has occurred, the PBB converter works with minimum inductor current and minimum energy loss. New topologies based on the PBB converter have been introduced to address input voltage disturbances for different onboard applications. The research shows that the performance of applications of symmetrical/asymmetrical multi-level diode-clamped inverters, DC-networks, and linear-assisted RF amplifiers may be enhanced by the utilization of topologies based on the PBB converter. Multi-level diode-clamped inverters have the problem of DC-link voltage balancing when the power factor of their load closes to unity. This research has shown that this problem may be solved with a suitable multi-output DC-DC converter supplying DClink capacitors. Furthermore, the multi-level diode-clamped inverters supplied with asymmetrical DC-link voltages may improve the quality of load voltage and reduce the level of Electromagnetic Interference (EMI). Mathematical analyses and experiments on supplying symmetrical and asymmetrical multi-level inverters by specifically designed multi-output DC-DC converters have been reported in two journal papers. Another application in which the system performance can be improved by utilization of the ‘current circulating’ switching state is linear-assisted RF amplifiers in communicational receivers. The concept of ‘linear-assisted’ is to divide the signal into two frequency domains: low frequency, which should be amplified by a switching circuit; and the high frequency domain, which should be amplified by a linear amplifier. The objective is to minimize the overall power loss. This research suggests using the current storage capacity of a PBB based converter to increase its bandwidth, and to increase the domain of the switching converter. The PBB converter addresses the industrial demand for a DC-DC converter for the application of auxiliary power supply of a typical electric train. However, after testing the industrial prototype of the PBB converter, there were some voltage and current spikes because of switching. To attenuate this problem without significantly increasing the switching loss, the idea of Active Gate Signalling (AGS) is presented. AGS suggests a smart gate driver that selectively controls the switching process to reduce voltage/current spikes, without unacceptable reduction in the efficiency of switching.

Dynamic coast control of train movement with genetic algorithm

The railway service is now the major transportation means in most of the countries around the world. With the increasing population and expanding commercial and industrial activities, a high quality of railway service is the most desirable. Train service usually varies with the population activities throughout a day and train coordination and service regulation are then expected to meet the daily passengers' demand. Dwell time control at stations and fixed coasting point in an inter-station run are the current practices to regulate train service in most metro railway systems. However, a flexible and efficient train control and operation is not always possible. To minimize energy consumption of train operation and make certain compromises on the train schedule, coast control is an economical approach to balance run-time and energy consumption in railway operation if time is not an important issue, particularly at off-peak hours. The capability to identify the starting point for coasting according to the current traffic conditions provides the necessary flexibility for train operation. This paper presents an application of genetic algorithms (GA) to search for the appropriate coasting point(s) and investigates the possible improvement on fitness of genes. Single and multiple coasting point control with simple GA are developed to attain the solutions and their corresponding train movement is examined. Further, a hierarchical genetic algorithm (HGA) is introduced here to identify the number of coasting points required according to the traffic conditions, and Minimum-Allele-Reserve-Keeper (MARK) is adopted as a genetic operator to achieve fitter solutions.

A fiber Bragg grating sensor system for train axle counting

Railway signaling facilitates two main functions, namely, train detection and train control, in order to maintain safe separations among the trains. Track circuits are the most commonly used train detection means with the simple open/close circuit principles; and subsequent adoption of axle counters further allows the detection of trains under adverse track conditions. However, with electrification and power electronics traction drive systems, aggravated by the electromagnetic interference in the vicinity of the signaling system, railway engineers often find unstable or even faulty operations of track circuits and axle counting systems, which inevitably jeopardizes the safe operation of trains. A new means of train detection, which is completely free from electromagnetic interference, is therefore required for the modern railway signaling system. This paper presents a novel optical fiber sensor signaling system. The sensor operation, field setup, axle detection solution set, and test results of an installation in a trial system on a busy suburban railway line are given.

Scheduling coordination through negotiation between train service providers in an open railway access market

A schedule coordination problem involving two train services provided by different operators is modeled as an optimization of revenue intake. The coordination is achieved through the adjustment of commencement times of the train services by negotiation. The problem is subject to constraints regarding to passenger demands and idle costs of rolling-stocks from both operators. This paper models the operators as software agents having the flexibility to incorporate one of the two (and potentially more) proposed negotiation strategies. Empirical results show that agents employing different combination of strategies have significant impact on the quality of solution and negotiation time.

Regulation of train service by coasting control in metro railway system

To maximise the capacity of the rail lineand provide a reliable service for pas-sengers throughout the day, regulation of train service to maintain steady service headway is es-sential. In most current metro systems, train usually starts coasting at a fixed distance from the departed station to achieve service regulation. However, this approach is only effective with re-spect to a nominal operational condition of train schedule but not necessarily the current service demand. Moreover, it is not simply to identify the necessary starting point for coasting under the run time constraints of current service conditions since train movement is attributed by a large number of factors, most of which are non-linear and inter-dependent. This paper presents an ap-plication of classical measures to search for the appropriate coasting point to meet a specified inter-station run time and they can be integrated in the on-board Automatic Train Operation (ATO) system and have the potential for on-line implementation in making a set of coasting command decisions.

Coast control of train movement with genetic algorithms

Railway service is now the major transportation means in most of the countries around the world. With the increasing population and expanding commercial and industrial activities, a high quality of railway service is the most desirable. We present an application of genetic algorithms (GA) to search for the appropriate coasting point(s) and investigate the possible improvement on fitness of genes. Single and multiple coasting point control with simple GA are developed to attain the solutions and their corresponding train movement is examined. The multiple coasting point control with hierarchical genetic algorithm (HGA) is then proposed to integrate the determination of the number of coasting points.