next up previous
Next: The Crew Scheduling Problem Up: Solving Very LargeCrew Scheduling Previous: Solving Very LargeCrew Scheduling

Introduction

Crew scheduling problems have their great practical importance based on the fact that, in most companies, employee related expenses may rise to a very significant portion of the total expenditures. Therefore, these notoriously difficult combinatorial optimization problems deserve a great deal of attention. In this article, we present a hybrid strategy that is capable of efficiently obtaining provably optimal solutions for some large instances of specific crew scheduling problems. These instances stem from the operational environment of a mass transit company that serves the metropolitan area of the city of Belo Horizonte, in Brazil.

Previous attempts to solve similar crew scheduling problems to optimality, either with Integer Programming (IP) or with Constraint Programming (CP) techniques alone, faced difficulties when handling large scale instances due to a series of factors [2,6,8].

In order to combine the capabilities of both the IP and CP techniques, we developed a hybrid approach to solve larger, more realistic, problem instances. The main idea is to use the linear relaxation of a smaller core problem in order to efficiently compute good lower bounds on the optimal solution value. Using the values of the dual variables in the solution of the linear relaxation, we can enter a column generation phase that computes new feasible duties. This phase is modeled as a constraint satisfaction problem which is then submitted to a constraint solver. The solver returns new feasible duties to be inserted in the IP problem formulation, and the initial phase can be taken again, restarting the cycle. This approach secures the strengths of both the pure IP and the pure CP formulations: only a small subset of all the feasible duties is efficiently dealt with at a time, and new feasible duties are quickly computed only when they will make a difference. The resulting code was tested on some large instances, based on real data. As of this writing, we can solve, in a reasonable time and with proven optimality, instances with an excess of 150 trips and 12 million feasible duties. The resulting code was compiled under the Linux operating system, kernel 2.0, and ran on a 350 MHz desktop PC with 320 MB of main memory.

This article is organized as follows. Section 2 describes the crew scheduling problem. In Section 3, we discuss some difficulties faced by the pure IP and CP approaches. In Section 4, we present the hybrid approach together with some implementation details, and also report on computational results based on real data. Finally, in Section 5, we conclude and discuss further issues.


next up previous
Next: The Crew Scheduling Problem Up: Solving Very LargeCrew Scheduling Previous: Solving Very LargeCrew Scheduling

1999-12-16