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.