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.

Real-time performance modelling of a sustained attention to response task

Vigilance declines when exposed to highly predictable and uneventful tasks. Monotonous tasks provide little cognitive and motor stimulation and contribute to human errors. This paper aims to model and detect vigilance decline in real time through participant’s reaction times during a monotonous task. A lab-based experiment adapting the Sustained Attention to Response Task (SART) is conducted to quantify the effect of monotony on overall performance. Then relevant parameters are used to build a model detecting hypovigilance throughout the experiment. The accuracy of different mathematical models are compared to detect in real-time – minute by minute - the lapses in vigilance during the task. We show that monotonous tasks can lead to an average decline in performance of 45%. Furthermore, vigilance modelling enables to detect vigilance decline through reaction times with an accuracy of 72% and a 29% false alarm rate. Bayesian models are identified as a better model to detect lapses in vigilance as compared to Neural Networks and Generalised Linear Mixed Models. This modelling could be used as a framework to detect vigilance decline of any human performing monotonous tasks.

Constraints of nutrient availability on primary production in two alpine tundra communities

A nutrient amendment experiment was conducted for two growing seasons in two alpine tundra communities to test the hypotheses that: (1) primary production is limited by nutrient availability, and (2) physiological and developmental constraints act to limit the responses of plants from a nutrient-poor community more than plants from a more nutrient-rich community to increases in nutrient availability. Experimental treatments consisted of N, P, and N+P amendments applied to plots in two physiognomically similar communities, dry and wet meadows. Extractable N and P from soils in nonfertilized control plots indicated that the wet meadow had higher N and P availability. Photosynthetic, nutrient uptake, and growth responses of the dominants in the two communities showed little difference in the relative capacity of these plants to respond to the nutrient additions. Aboveground production responses of the communities to the treatments indicated N availability was limiting to production in the dry meadow community while N and P availability colimited production in the wet meadow community. There was a greater production response to the N and N+P amendments in the dry meadow relative to the wet meadow, despite equivalent functional responses of the dominant species of both communities. The greater production response in the dry meadow was in part related to changes in community structure, with an increase in the proportion of graminoid and forb biomass, and a decrease in the proportion of community biomass made up by the dominant sedge Kobresia myosuroides. Species richness increased significantly in response to the N+P treatment in the dry meadow. Graminoid biomass increased significantly in the wet meadow N and N+P plots, while forb biomass decreased significantly, suggesting a competitive interaction for light. Thus, the difference in community response to nutrient amendments was not the result of functional changes at the leaf level of the dominant species, but rather was related to changes in community structure in the dry meadow, and to a shift from a nutrient to a light limitation of production in the wet meadow.

Optimal track access rights allocation for agent negotiation in an open railway market

In open railway access markets, a train service provider (TSP) negotiates with an infrastructure provider (IP) for track access rights. This negotiation has been modeled by a multi-agent system (MAS) in which the IP and TSP are represented by separate software agents. One task of the IP agent is to generate feasible (and preferably optimal) track access rights, subject to the constraints submitted by the TSP agent. This paper formulates an IP-TSP transaction and proposes a branch-and-bound algorithm for the IP agent to identify the optimal track access rights. Empirical simulation results show that the model is able to emulate rational agent behaviors. The simulation results also show good consistency between timetables attained from the proposed methods and those derived by the scheduling principles adopted in practice.

Coast control for mass rapid transit railways with searching methods

With daily commercial and social activity in cities, regulation of train service in mass rapid transit railways is necessary to maintain service and passenger flow. Dwell-time adjustment at stations is one commonly used approach to regulation of train service, but its control space is very limited. Coasting control is a viable means of meeting the specific run-time in an inter-station run. The current practice is to start coasting at a fixed distance from the departed station. Hence, it is only optimal with respect to a nominal operational condition of the train schedule, but not the current service demand. The advantage of coasting can only be fully secured when coasting points are determined in real-time. However, identifying the necessary starting point(s) for coasting under the constraints of current service conditions is no simple task as train movement is governed by a large number of factors. The feasibility and performance of classical and heuristic searching measures in locating coasting point(s) is studied with the aid of a single train simulator, according to specified inter-station run times.

Using poster presentations as assessment of work integrated learning

