Skip to main content

Über dieses Buch

This proceedings volume consists of papers presented at the Sixth International Workshop on Computer-Aided Scheduling of Public Transpon, which was held at the Fund~lio Calouste Gulbenkian in Lisbon from July 6th to 9th, 1993. In the tradition of alternating Workshops between North America and Europe - Chicago (1975), Leeds (1980), Montreal (1983), Hamburg (1987) and again Montreal (1990), the European city of Lisbon was selected as the venue for the Workshop in 1993. As in earlier Workshops, the central theme dealt with vehicle and duty scheduling problems and the employment of operations-research-based software systems for operational planning in public transport. However, as was initiated in Hamburg in 1987, the scope of this Workshop was broadened to include topics in related fields. This fundamental alteration was an inevitable consequence of the growing demand over the last decade for solutions to the complete planning process in public transport through integrated systems. Therefore, the program of this workshop included sections which dealt with scheduling problems and computerized systems for operational planning as well as sections on network planning and data management.



Line Network Planning

The dual set procedure is used to achieve two objectives: firstly, a higher proportion of direct passengers, and secondly to achieve the minimum number of lines as defined by the final nodes of the path network. In contrast to familiar planning procedures, the set M of possible lines is sub-divided into the subsets K, R when calculating the number of direct passengers. The following conditions apply: K, R ∈ M and K ⋂ R =∅. Set K contains the lines with high traffic volume, while lines with low traffic volume are all in set R. This sub-division reduces the complexity to such an extent that it is possible to calculate all permutations within the subsets.
To calculate the lines in set K, the traffic flows are analyzed on the basis of the shortest possible paths. The routes from each node to each other node are split up into line sections. Depending on the overall evaluation, these line sections are recombined. This construction is used to simulate traffic flows on the combined set of lines. Following sorting and elimination of parallelities, “n” lines are classed as set K. “n” is dependent on the size of the network. After all connections between lines in set K have been worked out, the lines are connected in such a way that the proportion of direct passengers is maximized.
Uwe Pape, Yean-Suk Reinecke, Erwin Reinecke

On Fair Zone Designs in Public Transportation

In this paper we develop some tools for designing balanced zones in public transportation networks. A zone in such a network is a set of stations which are treated as a unit as far as the fares for the passengers are concerned: The zone tariff is only dependent on the starting and ending zones of their travel. A fair zoning is one where the zone tariff is as close as possible to the distance tariff which relates the fare to the actual distance of a customer trip. In particular, the goal of a fair zone design is that neither the public transportation company nor the customer will have major disadvantages in the transition from distance tariff to zone tariff.
We will consider three objective functions which model this goal. If the zones are fixed we will show how to choose the tariffs in order to minimize the respective objective functions. This result will be combined with Greedy heuristics to design simultaneously zones and the corresponding tariffs. The paper is concluded by an application of our methods to the data of a regional public transportation company in Germany and a summary of further research in this area.
Horst W. Hamacher, Anita Schöbel

Transfer Optimization in Public Transport

In the paper the static and dynamic transfer optimization problems are formulated and solved for various objective functions. In the static case these functions are related to different moments of the transfer waiting time (i.e. mean value, second order moment, variance and probability of not exceeding some fixed treshold waiting time value). The analytical solutions with Shifted Truncated Exponential randomness representation of the vehicles travel times, are presented and compared on an illustrative example for two cases: no holding and punctuality holding control realized at transfer point This is followed by the formulation and solution of the problem of synchronizing different lines which partly use common route segments. In the dynamical case a measure of off-schedule deviations is used as the objective function and optimal transfer synchronization problem is numerically illustrated by real example. Finally, practically important conclusions and implementation possibilities are suggested.
Andrzej Adamski

Practical Experiences in Schedule Synchronization

In complex networks schedule synchronization has a major importance when constructing timetables. Restrictions in this field are based on the structure and the complexity of the existing network, different headways, and the origin-destination pairs of the demand structure. With respect to service quality one main objective coming to mind consists of minimizing the sum of all waiting times of all passengers at transfer nodes in a transit system. Furthermore, modifications of such an objective function incorporating the maximum waiting time may have to be observed as well as interrelationships between service level and operating cost.
Due to the problems’ complexity a number of heuristic solution procedures has been developed for schedule synchronization. In a moderate number of case studies for some public transport networks of German cities we applied a regret heuristic together with some improvement strategies, i.e., simulated annealing and tabu search. Within the latter strategy modifications of a dynamic tabu list management including a look ahead method have been tested. Numerical results are reported and the obtained timetables based on our heuristic approach clearly underline its advantage over previously applied planning tools.
Joachim R. Daduna, Stefan Voß

