State space relaxation for set covering problems related to bus driver scheduling

This paper reports on a lower bound technique based on state space relaxation for a dynamic program associated with a particular class of covering problems related with crew scheduling. Both dynamic programming and state space relaxation (SSR) techniques may be applied to any type of set covering problem (SCP), but, in particular, the SSR described in this paper revealed itself as an interesting approach for the bus driver scheduling problem. SSR provides a lower bound on the optimal value for the SCP and some reduction tests are derived in order to reduce the number of columns and rows for the instances. Also, feasible solutions may be built upon the SSR solutions yielding an upper bound on the optimum. Computational experience with real life test problems show that the technique described in this paper is worthwhile trying when dealing with such applications. In fact, for most of the cases, the authors were able to improve on the quality of the feasible solutions obtained through the using of the greedy heuristics described in the literature for the set covering problem.