Computer-aided Systems in Public Transport

This article proposes a Lagrangean relaxation approach to solve integrated duty and vehicle scheduling problems arising in public transport. The approach is based on a version of the proximal bundle method for the solution of concave decomposable functions that is adapted for the approximate evaluation of the vehicle and duty scheduling components. The primal and dual information generated by this bundle method is used to guide a branch-and-bound type algorithm.

Computational results for large-scale real-world integrated vehicle and duty scheduling problems with up to 1,500 timetabled trips are reported. Compared with the results of a classical sequential approach and with reference solutions, integrated scheduling offers remarkable potentials in savings and drivers’ satisfaction.

This paper presents a new approach for solving the crew scheduling problem in public transit. The approach is based on interaction with the corresponding vehicle scheduling problem. We use a model of the vehicle scheduling problem which is based on a time-space network formulation. An advantage of this procedure is that it produces a bundle of optimal vehicle schedules, implicitly given by the solution flow. In our approach, we give this degree of freedom to the crew scheduling phase, where a vehicle schedule is selected that is most consistent with the objectives of crew scheduling.

In this paper we discuss several methods to solve large real-world instances of the vehicle and crew scheduling problem. Although there has been an increased attention to integrated approaches for solving such problems in the literature, currently only small or medium-sized instances can be solved by such approaches. Therefore, large instances should be split into several smaller ones, which can be solved by an integrated approach, or the sequential approach, i.e., first vehicle scheduling and afterwards crew scheduling, is applied.

In this paper we compare both approaches, where we consider different ways of splitting an instance varying from very simple rules to more sophisticated ones. Those ways are extensively tested by computational experiments on real-world data provided by the largest Dutch bus company.

The vehicle scheduling problem, arising in public transport bus companies, addresses the task of assigning buses to cover a given set of timetabled trips. It considers additional requirements, such as multiple depots for vehicles and vehicle type groups for timetabled trips as well as depot capacities. An optimal schedule is characterized by minimal fleet size and minimal operational costs including costs for unloaded trips and idle time spent outside the depot. This paper discusses the multi-depot, multi-vehicle-type bus scheduling problem for timetabled trips organized in bus lines. We use time-space-based networks for problem modeling. The cost-optimal vehicle schedule may involve several line changes for a given bus within a working day which might not be desirable from the practical point of view. Some bus companies prefer to pose a restriction for bus line changes as well. Because the network flow based model works with trips and not lines, it does not explicitly take into account line changes. In this contribution, we discuss several methods to find schedules with an acceptable number of line changes.

In this paper we report on the results of a research project on train traffic control systems, supported by the European Commission. The results of the project include the development of new optimisation models and algorithms for traffic management, and a general architecture for train traffic control, capable of managing both fixed block and moving block signaling safety concepts. This paper focuses in particular on models and algorithms for real time conflict resolution. Computational results are reported, based on a portion of the Dutch railway network, on the high-speed line Paris-Brussels-Amsterdam.

Airline crew scheduling is a comparably well-studied field in operations research. An increasing demand for higher crew satisfaction arises; especially after most relevant cost factors have been optimized to their greatest extent, mostly with secondary or little regard on quality-of-life criteria for the involved crew members. One such criterion is team orientation. Independent from the chosen assignment strategy (bidline systems, personalized rostering or preferential bidding), current approaches do not consider frequently occurring changes within daily or day-by-day team compositions. By this, crew members rarely know with whom they work for the next flight(s) and/or day(s), respectively. In case of overnight stays outside their individual home base, crew members easily experience themselves having to find their ways to the booked hotels on their own. The avoidance of both aspects is highly appreciated by the crew as well as by the airlines, and will be addressed in the Team-oriented Rostering Problem. In this work we present a first interpretation of Team-oriented Rostering for cockpit crew, namely captains and first officers which can be implemented via two dedicated optimization models: Extended Rostering Model and Roster Combination Model. Due to the high combinatorial complexity, certain strategies are applied during roster generation and roster combination in order to solve mid-sized instances based on a European tourist airline setting. As a result, the implied trade-off curve between operational cost and the number of team changes will be discussed.

In the planning process of railway companies, we propose to integrate important decisions of network planning, line planning, and vehicle scheduling into the task of periodic timetabling. From such an integration, we expect to achieve an additional potential for optimization.