Background / context: The ALTC WIL Scoping Study identified a need to develop innovative assessment methods for work integrated learning (WIL) that encourage reflection and integration of theory and practice within the constraints that result from the level of engagement of workplace supervisors and the ability of academic supervisors to become involved in the workplace. Aims: The aim of this paper is to examine how poster presentations can be used to authentically assess student learning during WIL. Method / Approach: The paper uses a case study approach to evaluate the use of poster presentations for assessment in two internship units at the Queensland University of Technology. The first is a unit in the Faculty of Business where students majoring in advertising, marketing and public relations are placed in a variety of organisations. The second unit is a law unit where students complete placements in government legal offices. Results / Discussion: While poster presentations are commonly used for assessment in the sciences, they are an innovative approach to assessment in the humanities. This paper argues that posters are one way that universities can overcome the substantial challenges of assessing work integrated learning. The two units involved in the case study adopt different approaches to the poster assessment; the Business unit is non-graded and the poster assessment task requires students to reflect on their learning during the internship. The Law unit is graded and requires students to present on a research topic that relates to their internship. In both units the posters were presented during a poster showcase which was attended by students, workplace supervisors and members of faculty. The paper evaluates the benefits of poster presentations for students, workplace supervisors and faculty and proposes some criteria for poster assessment in WIL. Conclusions / Implications: The paper concludes that posters can effectively and authentically assess various learning outcomes in WIL in different disciplines while at the same time offering a means to engage workplace supervisors with academic staff and other students and supervisors participating in the unit. Posters have the ability to demonstrate reflection in learning and are an excellent demonstration of experiential learning and assessing authentically. Keywords: Work integrated learning, assessment, poster presentations, industry engagement.

Petri net modeling of spatial and temporal constraints in track allocation problem at railway stations

The track allocation problem (TAP) at a multi-track, multi-platform mainline railway station is defined by the station track layout and service timetable, which implies combinations of spatial and temporal conflicts. Feasible solutions are available from either traditional planning or advanced intelligent searching methods and their evaluations with respect to operational requirements are essential for the operators. To facilitate thorough analysis, a timed Coloured Petri Nets (CPN) model is presented here to encapsulate the inter-relationships of the spatial and temporal constraints in the TAP.

Coasting control of train operation by genetic algorithm

Balancing between the provision of high quality of service and running within a tight budget is one of the biggest challenges for most metro railway operators around the world. Conventionally, one possible approach for the operator to adjust the time schedule is to alter the stop time at stations, if other system constraints, such as traction equipment characteristic, are not taken into account. Yet it is not an effective, flexible and economical method because the run-time of a train simply cannot be extended without limitation, and a balance between run-time and energy consumption has to be maintained. Modification or installation of a new signalling system not only increases the capital cost, but also affects the normal train service. Therefore, in order to procure a more effective, flexible and economical means to improve the quality of service, optimisation of train performance by coasting point identification has become more attractive and popular. However, identifying the necessary starting points for coasting under the constraints of current service conditions is no simple task because train movement is attributed by a large number of factors, most of which are non-linear and inter-dependent. This paper presents an application of genetic algorithms (GA) to search for the appropriate coasting points and investigates the possible improvement on computation time and fitness of genes.

Forecasting negative effects of monotony and sensation seeking on performance during a vigilance task

The driving task requires sustained attention during prolonged periods, and can be performed in highly predictable or repetitive environments. Such conditions could create hypovigilance and impair performance towards critical events. Identifying such impairment in monotonous conditions has been a major subject of research, but no research to date has attempted to predict it in real-time. This pilot study aims to show that performance decrements due to monotonous tasks can be predicted through mathematical modelling taking into account sensation seeking levels. A short vigilance task sensitive to short periods of lapses of vigilance called Sustained Attention to Response Task is used to assess participants‟ performance. The framework for prediction developed on this task could be extended to a monotonous driving task. A Hidden Markov Model (HMM) is proposed to predict participants‟ lapses in alertness. Driver‟s vigilance evolution is modelled as a hidden state and is correlated to a surrogate measure: the participant‟s reactions time. This experiment shows that the monotony of the task can lead to an important decline in performance in less than five minutes. This impairment can be predicted four minutes in advance with an 86% accuracy using HMMs. This experiment showed that mathematical models such as HMM can efficiently predict hypovigilance through surrogate measures. The presented model could result in the development of an in-vehicle device that detects driver hypovigilance in advance and warn the driver accordingly, thus offering the potential to enhance road safety and prevent road crashes.

The role of bricolage and resource constraints in high potential sustainability ventures

