Skip to main content

Über dieses Buch

This proceedings volume consists of papers presented at the Seventh International Workshop on Computer-Aided Scheduling of Pllblic Transport, which was held at th th the Massachusetts Institute of Technology from August 5 to 8 , 1997. In the tradition of alternating Workshops between North American and Europe - Chicago (1975), Leeds (1980), Montreal (1983), Hamburg (1986), Montreal (1990), and Lisbon (1993), Cambridge (Massachusetts, USA) was selected for the Workshop in 1997. As in earlier workshops, the central theme dealt with vehicle and crew scheduling problems and the development of software systems incorporating operations research techniques for operational planning in public transport. However, following the trend that started in Hamburg in 1987, the scope of this Workshop was broadened to include topics in related fields. Two trends underlie this. First, the recognition that the core scheduling issues in public transport have important common elements with other application areas in which extensive work is also underway, and that it is vital to learn from these other initiatives. Second, while scheduling is indeed a core problem in public transport planning, and has shown the first and greatest benefits from computer application, it is intimately related to the preceding tasks in the planning hierarchy, such as service design, and the following tasks such as operations control and public information.



Crew Scheduling

Solution of Large-Scale Railway Crew Planning Problems: the Italian Experience

Crew scheduling is a very well known problem which has been historically associated with airlines and mass transit companies; recently railway applications have also come on the scene. This is especially true in Europe, where deregulation and privatization edicts are forcing a re-organization of the rail industry and better productivity and more efficient services are strongly required by the market and the public. Therefore, this sector is showing increasing interest in Operations Research and Management Science. Railway crew planning represents a hard problem due to both the dimensions and the operational/regulation constraints involved. This paper describes the development of a new crew planning system set up by Ferrovie dello Stato SpA (the Italian railway company) in co-operation with the University of Bologna.
Alberto Caprara, Matteo Fischetti, Pier Luigi Guida, Paolo Toth, Daniele Vigo

Crew Pairing for a Regional Carrier

This paper addresses the problem of generating valid crew pairings in the context of a regional air carrier. The classical column generation solution approach based on extensive enumeration of all valid duties is impractical in this context where duties comprise ten to twelve legs. In order to alleviate this difficulty, we propose an alternative approach which takes into account all work rules and air traffic regulations during the construction of valid crew pairings. Two network structures compatible with this approach are described. The first is a leg-on-node model while the second involves a leg-on-arc representation. Computational results obtained with the GENCOL optimizer on problems varying from 63 to 986 legs lead us to conclude that the leg-on-arc representation is substantially more efficient. In addition, we study the cost impact of three changes in the operating scenario. Finally, we illustrate how bounded perturbation variables virtually eliminate degeneracy, hence significantly decreasing CPU time.
Guy Desaulniers, Jacques Desrosiers, Arielle Lasry, Marius M. Solomon

An Improved ILP System for Driver Scheduling

Mathematical programming approaches to driver scheduling have been reported at many previous workshops and have become the dominant approach to the problem. However the problem frequently is too large for mathematical programming to be able to guarantee an optimal schedule. TRACS II, developed at the University of Leeds, is one such mathematical programming-based scheduling system. Several improvements and alternative solution methods have now been incorporated into the mathematical programming component of the TRACS II system, including a column generation technique which implicitly considers many more valid shifts than standard linear programming approaches. All improvements and alternative strategies have been implemented into the mathematical programming component of TRACS II to allow different solution methods to be used where necessary, and to solve larger problems in a single pass, as well as to produce better solutions. Comparative results on real-world problems are presented.
Sarah Fores, Les Proll, Anthony Wren

An Exact Branch and Cut Algorithm for the Vehicle and Crew Scheduling Problem

We present a new model for the vehicle and crew scheduling problem in urban public transport systems by combining models for vehicle and crew scheduling that cover a great variety of real world aspects, including constraints for crews resulting from wage agreements and company regulations. The main part of the model consists of a set partitioning formulation to cover each trip. A column generation algorithm is implemented to calculate the continuous relaxation which is embedded in a branch and bound approach to generate an exact solution for the problem. To improve the lower bounds, polyhedral cuts basing on clique detection and a variant of the column generation algorithm that suits the cuts were tested.
Christian Friberg, Knut Haase

