Effective search space control for large and/or complex driver scheduling problems

Effective search space control for large and/or complex driver scheduling problems

0.00 Avg rating0 Votes
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: ,
Keywords: personnel & manpower planning, programming: integer, heuristics
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.