Transit Route Design Using Scheduling and Multiobjective Programming Techniques

This research provides a new and efficient approach to solve the Transit Route Design (TRD ) problem. This is considered the most complex and cumbersome problem across network route allocation problems. The wide range of the TRD characteristics creates difficulties to formulize the problem uniquely. At the same time, the TRD complexity type creates combinatorial problems, and its formulation cannot be solved via known mathematical programming approaches and packages. The suggested model deals with both its complexity and its practical issues. This is the first time that three transit operational components are being considered simultaneously: route design; timetabling (frequencies); and vehicle scheduling. The approach used has an impact on three components involved: the operator, the user, and the considered authority. The objectives of these three components do not always coincide. From the operator viewpoint, the system should minimize its expenses while, from the user perspective, the system should maximize its level-of-service. This trade-off situation creates this work’s optimization framework. The formulation of this work contains two objective functions — each to be minimized. However, it is impossible to treat both functions simultaneously, and hence, multi-objective programming is being used. This multi-objective programming technique was not used, to our knowledge, for solving the TOD problem. In fact, due to the problem complexity, the ordinary mathematical programming methods cannot be used in this technique, and therefore, a new approach is provided. This new procedure is heuristic in nature and divided into two phases: (a) generation of finite sets of alternative efficient non-inferior solutions, and (b) evaluation and selection of the various solutions using multi-objective preference techniques for discrete variables (“compromise programming” procedure). This approach enables to solve the complex TRD problem. It combines mathematical programming with decision-making methods, using search and enumeration processes while performing the optimization. Thus, it is possible to encounter relatively large-scale problems (networks) with the possibility to interact with the solution method during intermediate steps.
Yechezkel Israeli, Avishai Ceder

Vehicle Scheduling for Public Mass Transit — An Overview

Vehicle scheduling always plays an important role in urban mass transit companies. Efficient schedules of a given timetable have a significant influence on the demand for vehicles and, hence, the demand for personnel. This means that the economic results of a urban mass transit company are closely linked to the planning activities in this area.
The objective of the paper is to show the state of the research in vehicle scheduling and its practical application in urban mass transit companies. First a brief outline of the historical developments is given. Subsequently, different retrictions for the vehicle scheduling problem are structured and explained. Some models and their mathematical formulation are described, whereby the questions of incorporating restrictions is an important issue. A depiction of solution possibilities offered by program systems for computer-aided scheduling in operational use and expierences from urban mass transit companies complete the remarks.
Joachim R. Daduna, José M. Pinto Paixão

Bus Scheduling with Trip Coordination and Complex Constraints

At the stage of compiling bus schedules, schedulers usually can still manoeuvre the trip timings to a certain extent. Sometimes, even options in the route structures might still be open. Most schedulers, especially in the highly competitive U.K. bus industry, would strive to explore many possibilities in order to derive the best schedules in terms of efficiency, competitiveness, quality of service to the public, and operational objectives. This paper reports on recent researches in producing complementary modules to the well-established bus scheduling system BUSPLAN to meet the schedulers / planners’ growing needs. These include interactive and semiautomatic tools for co-ordinating trip timings, and heuristics for handling multivehicle-type constraints.
Earlier work on the co-ordination of trip timings had already been reported in the Fourth Workshop in Hamburg. Recent research has extended this to cover full-day operations rather than just over periods of steady state operations. This encompasses smooth transitions between steady state periods and less regular services at the beginning and end of day. Dead running between terminals also becomes an important consideration.
Since deregulation in 1986, there is a resurgence in multi-vehicle-type constraints in the U.K. bus industry. These constraints are sometimes complicated by the use of more than one depot. VAMPIRES, which was developed in the 1970s and whose algorithm now forms the basis of BUSPLAN, included heuristics for these problems. This paper describes recent improvement updates to these heuristics. Research in improving the VAMPIRES algorithm through object-oriented modelling is also outlined.
Raymond S. K. Kwan, Mohammad A. Rahin

Minimum Cost Vehicle Scheduling with Different Types of Transit Vehicles

