Quality of driver work schedules significantly impacts the operating profits of any transit company. Further, developing work schedules is a computationally intensive process.; This thesis presents a mathematical model for developing non-homogeneous driver work schedules in an intercity transit system with multiple fleets. We model this problem as an integer program. We present a column generation procedure in a branching framework to efficiently solve a set covering formulation of the driver scheduling problem.; A solution procedure is developed to find new columns for the column generation master problem. This procedure is based on the structure that we found in the pricing problem. The pricing problem is modeled as a resource constrained shortest path problem. We use Lagrangian relaxation coupled with tabu search to solve the pricing problem. The Lagrangian dual is solved using a subgradient optimization algorithm. Our tabu search procedure includes a set of moves to explore the solution neighborhood for good work schedules.; We design an upper bounding procedure for the set covering formulation based on a greedy randomized approach. A lower bounding procedure for the linear programming value at each node in the branching scheme is also developed.; We conduct computational studies on generating work schedules to service 5, 10, and 16 cities. The performance of our algorithm is measured for varying levels of problem parameters. Our computational study also includes investigating the impact of different policy issues on the labor costs and the quality of work schedules.
展开▼
