Constraint-based local search for container freight rail scheduling

A traditional container rail service is based on regular timetables. This causes a risk that some customers may turn away if their preferred itinerary is not attainable and the take-up of some services in a fixed schedule may be low and therefore not profitable. To increase railway's profitability and competitiveness, a demand responsive schedule would be advantageous. The decision support model and algorithms for producing a schedule in advance of the weekly operation is the main subject of this thesis.

The container rail scheduling problem is modelled as a constraint satisfaction problem in which the rail business criteria and operational constraints are represented as soft and hard constraints respectively. A constraint-based local search algorithm is developed to solve problems of realistic size. The algorithm includes strategies for accepting non-improving moves and randomised selection of violated constraints and variables to explore. These strategies aim to achieve diversified exploration of the search space. Different measures of the constraint violation are also used to drive the search to promising solution regions.

A predictive choice model is introduced for search intensification to improve further the quality of solutions for the problem. With sufficient trial history, the model will predict a good choice of value for a variable. The variable will be fixed at its predicted value for a dynamically determined number of trials. At this point, the propagation of consistency between the variables is enforced, leading to intensified exploration of the search space. Experimental results, based on real data from the Royal State Railway of Thailand, have shown good computational performance of the approach and suggested benefits can be achieved for both the rail carrier and its customers.

Finally, the proposed algorithm for rail scheduling has been adapted to solve the generalised assignment problem, a well-known hard combinatorial optimisation problem. The experimental results have shown that the proposed method can obtain high quality solutions that are as good as or close to the solutions obtained from the existing methods, but with using significantly less computational time. This suggests that generalising the method may be a promising approach for other combinatorial problems in which all decision variables in the model are binary and where quick and high quality solutions are desirable.