Models for periodic timetabling are commonly based on the Periodic Event Scheduling Problem (PESP). We show that, for our purpose of this integration, the PESP has to be extended by only two features, namely a linear objective function and a symmetry requirement. These extensions of the PESP do not really impose new types of constraints. Indeed, practitioners have already required them even when only planning timetables autonomously without interaction with other planning steps. Even more important, we only suggest extensions that can be formulated by mixed integer linear programs.

Moreover, in a self-contained presentation we summarize the traditional PESP modeling capabilities for railway timetabling. For the first time, also special practical requirements are considered that we prove not being expressible in terms of the PESP.

During the last 15 years, many solution methods for the important task of constructing periodic timetables for public transportation companies have been proposed. We first point out the importance of an objective function, where we observe that in particular a linear objective function turns out to be a good compromise between essential practical requirements and computational tractability. Then, we enter into a detailed empirical analysis of various Mixed Integer Programming (MIP) procedures — those using node variables and those using arc variables — genetic algorithms, simulated annealing and constraint programming. To our knowledge, this is the first comparison of five conceptually different solution approaches for periodic timetable optimization.

On rather small instances, an arc-based MIP formulation behaves best, when refined by additional valid inequalities. On bigger instances, the solutions obtained by a genetic algorithm are competitive to the solutions CPLEX was investigating until it reached a time or memory limit. For Deutsche Bahn AG, the genetic algorithm was most convincing on their various data sets, and it will become the first automated timetable optimization software in use.

This study formulates a mixed-fleet ferry routing and scheduling model while considering passengers’ choices for differential services. Ferry services with different operation characteristics and passengers with different preferred arrival time-windows are considered in the model. The logit model is applied to determine passengers’ service choices. The formulation then determines the best mixed-fleet operating strategy, including interlining schemes, so as to minimize the objective function that combines both the operator and passengers’ performance measures. Mathematically, this mixed-fleet routing and scheduling problem is formulated as a mixed integer nonlinear program. This study then develops an iterative heuristic algorithm to solve this problem. The results show that the algorithm could improve the operations of the system given different initial points. Nevertheless, finding the global optimal solution could be difficult due to the inherent non-convex nature of the problem.

Planning train movements is difficult and time-consuming, particularly on long-haul rail networks, where many track segments are used by trains moving in opposite directions. A detailed train plan must specify the sequence of track segments to be used by each train, and when each track segment will be occupied. A good train plan will move trains through the network in a way that minimises the total cost associated with late arrivals at key intermediate and final destinations.

Traditionally, train plans are generated manually by drawing trains on a train graph. High priority trains are usually placed first, then the lower priority trains threaded around them. It can take many weeks to develop a train plan; the process usually stops as soon as a feasible train plan has been found, and the resulting plan can be far from optimal.

Researchers at the University of South Australia and WorleyParsons Rail have developed scheduling software that can generate optimised train plans automatically. The system takes a description of the way trains move through the network and a list of trains that are required to run, and quickly generates a train plan that is optimised against key performance indicators such as delays or lateness costs.

To find a good plan, we use a probabilistic search technique called Problem Space Search. A fast dispatch heuristic is used to move the trains through the network and generate a single train plan. By randomly perturbing the data used to make dispatch decisions, the Problem Space Search method quickly generates hundreds of different train plans, then selects the best. The automatic scheduling system can be used to support applications including general train planning, real-time dynamic rescheduling, integrated train, crew and maintenance planning, infrastructure planning and congestion studies.

One of the first applications of the system has been for an Australian mineral railway, to prepare efficient train plans to match mineral haulage requirements. The product is mined at six sites and transported by rail to a port. The numbers and sizes of train loads from each site are determined by grading requirements to meet the product specification for shipping. The train plan is then the orderly translation of these transportation requirements into an efficient timetable which resolves meets and crosses over a long single track railway. These train movements are thus part of an integrated mine-to-ship logistics chain.