Driver Scheduling Using Genetic Algorithms with Embedded Combinatorial Traits

The integer linear programming (ILP) based optimization approaches to driver scheduling have had most success. However there is scope for a Genetic Algorithm (GA) approach, which is described in this paper, to make improvements in terms of computational efficiency, robustness, and capability to tackle large data sets. The question “What makes a good fit amongst potential shifts in forming a schedule?” is pursued to identify combinatorial traits associated with the data set. Such combinatorial traits are embedded into the genetic structure, so that they would play some role in the evolutionary process. They could be effective in narrowing down the solution space and they could assist in evaluating the fitness of individuals in the population.
The first stage of research uses as a starting point the continuous solution resulting from relaxing the integer requirement of an ILP model for driver scheduling. The continuous solution consists of a relatively small set of shifts, which usually contains a high proportion of the shifts in the integer solution obtained. The aim is to derive a GA to evolve from the non-integer solution to yield some elite schedules for further exploitation of combinatorial traits. This first stage is already very effective, yielding in some test cases schedules as good as those found by ILP.
The second stage of research is still ongoing. The aim is to extract from the fittest individuals in the population various forms of combinatorial traits. The genetic structures are then dynamically transformed to make use of the traits in future generations.
Ann S. K. Kwan, Raymond S. K. Kwan, Anthony Wren

An Integrated Approach to Ex-Urban Crew and Vehicle Scheduling

Scheduling of vehicles and crews, traditionally performed sequentially by scheduling vehicles prior to crews, has to be carried out simultaneously in particular settings such as the ex-urban mass transit, where crews are tightly dependent on vehicles’ activity or crews’ dead-headings are highly constrained. In this paper we propose an integrated approach to vehicle and crew scheduling which exploits the network structure of the problem. A heuristic method based on Lagrangean relaxation is presented, which determines a set of pieces of work suitable for both vehicle activities as well as for crew duties. Crew duties are fixed step by step, while vehicles are scheduled once all the trips have been partitioned into pieces. Extended use is made of Bundle methods for polyhedral functions and algorithms for constrained shortest paths and assignment within a dual greedy heuristic procedure for the set partitioning problem. Computational results are provided for Italian public transit operators, which show some improvements over the results of the sequential approach.
Andrea Gaffi, Maddalena Nonato

Producing Train Driver Schedules Under Differing Operating Strategies

The privatization of British Rail into twenty five train operating companies and three freight companies has highlighted the need for each company to have efficient operating schedules. Manpower costs are a significant element in any transport organization, and the ability to minimize these is seen as crucial to the effective running of these companies. In addition, the need to try out different operating strategies is gaining in importance as the search for cost cutting progresses.
Following a feasibility study conducted with British Rail in 1990–91 the paper describes more recent work in which a new driver scheduling system TRACS II has been developed to take account of the conditions relating specially to the rail situation.
Taking data from several train operating companies and talking to many others, both passenger and freight, a database of train work exhibiting a wide variety of different operating strategies has been established. This has enabled the development of new software tools and indicated new areas where further research could be useful.
The driver schedules produced for the train companies have shown savings in manpower requirements over those currently in operation. This situation has been achieved consistently, and savings improved as new techniques developed through the course of the work. The ease with which the drivers’ labor agreement could be changed has greatly impressed the staff in the companies with whom we have worked and further research has been independently promoted. The paper will show how these savings have been achieved and indicate the types of computer techniques employed.
Ann S. K. Kwan, Raymond S. K. Kwan, M. E. Parker, Anthony Wren

Integrated Scheduling of Buses and Drivers

