Telebus is Berlin's dial-a-ride service for handicapped people. Every day, about 2,000 transportation orders are scheduled into tours for more than 100 minibuses, which are rented by Telebus on demand. This project was concerned with the development of a vehicle scheduling optimization tool, based on a set partitioning approach. This tool is in daily use at Telebus since June 03, 1995. The result of the optimization is that a 30% increase in transports could be coped with at zero extra costs.
Problem
Like many other cities, Berlin offers to mobility disabled people a special transportation service. The so-called Telebus provides door-to-door transportation in special minibusses as well as mobility aid at the pick-up and the drop-off point. Telebus is a dial-a-ride system. Every entitled user (currently more than 25,000 people) can order some 50 rides per month at Telebus's telephone center. A regular order is placed one day in advance (later so-called ``spontaneous rides'' are provides as possible). At the eve of the day before a particular day of operation, about 2,000 such orders are scheduled into a fleet of mini-busses that Telebus rents on a daily basis from charitable organizations and commercial companies.
Telebus can transport passengers individually or in so-called clusters, i.e., sequences of rides that involve loads of more than passenger at a time. Typical examples of such clusters are concatenations (a passenger watches a pick-up of another), insertions (a passenger watches the pick-up and the drop-off of another), multiple concatenations and/or insertions, and group rides. A rotation for a Telebus consists of a pull-out from a depot, a sequence of clusters and individual rides connected by deadhead trips, one or several breaks for the drivers, and a final pull-in trip to the depot. The vehicle scheduling problem at Telebus is to choose the right fleet and appropriate vehicle rotations to service all orders.
There are two main objectives, namely, maximization of service quality, i.e., punctuality and total service time, and minimization of operation costs. These goals are, of course, competing. Telebus compromises by establishing quality rules and optimizing within these rules for minimum costs.
Telebus has to take six kinds of vehicle scheduling rules into account. The first group are the mentioned service quality rules. There is a maximum deviation of the requested arrival (or delivery) time, and there is a limit on the maximum travel time in excess of the shortet route. A second group are vehicle capacity constraints. There are different types of passengers (with foldable and non-foldable wheelchairs, ambulatories, with and without companion) and different types of minibusses with varying transportation capacities. Third, Telebus itself sets restrictions on the "depth" and "length" of clusters to safeguard against lateness or vehicle breakdowns. Fourth, there is a group of rules for the special treatment of certain orders, e.g., that a mentally disabled person is transported by a certain driver. The fifth group are labor regulations for bus drivers such as maximum duty and driving time, lenghts and positions of breaks, etc. Finally, there are constraints on the available number of vehicles of certain types at the various depots.
Method
The vehicle scheduling problem at Telebus belongs to a type of scheduling problems where a set of tasks has to be organized into sequences complying with complex rules. Such problems can be attacked with a set partitioning approach of combinatorial optimization.
In the Telebus project, we applied this technique twice in a two-step solution approach. The idea is to schedule in a first "clustering phase" orders into clusters, and to concatenate in a second "chaining phase" these clusters into tours. The advantage of this approach is that the clustering phase is well-suited to deal with the "local" scheduling rules concerning quality, vehicle capacities, cluster construction, and the treatment of individual orders. When the clusters are known, the chaining phase has a chance to deal with the "global" constraints regarding labor regulations and vehicle availabilities. The disadvantage is, of course, that it is not clear how to construct a set of clusters that is a good (or the best) basis for the construction of tours without already knowing these tours. We try to get into this direction by determining a set of clusters of minimum total internal travelling time, i.e., travelling time within the clusters.
The starting point for our clustering and chaining approaches are scheduling graphs. The nodes of the clustering graph correspond to depots, pick-ups, and drop-offs of individual orders, connected by dead-head trips. Associated with the pick-up and drop-off nodes are time windows. Clusters correspond to paths in this graph and the clustering problem becomes a problem to partition the nodes of the scheduling graph into a cost minimal set of cluster-paths. It turns out that, in the Telebus case, it is possible to enumerate all possible clusters and that the resulting integer programming set partitioning problem can be solved within a couple of minutes to proven optimality.
The graph in the chaining approach is similar, except that the non-depot nodes now correspond to clusters. However, this time, it is not possible to enumerate all possible tours. In the Telebus project, we decided to generate a hopefully representative collection of some hundred thousand tours and determine their best combination again by an integer programming set partitioning solver. It turns out that the chaining problems are much harder than the clustering ones, and we can in general not solve them to optimality. But we can provide heuristic solutions that still improve the scheduling quality at Telebus significantly.
Results
Our set partitioning optimization tool is part of the Telebus computer system IntraCity, developped by the ZIB spin-off company Intranetz Ltd, founded by two coworkers of this project. The system is in operation at Telebus since June 03, 1995. It resulted in a significant improvements in the service quality at Telebus, in particular concerning deviations from requested pick-up times. The result of the optimization was that a 30% increase in the number of orders per day due to the rising popularity of Telebus in the Eastern part of Berlin at that time could be coped with at zero extra cost.