The Commonwealth of Pennsylvania has the nation’s largest rural population and the Commonwealth plays an important role in providing transportation for students to travel to their respective schools. State and local governments reimburse school districts for student transportation costs in Pennsylvania. Effective policies for governing the transportation of students can result in large cost savings for the respective governments and reduced travel time for the students. This paper presents heuristics to solve a complex rural school bus routing problem using digitized road networks that can lead to cost savings for both State and local governments. The school bus routing problem addressed and solved in this paper is a mixed-fleet, multi-depot, site-dependent, split-delivery problem with side constraints. Computation of real road distances for the rural school district between pickup points, depots and schools, consisting of 4200 road segments, was done using digitized road networks obtained from the U. S. Census Bureau. Heuristic algorithms were designed and implemented to solve a school bus routing problem with real life data obtained from a rural school district. Feasible solutions to the complex rural school bus routing problem, consisting of 13 depots, 5 schools, 71 pickup points and 583 students, were obtained in less than 10 minutes of CPU time.

London Heathrow airport is one of the busiest airports in the world. Moreover, it is unusual among the world’s leading airports in that it only has two runways. At many airports the runway throughput is the bottleneck to the departure process and, as such, it is vital to schedule departures effectively and efficiently. For reasons of safety, separations need to be enforced between departing aircraft. The minimum separation between any pair of departing aircraft is determined not only by those aircraft but also by the flight paths and speeds of aircraft that have previously departed. Departures from London Heathrow are subject to physical constraints that are not usually addressed in departure runway scheduling models. There are many constraints which impact upon the orders of aircraft that are possible and we will show how these constraints either have already been included in the model we present or can be included in the future. The runway controllers are responsible for the sequencing of the aircraft for the departure runway. This is currently carried out manually. In this paper we propose a metaheuristic-based solution for determining good sequences of aircraft in order to aid the runway controller in this difficult and demanding task. Finally some results are given to show the effectiveness of this system and we evaluate those results against manually produced real world schedules.

Historically, schedulers and operations management personnel have made decisions with limited information about various states of the transit system. The present study highlights innovative uses of data collected via automatic vehicle location and automatic passenger count technologies in the areas of scheduling and operations management at TriMet, the transit provider for the Portland, Oregon metropolitan region. Two main topics are addressed in this paper. First, we look at efforts at TriMet involving the use of archived operations data to improve bus schedules. Second, we look at the role of operator behavior in relation to service reliability and steps the agency is taking to reduce run time variability and maintain vehicle headways through better management of operators. The quality, quantity, and disaggregate nature of data at TriMet has greatly enhanced the agency’s ability to generate performance reports as well as undertake special purpose studies targeting specific operational issues, providing essential feedback into the scheduling process.

When a bus on a scheduled trip breaks down, one or more buses need to be rescheduled to serve the customers on that trip with minimum operating and delay costs. The problem of reassigning buses in real-time to this cut trip, as well as to other scheduled trips with given starting and ending times, is referred to as the bus rescheduling problem (BRP). This paper considers modeling, algorithmic, and computational aspects of the single-depot BRP. The paper develops the sequential and parallel auction algorithm to solve the BRP. Computational results show that our approach solves the problem quickly.

Bus route running time represents a key element of transit performance. An understanding of running time behavior and the factors that influence it is essential for off-line planning and operations design purposes including fleet size planning, schedule design, and passenger travel time performance assessment. Such an understanding is also critical for realtime applications including bus operations control and passenger information systems. This paper focuses on developing models of running time and estimating them using field data. Two model structures are considered. The schedule-based model specifies the upcoming running time as a function of the most recent deviation from the schedule the bus has exhibited at the terminus. This model characterizes the situation where a late running bus attempts to catch up with the schedule and, hence, reflects an upcoming running time shorter than the target running time, and vice versa. The autoregressive model specifies the upcoming running time as a function of the most recent running time. This model characterizes one of two situations depending on the sign of the parameter estimate. On the one hand, when the most recent running time is longer than the mean, the upcoming running time would also be longer than the mean if the operation is dominated by exogenous factors that cause delays such as other traffic or weather. On the other hand, the upcoming running time would be shorter than the mean if the driver is capable of speeding up to reduce the delay in the operation. Irrespective of the model structure, the characteristics of the driver-bus pair may also influence the extent to which the upcoming running time will deviate from the target or the mean. To capture this potential heterogeneous phenomenon, the fixed effects formulation is adopted whereby driverbus pair dummy variables are included in the model. Field data are utilized in estimating the two types of models in the presence of driver-bus heterogeneity. In general, the schedule-based model is superior to the autoregressive model in describing running time behavior. Moreover, driver-bus heterogeneity is found to be a significant contributor to this behavior.