In Brazil, bus services, which have to meet extraordinary levels of demand and traffic congestion, are generally planned by a city transport authority, and franchised out to several private companies for operation. The nature of the scheduling problem is different from most of those described at previous workshops, because vehicle and driver schedules are developed simultaneously, but on a line by line basis. The present paper describes work carried out on representative Brazilian city schedules using enhancements of the Leeds scheduling systems reported at previous workshops. Although the precise nature of the problem varies among the cities studied, the approaches adopted in this research are similar. The Leeds scheduling software, adapted for the Brazilian situation, is used in a novel way to produce efficient combined bus and driver schedules, with buses being switched between lines to improve efficiency. Already savings have been indicated. The paper includes a detailed exposition of the processes used in one of the cities, serving to emphasize the practical problems which must be addressed in any implementation.
Anthony Wren, Nicolau D. Fares Gualda

Vehicle Scheduling and Service Design

Object Oriented Bus Vehicle Scheduling — the BOOST System

BOOST (Basis for Object Oriented Scheduling of Transport) embraces the object-oriented paradigm, which is much acclaimed for excellent conceptualisation, extensibility and reusability. The VAMPIRES algorithm, originated in the 1960s for scheduling train locomotives and later formed the basis of the BUSPLAN system within the BUSMAN package, has been updated using the object-oriented approach and used as the core scheduling algorithm in BOOST. In this paper the advantages of the object-oriented approach, as compared with the traditional procedural approach, are illustrated through the re-modelling of the VAMPIRES algorithm. Concepts and domain knowledge are abstracted at different levels dependent on the contexts. Thus the object-oriented scheduling processes are clear to understand and easy to extend. BOOST features a Windows- based graphical user interface (GUI). The styles of data management and interactive schedule manipulation utilities are described. Results of testing BOOST against the conventional BUSPLAN and recent practical applications of BOOST are reported.
Raymond S. K. Kwan, Mohammad A. Rahin

Solving Large-Scale Multiple-Depot Vehicle Scheduling Problems

This paper presents an integer linear programming approach with column generation for the NP-hard Multiple-Depot Vehicle Scheduling Problem (MDVSP) in public mass transit. We describe in detail the basic ingredients of our approach that seem indispensable to solve truly large-scale problems to optimality, and we report on computational investigations that are based on real-world instances of three large German public transportation companies. These instances have up to 25,000 timetabled trips and 70 million integer decision variables. Compared to the results obtained with one of the best planning system currently available in practice, our test runs indicate savings of several vehicles and a cost reduction of about 10%.
Andreas Löbel

Exact Algorithms for the Multi-Depot Vehicle Scheduling Problem Based on Multicommodity Network Flow Type Formulations

We compare the linear programming relaxation of different mathematical formulations for the multi-depot vehicle scheduling problem. As a result of this theoretical analysis, we select for development a tree search procedure based on a multicommodity network flow formulation that involves two different types of decision variables: one type is used to describe the connections between trips, in order to obtain the vehicle blocks, while the other type is related to the assignment of trips to depots. We also develop a branch and bound algorithm based on the linear relaxation of a more compact multicommodity network flow formulation, in the sense that it contains just one type of variable and fewer constraints than the previous model. Computational experience is presented to compare the two algorithms.
Marta Mesquita, José Paixão

Timetable Synchronization for Buses

The objective of this work is to create a timetable for a given network cf buses, in order to maximize the synchronization among the buses, namely, to maximize the number of simultaneous arrivals of buses at the connection nodes (transfer nodes) of the network. The data for the problem are as follows: a bus route network, including connection nodes of the bus routes; the number of bus departures for every bus route in the network, during a given time period [O,T]; the traveling time of each bus route to the nodes of the network; maximal and minimal headways between two adjacent departures for each bus route. The decision variables are the departure times of all buses for each route. Creating a timetable with maximal synchronization enables the transfer of passengers from one route to another, with minimum waiting time at the transfer nodes. This problem is a major concern to the public transportation designers, taking into account the satisfaction and convenience of the system’s users. In this work, the problem is formulated as a mixed integer programming problem, and a heuristic algorithm is developed to solve the problem in polynomial time.
Avishai Ceder, Ofer Tal

