The application of constraint logic programming to cane railway scheduling

In Australia, cane transport is the largest unit cost in the manufacturing of raw sugar, making up around 35% of the total manufacturing costs. Producing efficient schedules for the cane railways can result in significant cost savings. This thesis presents a study of using Constraint Logic Programming (CLP) for solving the cane transport scheduling problem. CLP is an extension of logic programming languages that incorporates constraints and constraint solving methods.

The cane railway scheduling problem (CRSP) is a unique problem. Although it shares some characteristics with many well-studied operations research problems it has many properties that made expressing it in a form suitable for CLP a novel challenge. Modern metaheuristic methods such as genetic algorithms and tabu search have been successfully applied to combinatorial optimisation problems including the CRSP. These metaheuristics use a variety of means to sample a subset of the total available solution set. In contrast, CLP relies on forward-checking to reduce the size of the solution set. Forward-checking results in the rejection of infeasible solutions as early as possible in the search. However for the CRSP, forward-checking alone proved to be insufficient to prune the search tree adequately. The novel heuristic labelling approach presented in this thesis proposes the concept of labelling templates to ensure that a good quality subset of possible solutions is tested. This heuristic labelling technique is tailored to the CLP approach and to the CRSP. However the approach should be applicable to other CLP applications.

Encouraging results of the application to several test problems and one real-life case are presented. The results demonstrate that CLP can be used as an effective tool for solving the cane transport scheduling problem. It can also be used as an efficient tool for altering an existing schedule to accommodate real-time changes in the cane transport system. The current integrated cane transport scheduling system that has been developed to address the CRSP does not include a dedicated rescheduling component.