Telebus Berlin: Vehicle Scheduling in a Dial-a-Ride System
Appeared in: Lecture Notes in Economics and Mathematical Systems, Proc. of the 7th Int. Workshop on Computer-Aided Transit Scheduling (N. Wilson, Hrsg.), Springer, Berlin (1999) 391-422
| SC 97-23 | Ralf Borndörfer, Martin Grötschel, Fridolin Klostermeier, Christian Küttner
Telebus Berlin: Vehicle Scheduling in a Dial-a-Ride System Appeared in: Lecture Notes in Economics and Mathematical Systems, Proc. of the 7th Int. Workshop on Computer-Aided Transit Scheduling (N. Wilson, Hrsg.), Springer, Berlin (1999) 391-422 | |
Abstract: Telebus is Berlins dial-a-ride system for handicapped
people that cannot use the public transportation system. The service is provided
by a fleet of about 100 mini-busses and includes aid to get in and out of the
vehicle. Telebus has between 1,000 and 1,500 transportation requests per day.
The problem arises to schedule these requests into the vehicles such that
punctual service is provided while operation costs should be minimum. Additional
constraints include pre-rented vehicles, fixed bus driver shift lengths,
obligatory breaks, and different vehicle capacities.
We use a set partitioning approach for the solution of the bus scheduling
problem that consists of two steps. The first clustering step identifies
segments of possible bus tours (``orders) such that more than one person is
transported at a time; the aim in this step is to reduce the size of the problem
and to make use of larger vehicle capacities. The problem to select a set of
orders such that the traveling distance of the vehicles within the orders is
minimal is a set partitioning problem that we can solve to optimality. In the
second step the selected orders are chained to yield possible bus tours
respecting all side constraints. The problem to select a set of such bus tours
such that each order is serviced once and the total traveling distance of the
vehicles is minimum is again a set partitioning problem that we solve
approximately.
We have developed a computer system for the solution of the bus scheduling
problem that includes a branch-and-cut algorithm for the solution of the set
partitioning problems. A version of this system is in operation at Telebus since
July 1995. Its use made it possible that Telebus can service today about 30%
more requests per day for the same amount of money than before.