Transportation Service Network Design: Models and Algorithms

We focus on the problem of large scale service network design for transportation carriers requiring the determination of the cost minimizing or profit maximizing set of transportation services and their schedules, given resource constraints. Examples include determining the set of flights and their schedules for an airline; determining the routing and scheduling of tractors and trailers in a trucking operation; and jointly determining the aircraft flights, ground vehicle and package routes and schedules for a provider of express shipment service. In this paper, we survey network design literature, and present a general modeling framework and solution approach for large-scale transportation service network design.
Daeki Kim, Cynthia Barnhart

Locomotive Assignment Using Train Delays

The locomotive assignment problem is to provide at minimum cost sufficient motive power to pull all the trains of a timetabled schedule. Optimization methods for large scale problems are based on multi-commodity flow models with additional restrictions, solved on a rolling horizon. Branch-and-bound strategies are used to find integer solutions. When there is an insufficient number of locomotives, some companies rent additional units while others prefer to postpone train departures. In this paper, we propose a method that finds a feasible solution by delaying the departure of some trains, according to their types. The numerical results using data from the company CN North America show that with a total of about 38 hours of delay time, all the train requirements could be satisfied for a one-week planning problem involving 1988 train segments. When the train requirements are satisfied, the cost penalties associated with undercovering are significantly reduced, and consequently, the integrality gap is decreased. In our numerical experiments, this gap decreases by 2% on average.
Koorush Ziarati, François Soumis, Jacques Desrosiers

Real-Time Control, Demand Responsive Systems and Information Systems

Optimal Real-Time Control Strategies for Rail Transit Operations During Disruptions

Rail transit systems are frequently subject to short term disruptions which temporarily block traffic, leading to increased passenger waiting times and overcrowding of trains. This paper focuses on the development of a real-time decision support system for rail transit operations. We develop a deterministic model of a rail system, and mixed integer programming formulations for several holding and short-turning strategies. We apply the formulations to problem instances based on the MBTA Red Line and demonstrate that passenger waiting time can be significantly reduced (on the order of 15–50%) by applying the resulting controls. We show that the great majority of benefits can be realized by applying only limited control actions on a small set of trains. Our formulations determine optimal control strategies, typically in less than 30 seconds.
Susan W. O’Dell, Nigel H. M. Wilson

Modeling Real-Time Control Strategies In Public Transit Operations

This paper presents recent research to model and solve real-time transit operations control problems. Types of control strategies studied include deadheading, expressing, and holding, both single and in combination. We formulated mathematical models for these control problems assuming real-time vehicle location information available. Important properties of the models are proved and illustrated. Efficient algorithms are developed for solving the control models. The advantages, disadvantages, and conditions for each type of control strategy are investigated. We show that while station-skipping strategies such as deadheading and expressing work in a totally different manner from holding, a coordinated combination of them results in the most effective and least disruptive control policies. Using AVI data collected for the MBTA Green Line (Boston, MA), the computational results show the control models are generally quite effective. The algorithms are also tested in situations where there are significant stochastic disturbances. Under stochastic conditions model performance is found to decline only moderately.
Xu Jun Eberlein, Nigel H. M. Wilson, David Bernstein

Knowledge-Based Decision Support System for Real-Time Train Traffic Control

Modern public transport and train traffic systems have to fulfill increasing demands on service reliability and availability. Train operators can only satisfy these requirements by quickly developing an efficient action in case of traffic disturbances. This paper describes a dispatching support system which is intended for use in railway operation control systems, but could also be useful for other kinds of public transport. The system consists of a knowledge-based decision support system, a simulation tool and a graphical user interface. The assistance consists of conflict detection, display of relevant information, prediction of certain dispatching measures’ impacts, and proposals for appropriate dispatching actions. Thus, the decision support system should significantly improve traffic performance, reliability, and customer satisfaction.
Alexander Fay, Eckehard Schnieder

