Truck driver scheduling in Australia

► We present a model of the Australian Heavy Vehicle Driver Fatigue Law which regulates driving and working hours of truck drivers in Australia. ► We present an exact solution approach for the Australian Truck Driver Scheduling Problem which is guaranteed to find a truck driver schedule complying with the regulation if such a schedule exists. ► We present fast heuristics which require only a small fraction of the computational effort required by the exact algorithm. ► The most effective heuristic can find a feasible schedule for almost all of the instances for which a feasible schedule exists; only in rare cases a feasible schedule can only be found by the exact algorithm. ► The technology developed and discussed in this paper can form the foundation for a successful application for accreditation required in order to operate according to the Basic Fatigue Management or the Advanced Fatigue Management option of the regulation.