Article ID: | iaor20083278 |
Country: | Germany |
Volume: | 155 |
Issue: | 1 |
Start Page Number: | 417 |
End Page Number: | 435 |
Publication Date: | Nov 2007 |
Journal: | Annals of Operations Research |
Authors: | Kwan Raymond S.K., Kwan Ann |
Keywords: | personnel & manpower planning, programming: integer, heuristics |
For real life bus and train driver scheduling instances, the number of columns in terms of the set covering/partitioning ILP model could run into billions making the problem very difficult. Column generation approaches have the drawback that the sub-problems for generating the columns would be computationally expensive in such situations. This paper proposes a hybrid solution method, called PowerSolver, of using an iterative heuristic to derive a series of small refined sub-problem instances fed into an existing efficient set covering ILP based solver. In each iteration, the minimum set of relief opportunities that guarantees a solution no worse than the current best is retained. Controlled by a user-defined strategy, a small number of the banned relief opportunities would be reactivated and some soft constraints may be relaxed before the new sub-problem instance is solved. PowerSolver is proving successful by many transport operators who are now routinely using it. Test results from some large scale real-life exercises will be reported.