Requirement for, and Design of, an Operations Control System for Railways

In this paper, we discuss computer-based systems that support operations control for railways. Specifically, we focus on the design of decision support tools for dispatchers. We have studied requirements of systems supporting operations control processes from the expert/user point of view for the German railway, “Deutsche Bahn AG.” The main goal is to help dispatchers ensure passenger traffic with the best possible quality in a dense network with more than 30,000 trips daily. We suggest that such a computer-based system must support the dispatcher in recognizing forthcoming conflicts as early as possible, rescheduling of passenger connections taking into account customers’ acceptance and cost, and reallocating vehicles/crews in a convenient way.
We represent a knowledge-based, object-oriented system architecture that includes components for information management, simulation, and optimization. Besides the scheduled state of a transportation system, our model also covers the actual (until now) and expected (in the future) states. The decision support system automatically recognizes conflict situations, such as missed passenger connections due to trains being delayed. What-if analyses can be performed to support the estimation of network-wide effects of a dispatcher’s decision. Expert’s knowledge rating possible decisions may be formalized and stored in the system to help in generating later decision proposals. Remote Java-based clients provide service point employees and passengers with station overviews and alternative connections based on the actual state of the network. Vehicle rescheduling is currently in progress.
Leena Suhl, Taïeb Mellouli

Telebus Berlin: Vehicle Scheduling in a Dial-a-Ride System

Telebus is Berlin’s dial-a-ride system for handicapped people who cannot use the public transportation system. The service is provided by a fleet of about 100 mini-buses and includes assistance in getting in and out of the vehicle. Telebus has between 1,000 and 1,500 transportation requests per day. The problem is to schedule these requests onto the vehicles such that punctual service is provided while operation costs are minimized. 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 of selecting a set of orders such that the traveling distance of the vehicles within the orders is minimal is a set partitioning problem that can be solved 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 bus tours such that each order is serviced once and such that the total traveling distance of the vehicles is minimum is again a set partitioning problem that is solved 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 has been in operation at Telebus since July 1995. Its use made it possible for Telebus to serve about 30% more requests per day with the same resources.
R. Borndörfer, M. Grötschel, F. Klostermeier, C. Küttner

Advanced Technologies in the Design of Public Transit and City Information Systems

Passenger information is an important factor in improving the acceptance of public transit services. Since mobility should be viewed in a more general context, information must not be limited to public transit, and information relevant to the various user groups and different trip purposes should be included. Therefore, a modular expert system has been developed, to fit the required functionality. The most important technical aspects are a detailed data structure, an efficient knowledge based search procedure to calculate connections between any origin and destination point in street networks and public transit networks, and a favourable processing speed. Beside these factors the design of the user interface forms a second focal point, especially concerning user friendly dialog, a uniform structure of screens, and the usage of common icons and pictograms. In addition, multimedia elements have been used to form an attractive product. A passenger information system based upon the presented concept has been implemented in Dresden and has been in operation since 1995.
Joachim R. Daduna, Kamen Danowski

An Overview of Models and Techniques for Integrating Vehicle and Crew Scheduling

In this paper, the problem of integrating vehicle and crew scheduling is considered. Traditionally, vehicle and crew scheduling have been dealt with in a sequential manner, where vehicle schedules are determined before the crew schedules. The few papers that have appeared in the literature have in common that no comparison is made between simultaneous and sequential scheduling, so there is no indication of the benefit of a simultaneous approach. In order to get such an indication before even solving the integrated problem, we propose a method to solve crew scheduling independently of vehicle scheduling. We introduce a mathematical formulation for the integrated problem, and briefly outline algorithms. The paper concludes with computational results for an application to bus scheduling at the public transport company RET in Rotterdam, The Netherlands. The results show that the proposed techniques are applicable in practice. Furthermore, we conclude that the effectiveness of integration as compared to a sequential approach is mainly dependent on the flexibility in changing buses during a duty.
Richard Freling, Albert P. M. Wagelmans, José M. Pinto Paixão


Weitere Informationen