This thesis describes the development of a bus crew scheduling method, based on a set partitioning model, for the Christchurch Transport Board, New Zealand. It also examines in detail the effects of the high degree of degeneracy in scheduling set partitioning models. Degeneracy can cause severe computational difficulties because it inflates the number of simplex iterations needed to solve the set partitioning linear programme. In this thesis, it is shown that a maximum-pivot leaving variable criterion can considerably improve the performance of the simplex method, but that this alone is insufficient. Experiments with several degeneracy-resolving techniques have been performed on a class of highly degenerate problems arising from an air crew rostering application, and the results are discussed. Before the set partitioning model can be applied to scheduling, the problem size must be heuristically reduced. Therefore the overall Christchurch system is divided into several subsystems which are solved sequentially. Also, a three-stage method has been developed which essentially considers each type of duty individually. At the first stage, meal-breaks are allocated carefully to reduce the effects of the loss of interaction among the subproblems. A further heuristic reduction technique is then applied to each subproblem, not only to reduce its size but also to improve its integer properties. The resulting solution method has been applied to the Christchurch weekday scheduling problem. A special technique for the Sunday scheduling problem has also been developed. The two methods are described and the promising results which have been achieved are discussed. / Whole document restricted, but available by request, use the feedback form to request access.
| Identifer | oai:union.ndltd.org:ADTP/275356 |
| Date | January 1988 |
| Creators | Falkner, Julie Carolyn |
| Publisher | ResearchSpace@Auckland |
| Source Sets | Australiasian Digital Theses Program |
| Language | English |
| Detected Language | English |
| Rights | Whole document restricted but available by request. Items in ResearchSpace are protected by copyright, with all rights reserved, unless otherwise indicated., http://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm, Copyright: The author |
Page generated in 0.002 seconds