Urban rail transit lines are subject to disruptions that can adversely affect passenger level of service and routine operations. This paper focuses upon the development of a real-time disruption response model with an emphasis on the train holding strategy. The paper also discusses the short-turning control strategy which is often used in conjunction with holding for longer disruptions. The holding problem is modeled as a non-linear mixed-integer program and a two-step solution procedure is designed to solve it quickly, yielding solution times of less than 10 seconds. The model is applied to a disruption scenario on a simplified representation of the MBTA Red Line. The sensitivity of the optimal holding strategy to the assumptions of finite train capacity and the value of in-vehicle time are also investigated. The results show a high level of regularity in the headway distribution for the control strategy when in-vehicle time is not considered. When accounting for in-vehicle delay, the optimal holding strategy consists of only a few trains being held at a few stations. Overall, the results suggest the present formulation yields control strategies that are simple enough to be implemented by transit practitioners and that the solution times are feasible for real-time implementation.

Inherent stochasticity within the transit operating environment suggests there may be benefits of holding vehicles at more than one holding station on a route. In this paper, the holding problem at multiple holding stations considers holding vehicles at a given subset of stations on the route. By approximating the vehicle dwell time as the passenger boarding time, the holding problem at multiple holding stations can be modeled as a convex quadratic programming problem, with the objective function as a convex quadratic function subject to many linear constraints. This particular problem can be solved by a heuristic that decomposes the overall problem into sub-problems which can be solved to optimality. Also, a hypothetical numerical example is presented to illustrate the effectiveness of the problem formulation and heuristic.

This work describes a highly informative graphical technique for the problem of finding the lower bound of the number of vehicles required to service a given timetable of trips. The technique is based on a step function that has been applied over the last 20 years as an optimization tool for minimizing the number of vehicles in a fixed-trip schedule. The step function is called a Deficit Function (DF), as it represents the deficit number of vehicles required at a particular terminal in a multi-terminal transit system. The initial lower bound on the fleet size with deadheading (empty) trip insertions was found to be the maximum of the sum of all DFs. An improved lower bound was established later, based on extending each trip’s arrival time to the time of the first feasible departure time of a trip to which it may be linked or to the end of the finite time horizon. The present work continues the effort to improve the lower bound by introducing a simple procedure to achieve this improvement that uses additional extension possibilities for a certain trip’s arrival times.

Systematic tabu search based meta-heuristic algorithms are designed and implemented for the transit route network design problem. A multi-objective nonlinear mixed integer model is formulated. Solution methodologies based on three variations of tabu search methods are proposed and tested using a small experimental network as a pilot study. Sensitivity analysis is performed, a comprehensive characteristics analysis is conducted and numerical results indicate that the preferred tabu search method outperforms the genetic algorithm used as a benchmark.

For transit services operated by competitive private companies, as in Hong Kong, the objectives of the companies are not to minimize the total traveler and/or infrastructure costs, but to optimize their profits. Other than engaging in a Bertrand Game, companies may also compete via their service frequencies. As evident in Hong Kong, the intense competition has led to a very visible phenomenon - companies putting more and more buses on major (profitable) corridors, leading to significant increases in congestion. This study aims to analyze externality pricing through bus tolling to manage the congestion caused by them. The result shows that bus tolling can be a promising tool.

A Mobility Allowance Shuttle Transit (MAST) system is an innovative concept that merges the flexibility of Demand Responsive Transit (DRT) systems with the low cost operability of fixed-route bus systems. It allows vehicles to deviate from the fixed path so that customers within the service area may be picked up or dropped off at their desired locations. In this paper, we summarize the insertion heuristic presented by Quadrifoglio et al. (2007) for routing and scheduling MAST services, and we carry out a set of simulations to show a sensitivity analysis of the performance of the algorithm and the capacity of the system over different shapes of the service area. The results show that a slim service area performs better in general, but also that the positive effects of a proper setting of the control parameters of the heuristic is much more evident for wider service areas. In addition, a performance comparison shows that MAST systems can provide a better service to customers than fixed-route ones even for a slim service area.