Dispatching buses in parking depots

Very often, space is a scarce resource in bus depots located in congested urban areas: Vehicles arriving at the end of their trips are packed together in a rather small space. This implies that when a vehicle has to leave to start a new trip, most often other vehicles have to be moved to clear the way. Here a new model, based on ‘Noncrossing Matching’ and ‘Generalized Assignment’, is presented to allocate parking spaces to vehicles in a depot to minimize the shunting cost. The results obtained by applying this approach to a real-life case are discussed.