A heuristic for the bus driver scheduling problem

In this paper a flexible and interactive heuristic for the bus crew scheduling problem is presented. The problem of crew scheduling arises in the context of the broader process of operational planning and control of urban transportation services. An introduction to the global problem, together with a reference to the GIST Decision Support System in which the heuristic is being tested, are presented. The crew scheduling problem is then described, and the way the problem is handled in the Public Transportation Company of Porto – STCP – is presented (this is the case study used in this work). The ‘run-cutting’ heuristic method developed here is then described with detail. Particular attention is paid to the interactive nature of the approach adopted. This interaction is achieved with the aid of some specially designed interfaces, that allow ‘what-if’ type analyses and the generation of better solutions. The solutions can then be visualised with a software component allowing their evaluations and the test of the heuristic. Several real instances were solved. Their resolution shows that the software developed in this work can be a useful tool for helping the planning process. Finally, a critical overview of the work is presented and future areas of research are identified.