Parking buses in a depot using block patterns: A Benders decomposition approach for minimizing type mismatches

In a transit authority bus depot, buses of different types arrive in the evening to be parked in the depot for the night, and then dispatched in the morning to a set of routes, each of which requests a specific bus type. A type mismatch occurs when the requested type is not assigned to a morning route. We consider the problem of assigning the buses to the depot parking slots such that the number of mismatches is minimized, under the constraint that the buses cannot be repositioned overnight. As in Hamdouni et al. Dispatching buses in a depot using block patterns. Technical Report, Les Cahiers du GERAD G-2004-51, HEC Montreal, Montreal, Canada, 2004, Transportation Science, to appear], we seek robust solutions by assigning a block pattern to each depot. This pattern partitions the lane into at most two blocks, each block containing buses of a given type. Since it may not be possible to respect the selected block patterns, the problem also involves a second objective which is to minimize the discrepancy between the bus type assignment to the parking slots and the block patterns. In this paper, we first study the simplified case where only the second objective is taken into account. We model this simplified problem as an integer linear program and show that practical instances of it can easily be solved using a commercial MIP solver. Then we formulate the general case as an extension of the simplified model and propose to solve it with a Benders decomposition approach embedded in a branch-and-bound procedure. This procedure is required because the Benders decomposition yields a subproblem with integrality constraints. Of particular interests, we develop strong pruning criteria and an innovative branching strategy that imposes decisions on the master problem variables which already take integer values. Computational results for the general case are also reported.