Effective search space control for large and/or complex driver scheduling problems |
| |
Authors: | Raymond S K Kwan Ann Kwan |
| |
Institution: | (1) School of Computing, University of Leeds, Leeds, UK;(2) TRACSiS Limited, Leeds, UK |
| |
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. |
| |
Keywords: | Driver scheduling Public transport Set covering Heuristics |
本文献已被 SpringerLink 等数据库收录! |
|