This work addresses the problem of how to allocate vehicles efficiently for carrying out all the trips in a given transit timetable, where each vehicle is assigned a chain of trips, some of which may be deadheading (empty) trips. The methodology presented takes into account the association between the characteristics of each trip (urban, peripheral, intercity, etc.), and its required vehicle type. The problem is based on given sets of trips and vehicle types, where the categories are arranged in decreasing order of vehicle cost. Therefore, each trip can be carried out by its vehicle type, or by other types listed in prior order. This problem can be formulized as a cost-flow network problem with an NP-hard complexity level. Thus, a heuristic algorithm is developed in this work, based on the deficit function theory. A simple example is used as an expository device to illustrate the procedures developed.
Avishai Ceder

Vehicle Scheduling Problem with Multiple Type of Vehicles and a Single Depot

This work is concerned with the vehicle scheduling problem with multiple type of vehicles, which consists on the scheduling of a set of trips so as to establish the individual services of vehicles that operate in a certain area. One e it is known both the set of trips to be undertaken and the types of vehicles adequated to each trip, we wish to determine the chains (a sequence of trips) for the vehicles, while minimizing all the operational costs involved. Every vehicle leaving the considered depot must return back to that depot, and there exists a limited number of vehicles of each type. The path assigned to each vehicle can only include trips which can be carried out by that type of vehicle. We present three different folmulations for this problem. For the purpose of obtaining lower bounds on the optimal value of the problem we studied the linear relaxation for two of the formulations and the lagrangean relaxation for the remaining one. We also considered a heuristic technique in order to produce a upper bound on the optimal value of the problem. In the end we present the accomplished computational experience.
Anabela Costa, Isabel Branco, Jose M. Pinto Paixão

Vehicle Scheduling with Time Constraint

We present methods for solving the vehicle scheduling problem with time constraint. Such problem consists of minimizing the costs related to the assignment of vehicles for performing a set of short trips. The vehicles are located at a single depot and one must consider the additional constraint that no vehicle can be away from the depot longer than a maximum time period. For two integer programming models we consider the corresponding Linear Programming and Lagrangean relaxations. The mathematical programming approach as well as a heuristic approach are tested on real-life problems.
Richard Freling, José M. Pinto Paixão

An Exact Algorithm for Combining Vehicle Trips

We consider a vehicle scheduling problem arising in freight transport systems where a vehicle fleet of different classes, split among different depots, must be used to perform a set of trips over a time period horizon minimizing a given cost function. The set of trips must be partitioned in a number of disjoint sequences (called duties) and each duty must be assigned to a vehicle satisfying time window and vehicle-trip objection constraints. Moreover, a vehicle can perform only one duty and must return to the starting depot. This problem is an extension of a simpler problem known as Multiple Depot Vehicle Scheduling Problem (MD-VSP) that is NP hard.
In this paper we formulate the problem as Set Partitioning Problem with side constraints (SPP) where each column is a feasible vehicle duty. We describe a procedure for computing a lower bound to the optimal cost by finding an heuristic solution of the dual of the linear relaxation of the SPP formulation, without generating the entire SPP matrix. The dual solution obtained and an upper bound to the optimal solution cost are used to reduce the number of variables in the SPP in such a way that the resulting SPP can be solved by a branch and bound algorithm. The computational results show that the proposed method can be used to solve large size problems.
Aristides Mingozzi, Lucio Bianco, Salvatore Ricciardelli

Bus Driver Scheduling — An Overview

In this paper, presented at the sixth International Workshop on Computer-Aided Transit Scheduling, the problem of bus driver scheduling is introduced, and some of the constraints and conditions existing in different user environments are presented. The way in which such conditions may affect solution methods is discussed.
The development of driver scheduling by computer through the five previous Workshops is presented, and the range of solution methods as evidenced by published papers is summarised. Particular attention is paid to the work presented at the later workshops, but papers published elsewhere are also introduced, and the authors draw on their own knowledge to augment the published material.
Anthony Wren, Jean-Marc Rousseau

Network Models, Lagrangean Relaxation and Subgradients Bundle Approach in Crew Scheduling Problems