Sustainability decisions and their impacts may be among the greatest challenges facing the world in the 21st century (Davos 2000). Apart from adaptation on the part of established organizations these challenges are arguably going to require solutions developed by new actors However, young ventures have only recently begun generating research interest within sustainability literature (Shepherd et al. 2009). In particular, little is known about resource behaviours of these ventures and how they adapt to substantial resource constraints. One promising theory that has been identified as a way that some entrepreneurs manage constraints is bricolage: a construct defined as “making do by applying combinations of the resources at hand to new problems and opportunities” (Baker and Nelson 2005: 333). Bricolage may be critical as the means of continued venture success as these ventures are frequently developed in severe resource constraint, owing to higher levels of technical sophistication (Rothaermel and Deeds 2006). Further, they are often developed by entrepreneurs committed to personal and social goals of resourcefulness, including values that focus on conservation rather than consumption of resources (Shepherd et al. 2009). In this paper, using seven novel cases of high potential sustainability firms from CAUSEE we consider how constraints impact resource behaviours and further illustrate and extend bricolage domains previously developed by Baker and Nelson (2005) with recommendations for theory and practice provided.

Effect of group formation on performance, task management and social loafing

Engineering graduates of today are required to adapt to a rapidly changing work environment. In particular, they are expected to demonstrate enhanced capabilities in both mono-disciplinary and multi-disciplinary teamwork environments. Engineering education needs, as a result, to further focus on developing group work capabilities amongst engineering graduates. Over the last two years, the authors trialed various group work strategies across two engineering disciplines. In particular, the effect of group formation on students' performance, task management, and social loafing was analyzed. A recently developed online teamwork management tool, Teamworker, was used to collect students' experience of the group work. Analysis showed that students who were allowed to freely allocate to any group were less likely to report loafing from other team members, than students who were pre-allocated to a group. It also showed that performance was more affected by the presence or absence of a leader in pre-allocated rather than free-allocated groups.

Utilising semantic tags in XML clustering

This paper presents an overview of the experiments conducted using Hybrid Clustering of XML documents using Constraints (HCXC) method for the clustering task in the INEX 2009 XML Mining track. This technique utilises frequent subtrees generated from the structure to extract the content for clustering the XML documents. It also presents the experimental study using several data representations such as the structure-only, content-only and using both the structure and the content of XML documents for the purpose of clustering them. Unlike previous years, this year the XML documents were marked up using the Wiki tags and contains categories derived by using the YAGO ontology. This paper also presents the results of studying the effect of these tags on XML clustering using the HCXC method.

An introduction to the constraints-led approach to learning in outdoor education

Participation in outdoor education is underpinned by a learner's ability to acquire skills in activities such as canoeing, bushwalking and skiing and consequently the outdoor leader is often required to facilitate skill acquisition and motor learning. As such, outdoor leaders might benefit from an appropriate and tested model on how the learner acquires skills in order to design appropriate learning contexts. This paper introduces an approach to skill acquisition based on ecological psychology and dynamical systems theory called the constraints-led approach to skills acquisition. We propose that this student-centred approach is an ideal perspective for the outdoor leader to design effective learning settings. Furthermore, this open style of facilitation is also congruent with learning models that focus on other concepts such as teamwork and leadership.

Modeling circulation of train-set with multiple routing

Planning on utilization of train-set is one of the key tasks of transport organization for passenger dedicated railway in China. It also has strong relationships with timetable scheduling and operation plans at a station. To execute such a task in a railway hub pooling multiple railway lines, the characteristics of multiple routing for train-set is discussed in term of semicircle of train-sets' turnover. In programming the described problem, the minimum dwell time is selected as the objectives with special derive constraints of the train-set's dispatch, the connecting conditions, the principle of uniqueness for train-sets, and the first plus for connection in the same direction based on time tolerance σ. A compact connection algorithm based on time tolerance is then designed. The feasibility of the model and the algorithm is proved by the case study. The result indicates that the circulation model and algorithm about multiple routing can deal with the connections between the train-sets of multiple directions, and reduce the train's pulling in or leaving impact on the station's throat.

Resource constraints in innovation : the role of bricolage in new venture creation and firm development

The emerging theory of ‘bricolage’ as a resource behaviour represents an attempt to address the central entrepreneurship research problem of making systematic sense of entrepreneurs that sometimes manage to create significant new economic activity under what appears to be severe resource constraints (Baker & Nelson 2005). However, despite growing interest in bricolage there is little large scale empirical evidence about the effectiveness and outcomes of using bricolage processes while developing innovative outcomes in nascent and young firms. In this research we test bricolage using different forms of innovation using data from the Comprehensive Australian Study of Entrepreneurial Emergence (CAUSEE) project. Our results indicate overall positive results of bricolage with all forms of innovativeness. A discussion of the results and recommended future research is provided.