Received 31 December 2015; accepted 22 February 2016; published 25 February 2016
With around $2.0 billion in export earnings, Australia is the world’s third largest exporter of raw sugar. In Australia, there are about 380,000 hectares, 24 mills and 4400 sugarcane farming entities growing sugarcane. Moreover, around 85% of exported raw sugar production is from Queensland (a northeast state of Australia). According to Australian Sugar Milling Council  , the sugar industry employs over 16,000 people across the growing, harvesting, milling and transport sectors, among which the transport sector is a critical part of the whole process due to the significance of transporting the sugarcane crop between farms and mills in time. In a practical sugarcane transport system, a daily schedule is implemented to meet the demands from both the harvesters and the mills. According to the feedback from our industry partners, over 35% of the total cost of sugarcane industry in Australia is incurred by sugarcane transportation.
The sugarcane transport system is a complex industrial management system, as it needs to schedule a large set of locomotives, bins, train runs, railway sections with satisfaction of specific demands from harvesters and the mills. A typical sugarcane railway network comprises single-track sections and multiple-track sections; and performs two main tasks: delivering the empty bins from the mills to the harvesters at farms; and collecting the full bins of sugarcane to the mills. Moreover, integration of several different sub-modules such as harvesting, delivering, unloading and milling is a requirement in the whole supply chain of the Australian sugar industry. The implementation of more efficient schedules is essential to reduce the overall cost and remove the negative effects on the sugar production system. For example, optimising the delivery and collection times can result in significant improvements on the throughput of the harvesters and the mills.
A short literature review related to sugarcane train scheduling is given as follows. Abel et al.  reported on the first automatic scheduler generator for a sugarcane railway system in Australia. This scheduler evolved into SRI’s ACRSS automatic scheduler  and remained the best tool available for this purpose  . Nevertheless, its schedules invariably require considerable modification before implementation. The models of Masoud et al.  -  , including the additional timely delivery and collection model elements, were used to test the model and to evaluate the performance of solution techniques. The objective function in this investigation only aimed to minimising the total running time. Masoud et al.  presented a case study involving a transport system with seven harvesters operating. This harvesting scenario was based on a subset of the Kalamia mill transport system for one typical day from the 2008 crushing season. Hu et al.  indicated that a sugarcane railway system is very complicated especially where there exists only a single track in a jaunting corridor. Li et al.  dealt with a green train scheduling model and implemented it to sugarcane industry. Li et al.  developed a method to produce an optimised schedule for minimising the delay of sugarcane bins, the number of locomotives, and etc. Masoud et al.  solved an advanced sugarcane railway scheduling optimisation model by constraint programming and metaheuristic algorithms. Burdett  developed advanced capacity analysis models for railway systems.
As most of publications in train scheduling are theoretic, one main contribution of this paper is to develop a real-time optimiser to produce an automatic scheduler for a sugarcane rail transport system, which is adapted as an extended parallel-machine job shop scheduling systems with blocking constraints  -  . Thus, the proposed mathematical model of the sugarcane transport system is formulated by mixed integer programming (MIP) in a standard way. Moreover, this extended model includes the additional real-time sugarcane transport constraints such as delivering and collecting bins through the rail system. Regarding the development of efficient solution techniques, the second main contribution of this paper is to propose a set of heuristic algorithms in efficiently solving this complicated sugarcane train scheduling problem. Another main contribution is to present a case study based on the data of Kalamia Sugar Mill in Northern Queensland and to conduct a sensitivity analysis in terms of key parameters   .
The outline of this paper is as follows. In Section 2, a sugarcane rail transport scheduling system is described and its main problem properties are analysed. In Section 3, a MIP model is developed to formulate the sugarcane rail transport scheduling problem. In Section 4, some heuristic solution approaches are presented to solve this complicated optimisation problem in an efficient way. Computational experiments and sensitivity analysis are reported in Section 5. We conclude this paper in the last section.
2. Problem Description
The sugarcane rail transport system applies a daily schedule to satisfy the requirements of the mills and the harvesters. Due to the potential negative effects such as interruptions to the raw sugar production process; delaying the supply of sugarcane to the mills and deteriorating the sugar quality, the sugarcane rail transport system needs to deal with many challenges by developing a mathematical model to optimise the real system. The railway system can generally operate for 24 hours a day, while the harvesting period is limited to about 12 hours each day. A train run consist of a series of operations, which involve activities such as traversing a track section, collecting bins, loading and unloading. In a crossing section, a conflict may occur when one operation may be in the outbound direction and the other may be in the inbound direction.
Figure 1 shows a sample rail network including a set of single-track sections and multiple-track sections that are regarded as crossing loops or sidings (Masoud, 2012). Figure 1 has seven track sections, where sections s2,1, s5,1 and s7,1 contain sidings (for storing empty and full bins for the harvesters). In addition, terminal and intermediate segments are defined in Figure 1. In the terminal segments, the train can travel outbound and then immediately travel inbound without any interruption. For intermediate segments, as shown in Figure 1, the train may go to visit other segments like terminal segment 2 or 3 after traversing intermediate segment 1 in the outbound direction, and return in the inbound direction to visit the intermediate segment in a reverse order. If blocking conditions are occurred in an intermediate segment, this segment would be blocked during the time period of implementing the outbound and inbound operations on it. The blocking time includes the interruption period between a pair of operations in the outbound and the inbound directions when the train is in either segment 2 or segment 3. As a result, the utilisation efficiency of the intermediate segment is further decreased, resulting from the longer blocking time on this segment.
To clarify these issues, assume that the train k1 run includes the path, Mill-s1,1-s2,1-s3,1-s6,1-s7,1-s7,1-s6,1-s3,1-s2,1- s1,1-Mill, where outbound operations O1-O2-O3 are implemented on the intermediate segment. Outbound operations 4 - 5 and inbound operations O6-O7 are implemented on terminal segment 3 continuously. Inbound operations O8-O9-O10 are implemented on the intermediate segment. Blocking the intermediate segment during use of k1, to satisfy the safety conditions, means this segment is blocked during the time period of implementing the operationsO1-O2-O3-O8-O9-O10. This period includes the time of operations O4-O5-O6-O7 since the operations of each segment should be implemented and conducted continuously. As a result, if the train k2 requires the intermediate segment, the waiting time of the train k2 to use the intermediate segment equals the time period of implementing the operations O1-O2-O3-O4-O5-O6-O7-O8-O9-O10 by train k1 which affect the utilisation efficiency of that segment.
The proposed model increases the utilisation efficiency of segments by assuming that intermediate segments have been given separate segment numbers for the outbound and inbound directions (segments 1 and 4 in Figure 2). Segment 1 includes the outbound operations O1-O2-O3 and segment 4 includes the inbound operations O8-O9-O10.
In the outbound and inbound directions of train k1, segment 1 and segment 4 are blocked respectively. As a
Figure 1. A sample sugarcane rail network with three sidings for delivering and collecting.
Figure 2. A single sugarcane rail network after applying model.
result, the waiting time of train k2 is reduced to equal the time period of implementing the outbound operations O1-O2-O3 on segment 1 by train k1. If k1 is in the inbound direction, the waiting time of k2 to catch segment 4 is equal to the time period of the inbound operations O8-O9-O10 of train k1. Blocking segment 1 does not automatically mean that the intermediate segment is blocked completely, since segment 4 can be used by another train k2 while train k1 is using segment 1. This conflict is addressed by the proposed algorithms of the solution approach in section 3 distinguishing between the segment types to prevent using one physical segment by more than one train at the same time.
The efficiency of the blocking segment constraints can be increased further in the proposed models by considering the passing loops in each rail branch (a long segment). Any blocking for any segment which includes a passing point can increase the waiting time of the system and then increase the operating cost and decrease the efficiency of rail section utilisation. Passing points can be passing loops (no activities; no delivering and no collecting) or a long siding (delivering or collecting) with passing loop and can allow for more than one train to pass at the same time.
2.1. Passing Loop without Storage
Each branch which includes a passing loop can be divided into two segments to increase the utilisation of this branch and reduce the waiting time of any train at this branch. As a result, the blocking segment is applied to each part that does not include a passing loop. For example in Figure 3, branch B1 includes a passing loop, so two segments (A1 and A2) are included in it where each segment includes some sections. The passing loop has two parallel tracks (C1 and C2) without storage. Branch B2 has no passing loop so the whole branch is considered as one segment.
2.2. Passing Loop with Storage
Siding types in sugarcane rail system are divided into big sidings that can allow for more than one train to pass and small sidings which do not allow for more than one train to pass at the same time. Small sidings can have a double track section, where one of them is used for sugarcane storage and another for a passing train (only one train at a time). The big sidings can have more than two tracks where one is used for sugarcane storage and other tracks for more than one train passing at a time (parallel machines). Each track in this siding can be considered as one segment that includes one section as shown in Figure 4.
Figure 4 shows a big siding (storage with passing loop) that has a triple section where each section can be a segment and allow for passing trains. Each segment includes only one section where Segments 3, 4 and 5 include sections s3,1, s4,1,s5,1 respectively, implying that blocking segments in this case includes blocking sections.
Figure 3. Rail branch includes passing loop.
Figure 4. Rail siding includes passing point.
3. Mathematical Programming
The sugarcane rail transport system was formulated as a multi-objective optimisation model considering three main operations: harvesting, transporting and milling. The model involves integration between these operations with a large number of constraints to produce an optimal automated scheduler for the sugarcane rail transport system satisfying many objectives at the same time. The transporting operation is the important link between milling and harvesting in an integrated framework. The integrated framework was developed by constructing meaningful relationships between these operations to build an integrated system. The sugarcane rail scheduling problem is mathematically formulated by MIP. The proposed MIP models’ objective functions deal with minimising the makespan objective and the total waiting time together. The models’ constraints include rail operation constraints and sugarcane system constraints. Rail operation constraints are related to trains passing on the rail network and include precedence, order of rail segments, train runs, passing priority, and blocking constraints. The sugarcane transport system constraints include train capacity, siding capacity, mill capacity, empty and full bin requirements, harvester rates, and harvesting times.
K Number of locomotives
Index of locomotives; &
E Number of segments
e Index of a segment;
S Total number of sections for all segments
Index of section sat segment e
Index of operations; &
R Number of locomotives runs
Index of runs of each locomotive; &
Processing time of operation o of locomotive k on section s at segment e
A large enough positive number
Total allotment of bins on each section
Capacity of train k of empty bins, Capacity of train k of full bins
Harvester rate at siding s
Harvester start time at siding s
Starting time of locomotive kin run r for operation o on section s on segment e
Number of full bins collected from siding s by locomotive k during operation o and run r on segment e
Number of empty bins delivered for siding s by locomotive k during operation o and run r on segment e
Equations ((1) and (2)) are defined together to minimise the makespan and the total operating time (TOT) for all train runs in the system.
Equation (3) ensures operation o of locomotive k should be after operation o + 1 of locomotive k on section s of segment e.
Equations (4) and (5) define the scheduling relationship of locomotives k and k' on section s of segment e.
Equation (6) defines the blocking constraints in the whole railway system.
Equations (7) and (8) ensure the deliveries and collections of empty and full bins equal the allotment at each siding.
Equation (9) satisfies the siding capacity.
Equation (10) requires the release of empty bin delivery conditions in the outbound direction.
Equation (11) ensures the collection of full bins in the inbound direction.
Equation (12) ensures no delay time in the first run.
Equation (13) ensures no delay time in delivering to the harvesters. .
Equations ((14) and (15)) ensure that the number of full bins collected is no more than the produced number of full bins at each siding at each run.
4. Solution Techniques
Some previous solution techniques developed to solve the single objective function model are extended and adapted to solve the multi-objective model.
4.1. Siding Neighbourhood Search (SNS) Algorithm
The SNS algorithm was developed to build different paths and routes for each train from any visited point using the idea of neighbourhood change. Active siding (with harvester) neighbourhoods are considered to create new paths for the trains through the sugarcane rail network. This algorithm includes the following main steps:
Step 1. Construct the locomotive runs by assigning the first active siding to visit by the train that has the most urgent need for empty bins considering blocked paths by bins or trains.
Step 2. Construct neighbours list for the visited siding using the three main criteria:
Set the shortest distance from the current siding, to help in reducing the total operating time of each trip.
Set the urgent need for delivering empty bins, to reduce the harvesting delays.
Set the urgent need for collecting full bins because of siding capacity is filled.
Step 3. Select the siding that will be visited by the train from the neighbours list.
Step 4. Update the neighbours list for each siding by removing the sidings that finished their daily allotment.
Step 5. Repeat the second step until the daily total allotments of all sidings are completed.
4.2. Sidings Satisfaction Priorities (SSP) Algorithm
This algorithm was developed to integrate with Siding Neighbourhood Search to produce a global list of all visit priorities for all active sidings in the system. A global list includes all neighbour lists that will be visited by trains in the SNS algorithm to and remove any conflicts between sidings by the filtering operation for the different neighbour lists. The filtering operation takes account of the sugarcane rail objectives and constraints. For instance, two trains visiting one active siding at the same time is not allowed. This list is always updated to provide the traffic office any information about the train trips or the expected paths for each train while processing the trip. The SSP algorithm consists of the following main steps:
Step 1. Construct a global list including all neighbours for all active sidings in SNS algorithm.
Step 2. Set the active sidings list that has high priority to visit.
Step 3. Eliminate any conflicts for the siding visits that will be selected from the high priority list.
Step 4. Update the high priority list and remove visited sidings from the list.
Step 5. Update the global list.
4.3. Rail Conflict Elimination (RCE) Algorithm
As a train conflict through the single rail track is a serious issue, the Rail Conflict Elimination (RCE) Algorithm is developed to resolve complex situations related to the conflicts through the rail network. Such a conflict will affect the safety and the efficiency of the system when two trains wish to pass through the same section at the same time. In this case, the potential conflicts are resolved by the RCE algorithm, as illustrated in Figure 5 and Figure 6.
The main procedure of the RCE algorithm is described below.
Step 1. Select section s.
Step 2. Set trains k and k' require section s.
Step 3. Set the finish times of trains k and k' on same section s.
Step 4. Get the conflict point (s, t) on section s during time t.
Step 5. If the finish time of train k is less than the finish time of train k', thentrain k will be selected to be scheduled first on section s;
Step 7. Else, train k’ is selected first.
Step 8. Backtrack choosing another section.
5. Computational Results
Five trains on a part of a rail network consisting of 22 rail sections including single, double and triple tracks are shown in Figure 7. Figure 7 shows 17 runs from the five trains where the vertical axis shows the different track sections while the horizontal axis shows the time in minutes. This type of graph shows the conflict points, the
Figure 5. Solving conflicts by a delayed train technique.
Figure 6. Solving the conflicts by a slow train technique.
Figure 7. Gantt chart for 5 trains and 17 train runs (different colours for trains).
locations where one train has to wait for another to pass and the length of waiting time. Figure 7 also displays the start time and finish time of each trip, the number of trains used in the system and the time taken in travelling through each section and for delivering and collecting.
Figure 7 shows a conflict point at 150 minute mark between the red and pale blue trains occupying in section 7. The pale blue train wants to go from section 6 through section 7 to section 14. The red train has to go from section 11 through section 7 to section 6. In the scenario, the red train is blocked at section 11 until the pale blue train passes through section 7 and moves into section 14 before the red train use section 7. In practice, many factors can affect the efficiency of the sugarcanerail systems such as number of trains and siding capacity. In this paper, the makespan and the total operating time of the sugarcanerail systems are considered in sensitivity analysis. In terms of the data provided by Kalamia Sugar Mill in Northern Queensland, there are 87 sections, 33 sidings with 4789 bins as a total allotment. The maximum makespan of the system is limited as 72 hours. In a sensitivity analysis, different numbers of trains are tested by comparing the values of the makespans and the total operating times of the obtained schedules.
Figure 8 shows the makespan value and total operating times in minutes for different number of trains where the trains speed is a fixed value, 30 km/h, and the capacity of the sidings is limited. The makespan of 2 trains is 5698.98 minutes and the total operating time equals 9343.2 minutes and the total number of runs = 72 trips. In case of using 2 trains, while the total operating time is low, the makespan is greater than the maximum makespan of the system, namely, three days. Thus, using 2 trains in the system is not sufficient to satisfy the total allotment, implying that the case of 2 trains is not applicable. By increasing the number of trains to be 3 trains, the makespan still is greater than the maximum where the makespan is 4726.8 minutes. Three trains need to run 84 trips in the total operating time is 10,730.88 minutes. Even when the number of trains is increased to be 4 trains, the total allotment is not satisfied as the makespan is 4371.96 minutes. The total number of trips is 102 with the total operating time of 12,413.46 minutes. As a result, the cases of 3 or 4 trains are also not applicable to meet such a daily demand.
As analysed in Figure 8, the case of 5 trains is able to reduce both the makespan and the total operating time, where the makespan of 4186.98 minutes is less than the maximum makespan. Consequently, using 5 trains is the most applicable solution in this case study, as the total operating time is also optimised. The total number of trips 114 trips in total operating time is 13,100.34 minutes. Figure 9 shows the Gantt chart of 5 trains scheduling and the total trips that are used to satisfy the demand of the system for three days. When increasing the total number of trains from 6 to 12, the makespan values keep steady but the total operating times are increasing. This is because the total blocking time of all train runs may be increased due to the use of additional trains through the rail network.
Figure 8. Sensitivity analysis of makespan and total operating time by different numbers of trains.
Figure 9. Gantt chart of sugarcane train schedule using 5 trains.
The sugarcane transport system is very complicated as the mathematical formulation model has a large set of constraints and variables even when the problem size is small. In the proposed MIP model, the system constraints are classified into two main categories: 1) constraints related to the rail operations’ feasibility due to passing of trains without accidents; 2) constraints related to the capacities of sidings and empty/full bins. To efficiently find the near-optimal schedule, Siding Neighbourhood Search (SNS) and Sidings Satisfaction Priorities (SSP) algorithms are developed and integrated in the solution procedure. A Rail Conflict Elimination (RCE) Algorithm is also adapted to resolve the train conflicts through the single rail track with the consideration of train passing constraints. Computational experiments show that the outputs are satisfactory to optimise the performance of the sugarcane transport systems system. Regarding the future research directions, more dynamic and stochastic elements will be considered and incorporated in a reactive sugarcane railway scheduling problem. Moreover, the proposed model in this paper will be extended to investigate an integrated train-track transportation dynamics  -  in a supply chain and applied to Australian sugarcane industry.
The authors acknowledge the funding support of the Sugar Research and Development Corporation, MSF Sugar Limited, Sucrogen Limited, Proserpine Co-operative Sugar Milling Associated Limited, Mackay Sugar Limited, Bundaberg Sugar Limited and Isis Central Sugar Mill Co. Ltd.
 Abel, D.J., Stark, K.P., Murry, C.R. and Demoulin, Y.M. (1981) A Routing and Scheduling Problem for a Rail System: A Case Study. Journal of the Operational Research Society, 32, 767-774.
 Masoud, M., Kozan, E. and Kent, G.A. (2010) A Constraint Programming Approach to Optimise Sugarcane Rail Operations. Proceedings of the 11th Asia Pacific Industrial Engineering and Management Systems Conference, Malaysia, 7-10 December 2010, Vol. 147, 1-7.
 Masoud, M., Kozan, E. and Kent, G.A. (2010) A Comprehensive Approach for Scheduling Single Track Railways. The Annual Conference on Statistics, Computer Sciences and Operations Research, Egypt, Cairo, 45, 19-30.
 Masoud, M., Kozan, E. and Kent, G.A. (2011) A Job-Shop Scheduling Approach for Optimising Sugarcane Rail Operations. Flexible Services and Manufacturing Journal, 23, 181-196.
 Hu, H., Li, K. and Xu, X. (2013) A Multi-Objective Train-Scheduling Optimization Model Considering Locomotive Assignment and Segment Emission Constraints for Energy Saving. Journal of Modern Transportation, 21, 9-16.
 Li, X., Wang, D., Li, K. and Gao, Z. (2013) A Green Train Scheduling Model and Fuzzy Multi-Objective Optimization Algorithm. Applied Mathematical Modelling, 37, 2063-2073.
 Li, X., Chien, C.F., Yang, L.X. and Gao, Z. (2014) The Train Fuelling Cost Minimization Problem with Fuzzy Fuel Prices. Flexible Service and Manufacturing Journal, 26, 249-267.
 Masoud, M., Kozan, E. and Kent, G.A. (2015) Hybrid Metaheuristic Techniques for Optimising Sugarcane Rail Operations. International Journal of Production Research, 53, 2569-2589.
 Burdett, R.L. (2015) Multi Objective Models and Techniques for Analysing the Absolute Capacity of Railway Networks. European Journal of Operational Research, 245, 489-505.
 Liu, S.Q. and Kozan, E. (2009) Scheduling Trains as a Blocking Parallel-Machine Job Shop Scheduling Problem. Computers and Operations Research, 36, 2840-2852.
 Liu, S.Q. and Kozan, E. (2011) Scheduling Trains with Priorities: A No-Wait Blocking Parallel-Machine Job-Shop Scheduling Model. Transportation Science, 45, 175-198.
 Liu, D., Lechner, B. and Freudenstein, S. (2016) Evaluation of High-Speed Track Quality Using Dynamic Simulation of Vehicle-Track Interaction. Journal of Transportation Technologies, 6, 9-14.