Mathematical models and algorithms embedded in the MTRAM package (Mass Transit Management) are described; MTRAM was installed at several mass transit companies in Italy to solve bus drivers scheduling problems, which consist in the selection of a set of duties covering the company service at the minimum cost. A duty is feasible when union constraints are satisfied; restrictions usually include the duty starting and ending at the same crew domicile. A more general class of crew scheduling problems is also addressed, where a crew domicile is given and daily duties can originate / terminate at places other than the domicile; daily duties are then grouped into pairings which last for a few days and must, in turn, originate and terminate at a single crew domicile and satisfy a variety of restrictions. Crew scheduling problems consist in the selection of a set of feasible pairings covering the service over a certain time horizon at the minimum cost. They arise in different settings such as railways and coach companies running long trips, and especially in airline companies.
Mathematical models developed for MTRAM can be extended to handle the second class of crew scheduling problems and to manage the growth of the model size. Tools developed to improve the efficiency of the approach include: design and implementation of a method for the generation of feasible duties and pairings, which strongly exploits the network structure of the problem; use of a new algorithm of the bundle &trust class to solve the model’s lagrangean dual; development of a theoretical tool allowing duties deletion without affecting the optimal solution.
Numerical results for both classes of problems (bus drivers and airline crew scheduling) are presented and related difficulties are discussed.
Paolo Carraresi, Maddalena Nonato, Leopoldo Girardi

Greedy Genetic Algorithms, Optimizing Mutations and Bus Driver Scheduling

Genetic algorithms have been applied to bus driver scheduling and compared to other approaches such as simulated annealing. Bus driver scheduling is a more difficult domain than most genetic algorithm applications. Special purpose genetic algorithms have been developed that search constrained versions of the initial search space. Greedy algorithms are used for crossovers, though these had to be randomized to give good results. Special purpose optimizing mutation improves search in domains too large for traditional mutation to be useful. The greedy genetic algorithm produces schedules typically within a few duties of the optimum solution. Further theoretical analyses are expected to result in new methods that will improve results. The technology developed may also have applications in other areas of transport scheduling.
Ross Clement, Anthony Wren

Enriching Rules in a Driver Duty Estimator

An estimator has been developed; it first analyses the critical relief opportunities of a bus schedule and then produces an assessment of the number of duties and types of duty required to cover the bus schedule. This paper reports the improvement of the estimator. The estimator has been applied to a variety of scheduling problems from bus companies and produced some very good estimates. Some problems are investigated and new rules formulated during the improvement process are described.
Liping Zhao, Anthony Wren, Raymond S. K. Kwan

Public Transport Workforce Sizing Recognizing the Service Reliability Objective

This paper presents a method for determining the optimal number of public transport operating personnel so as to minimize total operating cost subject to a constraint on the minimum level of service reliability. For a given timetable and crew scheduling solution, the number of operators required to be available is known if all service is to be run and no additional (unscheduled) service is required. However, in light of uncertainties about absence rate and incidence (over the day, the week and the year), and the need for extra service as well as the time involved in hiring and training new operators and restrictions against laying off operators once hired, determination of optimal workforce size is a difficult problem. The method proposed involves developing a relationship between the amount of overtime required (to fill in for any manpower deficit which may occur) and the resulting service reliability. A two-stage method is developed which first estimates the optimal number of operators required in each period (typically four-weeks long), and then defines the annual hiring program and vacation allocation plan to minimize the “errors” from the ideal manpower targets in each period. A case study of the MBTA is used to illustrate application of the proposed method.
Yoram Shiftan, Nigel H. M. Wilson

A New Approach for the Crew Rostering Problem

In this paper an algorithm is presented for determining a lower bound for the Crew Rostering Problem (CRP). The formulation of the CRP presented is basically that of a Set Covering Problem (SCP) with additional constraints. The method proposed to derive a lower bound consists on solving a linear relaxation based on an adaptation of the classic Column Generation approach, since the reduced costs can only be underestimated. The associated sub-problem is shown to be a Shortest Path with Additional Constraints Problem. Furthermore, a very efficient cut for the formulation is presented.
Fernando Catanas, José M. Pinto Paixão

Real-Time Computer Aided Adaptive Control in Public Transport from the Point of View of Schedule Reliability

In the paper a Distributed Computer Adaptive Control and Management System idea is described and motivated. The microcomputer control system called ZPD which creates the control node in this distributed control system, is presented in two practically important applicattions:
In the first as a human operator’s support tool for real-time dispatching control and supervision of the vehicles at various control points (terminals, depots, control centres).
In the second as an on-board vehicle real-time adaptive control unit for distributed autonomous control purposes (i.e. for the autonomous counteraction of the off-schedule deviations, public transport priority control at traffic signalized intersections, transfer synchronization). In this application the control node corresponds to the vehicle equipped with on-board computer.
Andrzej Adamski

