Bus fleet route planning is often carried out in the following two sequential stages:
1) Based on the demand, determine the trips to be carried out.
2) Assign buses to the trips so as to minimize total costs.

Step 1 fixes the starting time of each trip taking into account the demand, but without considering but assignment. Step 2 optimizes bus assignment without modifying the trip starting times established in step 1. The resulting operating plan is suboptimal: costs can be reduced without significantly affecting the quality of service by slightly modifying the schedules of certain trips a posteriori to reduce the number of vehicles required and the total travelling time.

We propose to fix the departure times during cost minimization in step 2. Step 1 involves only the determination of an interval during which each trip must begin to ensure an adequate quality of service.

The bus assignment problem with fixed departure times can be formulated as a minimum cost flow problem whose optimal solution is easily obtained [8]. With flexible departure times, the problem becomes more difficult. Good solutions have been obtained within acceptable computation times using heuristic methods. One method which is particularly suitable for this type of problem is that developed by Bokinge and Hasselstrom [3] and integrated into the Volvo Traffic Planning Package. The optimal method proposed here is capable of solving problems encountered in practice. Results for problems with 128 and 158 departures are presented in section 10. The problems come from two Swedish cities and were suggested to us by the authors of [3].