Parking buses in a depot with stochastic arrival times

Given buses of different types arriving at a depot during the evening, the bus parking problem consists of assigning these buses to parking slots in such a way that they can be dispatched adequately to the next morning routes without moving them between their arrivals and departures. In practice, the bus arrival times deviate stochastically from the planned schedule. In this paper, we introduce for this problem two solution approaches that produce solutions which are robust to variations in the arrival times. The first approach considers that each arrival can deviate from its planned arrival order (sooner or later) by at most k positions, where k is a predefined parameter. In the second approach, the objective aims at minimizing the expectation of a function positively correlated with the number of buses that make the planned solution infeasible because they arrive too late or too early. In both approaches, the problem is modeled as an integer linear program that can be solved by a commercial mip solver. Computational results obtained on instances derived from a real-world dataset are reported.