Real-Time Dispatching of Public Transit Operations with and without Bus Location Information

This paper presents an approach to rescheduling of bus operations at termini (dispatching) in real time by adjusting layover times, instructing buses to skip stops, and turning short certain trips. The problem is expressed as a non-linear program and as a stochastic binary (0–1) integer program. A number of solution heuristics are proposed and tested using simulation of actual bus operations. In addition, the impact of bus location information on dispatching decision quality is assessed.
Yihua Li, Jean-Marc Rousseau, Michel Gendreau

Integrated Data Processing for Public Transport in Hamburg

The experts agree: Information processing must be integrated, ‘isolated solutions’ belong to the past The development in Hamburg will be shown. The presentation begins with a survey of the integration of data processing as attained today in the HHA concern with approx. 1, 500 end users. There follows a detailed discussion of the systems in the operations departments which are typical of transport companies. This will include technical and operational systems such as automatic vehicle monitoring, analysis and review system and passenger connection synchronization, and also a revenue allocation system in connection with the Hamburg transport association.
Peter Petzold, Peter Schütze

Train Scheduling — Migration of Manual Methods to Scalable Computer Platforms

This paper will describe the evolution of train scheduling in London Underground over the past thirty years and will show how developments in signalling contributed to the initial implementation of a validated timetable datafile. Establishment of the first system concepts enabled further development to produce a completely computerised environment to facilitate planning and scheduling of trains together with the ability to cater for diverse production requirements. This includes provision of control documentation, statistics and signal data. The early implementation of such a system ensured that, when the new generation of centralised control systems began to be installed, data files and subsequently a common database were already available to facilitate provision of planned data in a controlled fashion.
Today, there is a focus on quality of service and a need to be able to assess planned against actual performance. Existence of the schedule system ensured that automation of data capture and the potential for ‘real time’ assessment was feasible, thus enabling the Company to embark upon development of more sophisticated management information and control systems. Further developments will enable the consideration of providing ‘real time’ service planning systems to improve even further the quality of service provided.
Richard Wallace

Recent Developments of HOT II

To assure the economic employment of company ressources (vehicles and staff) for public transport, the scheduler at the Hamburger Hochbahn AG (HHA) was supported by the optimizing planning tool HOT since the seventies. At the middle of the eighties the redevelopment of HOT led to the integrated solution HOT II. The objectives of the recent developments were the extension of the data base, the improvement of the optimisations and the revision of the user interface. Since 1990 the functional requirements were influenced more and more by the increasing number of users outside of Hamburg.
Manfred Völker, Peter Schütze

Results Obtained with Crew-Opt: A Column Generation Method for Transit Crew Scheduling

Crew-Opt is a set-covering method that uses column-generation to produce nearly optimal solutions to crew scheduling problems. We presented this method at the previous workshops. Since that time, we have been using Crew-Opt in a number of experiments and practical trials for a wide range of situations. We will review the basic principles of this method and report on our work with complex public transit problems.
Further development carried out at the University of Montréal (GERAD), together with the rapid increase in computer CPU speed, opens up the possibility of solving large crew scheduling problems optimally with this approach.
Jean-Marc Rousseau, Jaques Desrosiers

Modelling the Scheduling of Itain Drivers

The application of a bus driver scheduling system using linear programming with heuristics, to the problem of scheduling train drivers in the United Kingdom is described. The speed with which the existing proven system could be amended to model this new situation was of the utmost importance. It was required to produce a model which would allow the user to explore the consequences of implementing possible changes to an existing set of rules for constructing train driver schedules and to determine quickly whether the proposed changes would produce desirable schedules.
The prototype was developed on a set of data relating to one depot, and in the first instance the existing constraints were modelled. The data set was then extended to include more depots. Testing on another set of data which exhibited different features to the original, enabled the model to be more thoroughly checked, and allowed the user the opportunity to become familiar with using it Methods were developed which enabled new styles of constraints to be modelled, and the system had to maintain a degree of flexibility to cater for rules which only became necessary as work and testing progressed.
The problems which were encountered in modifying the existing system to embrace the practices of railway operation are outlined. Because of the time constraints placed upon the exercise both the model and the data input were the subject of some simplifying assumptions. However, the ease of use of the model by the user and the degree to which the model was successfully used, demonstrated the viability of the project.
Margaret E. Parker, Anthony Wren, Raymond S. K. Kwan


Weitere Informationen