Synchronization of Public-Transport Timetabling with Multiple Vehicle Types 

Get Complete Project Material File(s) Now! »

Chapter 3. User and Operator Perspectives in Public Transport Timetable Synchronization Design

Transportation Research Record: Journal of the Transportation Research Board, 2667, DOI:10.3141/2667-15.(Liu and Ceder, 2017b)


Increased traffic congestion and the adverse environmental impact of private cars, has resulted in an increasingly pressing need for an integrated public transport (PT) system that is more attractive than private car use. The intelligent PT timetable synchronization design is one way to improve the integration and service quality of a PT system with increased connectivity, synchronization, and attractiveness towards far more user-oriented, system-optimal, smart and sustainable travel. This work proposes a new multi-criteria optimization modelling framework using a systems approach for the PT timetable synchronization design problem. A new bi-objective model that takes account of both PT users’ and operators’ interests is proposed. The nature of the overall mathematical formulations of the new model is bi-objective nonlinear integer programming with linear constraints. Based on the characteristics of the model, a novel, deficit function (DF)-based sequential search method is proposed to solve the problem so as to obtain Pareto-efficient solutions. The visual nature of the proposed DF and the two-dimensional fleet-cost space graphical techniques can facilitate the decision-making process of PT schedulers for finding a desired solution. Numerical results from a small PT network demonstrate that the proposed mathematical programming model and solution method are effective in practice and have the potential for being applied in large-scale and realistic networks.


Transfers in public transport (PT) systems, especially those involving buses, are used to create a more efficient network by the reduction of operational costs and the allowance of more flexible route planning. However, transfers are cited as a key reason for PT being less attractive than cars (Ceder et al., 2013; Ceder, 2016). Long transfer waiting time and missed transfer connections have been found to considerably reduce the attractiveness and reliability of PT service. Subsequently, the unreliable and irregular PT service will not only frustrate the existing passengers, but also deter potential new users. It seems relatively intuitive that reducing the transfer cost, from the perspective of PT users, and reducing the operations cost, from the perspective of PT operators, will lead to an increase in PT ridership and competiveness with private cars. This transfer service improvement scheme will ultimately help to shift a significant amount of private car users to PT in a sustainable manner.
Among a variety of PT transfer improvement strategies, timetable synchronization is a useful strategy used by PT schedulers to provide a well-connected smooth transfer service, reduce the inter-route or intermodal passenger transfer waiting time and improve the network-wide level of service. The PT timetable synchronization design (PT-TSD) problem is aimed at creating a timetable for a given network of vehicles so as to maximize their synchronization at transfer stops and reduce the transfer cost of passengers in the whole network (Ceder et al., 2001). PT schedulers take user satisfaction and convenience into account, acknowledging the importance of creating a timetable with maximum synchronization, which enables the transfer of passengers from one route to another with minimum waiting time at transfer nodes.
A major motivation for this study was to address the needs of the Auckland Transport (AT) which is responsible for the planning and operation of Auckland’s PT systems, including bus, ferry and train services. Transfers in the current PT system tend to be criticized for inconvenience and inefficiency for users. Some routes are operated with a very long headway, such as 20, 30, and 60 minutes, which makes transferring between lines inconvenient, involving irregular and often long transfer waiting times for a missed connection. Recently, the Auckland Regional Public Transport Plan was released with the aim of developing an integrated and well-connected PT network which can allow Aucklanders to have seamless and smooth transfers between hierarchical high and low frequency PT routes (Auckland Transport, 2013). AT is now moving to provide a simpler and more integrated PT network for Auckland. By doing so, transferring between routes will be supported by improved timetables, better vehicle capacity, good interchange facilities and simplified zone fares which will be implemented in 2016 (Auckland Transport, 2016). It is anticipated that by 2018, Aucklanders will be able to enjoy more frequent, more connected travel where they just show up at a bus stop, train station or ferry terminal, and go. Accordingly, efficient planning and operation tools are needed to help to develop an integrated multimodal PT system for the future sustainable development of New Zealand’s largest and busiest city.

Literature Review

Several computer-aided systems, mathematical models and algorithms have been developed to design synchronized timetables for PT networks with transfers. The earliest known approach which was actually applied is the graphical optimization technique. Rapp and Gehner (1976) developed a computer-aided, interactive graphic system for transfer optimization in the Basel Transit System. The system adopts a graphical person-computer interactive approach to reduce transfer delay and the number of vehicles required. Another graphical optimization method used in the timed transfer system (TTS) in a Philadelphia suburb was described by Vuchic (2005). This TTS used a clock-type diagram to provide graphical representations of synchronized schedules. Other earlier theoretical investigations of the PT-TSD are mainly focused on how to set route headways and offset times (departure time of the first trip). Salzborn (1980) studied a special inter-town route connected by a string of feeder routes. Some intuitive rules are provided to set the departure and arrival times of buses on the feeder routes. Daganzo (1990) examined the single transfer node case, and provided some intuitive rules for setting the headways of the inbound and outbound routes.
The second approach to solve the PT-TSD problem employs analytical formulations for idealized PT systems. Knoppers and Muller (1995) investigated the impact of fluctuations in passenger arrival times on the possibilities and limitations of synchronized PT transfers. They concluded that transfer synchronization is gainful when the arrival time of the feeder line is within a time window relative in length to the headway of the connecting line. Ting and Schonfeld (2005) provided analytical formulations of cost components in the objective function, including operating cost, waiting cost, transfer cost. They proposed to use integer-ratio headways and slack time to minimize the total costs of operations.
The third approach that was widely used in the literature adopts mathematical programming models. Klemt and Stemme (1988), and Domschke (1989) provided a quadratic programming model of the problem to minimize passenger transfer waiting time. A set of heuristics, such as regret methods, improvement algorithms and simulated annealing, are proposed to solve the model problem. Bookbinder and Desilets (1992) developed an integer programming model and an iterative improvement heuristic procedure was provided to minimize mean transfer disutility. Voß (1992) proposed a 0-1 integer programming and a tabu search algorithm to minimize transfer waiting time. Ceder et al. (2001) developed a mixed integer linear programming model and several heuristic algorithms to maximize the number of simultaneous bus arrivals at the transfer nodes of PT networks. Based on this seminal work, a series of follow-up studies have been conducted by other researchers, such as Shafahi and Khani (2010), Ibarra-Rojas and Rios-Solis (2012), Aksu and Akyol (2014). Wong et al. (2008) developed a mixed integer programming model and an optimization-based heuristic method to minimize the total passenger transfer waiting time for the MTR system in Hong Kong. Ibarra-Rojas et al. (2014) developed a bi-objective, integer programming model to maximize the number of passengers benefited by well-timed transfers and minimize vehicle operating costs.
The objective function of the aforementioned work (except Ting and Schonfeld, 2005; Aksu and Akyol, 2014; Ibarra-Rojas et al., 2014; Ceder, 2016) is either to minimize the total passenger transfer waiting time or maximize the number of direct transfers. One limitation of these works is that they failed to consider other system performance measures. For example, the minimization of passenger transfer waiting time may lead to impaired performance of other system measures, such as increased fleet size, increased travel time and more empty seat-hours. Therefore, a comprehensive, systematic and multi-criteria approach that can take all of the system performance measures into consideration is needed.

Objectives and Contributions

The objective of this work is to provide a new multi-criteria optimization model and solution methods for the PT-TSD problem taking into account both passenger and operator interests. The contribution of this research is threefold. First, we have developed a new bi-objective, integer programming model for the PT-TSD problem considering five system-performance measures, i.e., total passenger in-vehicle travel time, total initial waiting time, total transfer waiting time, empty seat/space-hours, and fleet size. Secondly, we have systematically and mathematically defined these performance measures used in the model. Finally, we developed a novel deficit function-based sequential search method for solving the proposed mathematical model.

Background on the Deficit Function

Following is a concise description of a step function approach proposed by Ceder (2016) and Ceder and Stern (1981) for assigning the minimum number of vehicles to allocate for a given timetable. The step function is called the deficit function (DF), as it represents the deficit number of vehicles required at a particular terminal in a multi-terminal transit system. The DF is a step function that increases by one at the time of each trip departure and decreases by one Chapter 3. User and Operator Perspectives in Public Transport Timetable Synchronization Design at the time of each trip arrival. Linis and Maksim (1967) and Gertsbach and Gurevich (1977) have called this step function a DF as its value represents the deficit number of vehicles required at a particular terminal in question in a multi-terminal PT system. To construct a set of DFs, the only information needed is a timetable of required trips. The DF has its appeal in its graphical nature and visual simplicity.
Let G = {g: g = l, …, n} denote a set of required trips. The trips are conducted between a set of terminals U = {u: u = l, …, q}, each trip to be serviced by a single vehicle, and each vehicle able to service any trip. Each trip g can be represented as a 4-tuple ( p g , t sg , q g , teg ), in which the ordered elements denote departure terminal, departure (start) time, arrival terminal, and arrival (end) time. It is assumed that each trip g lies within a schedule horizon [T1, T2], i.e., T1 £ t sg £ t eg £ T2 . The set of all trips S = {( p g , t sg , q g , t eg ): p g , q g Î U , g ÎG} constitutes the timetable. Two trips g1, g2 may be serviced sequentially (feasibly joined) by the same vehicle if and only if (a) t eg1 £ tsg2 and (b) q g1 = pg2 .
Let d(u, t, S) denote the DF for terminal u at time t for schedule S . The value of d(u, t, S) represents the total number of departures minus the total number of trip arrivals at terminal u, up to and including time t. The maximum value of d(u, t, S) over the schedule horizon [T1, T2], designated D(u, S), depicts the deficit number of vehicles required at u. Note that S will be deleted when it is clear which underlying schedule is being considered.
Theorem 1 (The fleet size theorem). If, for a set of terminals U and a fixed set of required trips G, all trips start and end within the schedule horizon [T1, T2] and no deadheading (DH) insertions are allowed, then the minimum number of vehicles required to service all trips in G is equal to the sum of all the deficits.
Proof. A formal proof of this theorem can be found in Ceder (2016).
The DF theory has been applied to various kinds of PT operations planning activities, including vehicle scheduling, timetable design, network route design, deployment planning of bus rapid transit systems, operational parking space design, and crew scheduling. A detailed summary of the major developments and innovations in the application of the DF theory in PT planning and operations can be found in the recent work of Liu and Ceder (2017a).

Notations and Mathematical Formulations

The mathematical programming formulations presented in this section are mainly inspired from the work of Ceder (2001, 2016) on PT network-route design, the work of Ceder and Stern (1984) on PT timetable design, and the work of Liu and Ceder (2016a) on transit coordination using integer-ratio headways.


Consider a connected network composed of a directed graph G = {N, A} with a finite number of nodes N connected by A arcs. The following notations are used:

Two Principal Objective Functions

 The PT-TSD problem is based on two principal objective functions, minimum Z1 and minimum Z2 , across the different sets of PT routes:
Passenger hours between nodes i and j, i, j Î N (defined as passenger riding time in a PT vehicle on an hourly basis; it measures the time spent by passengers in vehicles between the two nodes);
 Initial waiting time between nodes i and j, i, j Î N (defined as the amount of time passengers spend at the boarding stops between the two nodes);
 Transfer waiting time between nodes i and j, i, j Î N (defined as the amount of time passengers spend at the transfer stops between the two nodes); Passenger load discrepancy cost on route r (defined as the difference between the expected load and the desired occupancy multiplied by the corresponding route segment travel time; passenger load discrepancy cost measures the overcrowding on vehicles);
 =      Fleet size (defined as the number of PT vehicles needed to provide all trips along a chosen set of routes);
=      Monetary or other weights, k=1, 2, 3, 4.
Chapter 3. User and Operator Perspectives in Public Transport Timetable Synchronization Design For given weights of 1 or without units, Equation (3.2) results in units of passenger hours (pass-h). Equation (3.3) is simply the minimum fleet size required.

Objective Function Components

Equations (3.2) and (3.3) essentially combine five objective function components. The first objective component is to minimize total passenger in-vehicle travel hours in the system. This is strictly from the perspective of PT users. The formulation of this objective component takes the following form:
where a1 is the monetary value of 1 hour’s (h’s) in-vehicle travel time. Specifically, its formulation is:
The second objective component is to minimize passengers’ total initial waiting time at boarding stops. This too is strictly from the perspective of the PT users. The following is the formulation of this objective component:
where a2 is the monetary value of 1 h’s initial waiting time. Different formulations of the expected initial waiting time for PT passengers can be found in Marguier and Ceder (1984). Assuming that PT passengers are arriving randomly at the stops and that the vehicle headways are relatively short and distributed in a deterministic manner (with no variation of the where Lr is the average (over days) maximum number of passengers (max load) observed on route r . If Fr = Fmin , then the load profile will have no influence on the frequency determination. Therefore, passengers’ total initial waiting time can be calculated by:
The third objective component is to minimize passengers’ total transfer waiting time at transfer stops. Yet again, this is strictly from the PT users’ perspective. The formulation of this objective component takes the following form:
where a3  is the monetary value of 1 h’s transfer waiting time.

Table of Contents
List of Figures
List of Tables 
Glossary of Acronyms 
Chapter 1. Introduction 
1.1. Background and Research Motivation
1.2. Statement of the Problem
1.3. Research Objectives
1.4. Scope of the Research
1.5. Significance of the Research
1.6. Research Methods
1.7. Structure of the Thesis
Chapter 2. Integrated Public Transport Timetable Synchronization and Vehicle Scheduling: A Bi objective Integer Programming Model using Deficit Function Approach 
2.1. Abstract
2.2. Introduction
2.3. Literature Review
2.4. Background on the Deficit Function
2.5. Model Formulation
2.6. Deficit Function-based Combined Optimization Approach
2.7. Numerical Example
2.8. Discussions
2.9. Concluding Remarks .
Chapter 3. User and Operator Perspectives in Public Transport Timetable Synchronization Design 
3.1. Abstract
3.2. Introduction
3.3. Literature Review
3.4. Objectives and Contributions
3.5. Background on the Deficit Function
3.6. Notations and Mathematical Formulations
3.7. Solution Method
3.8. Numerical Example
3.9. Conclusions
Chapter 4. Synchronization of Public-Transport Timetabling with Multiple Vehicle Types 
4.1. Abstract
4.2. Introduction
4.3. Model Assumptions
4.4. Model Formulations
4.5. Heuristic Algorithm
4.6. Numerical Example
4.7. Case Study
4.8. Conclusions
Chapter 5. Synchronizing Public Transport Transfers by Using Intervehicle Communication Scheme: Case Study 
5.1. Abstract
5.2. Introduction
5.3. Transfer Types
5.4. Methodology
5.5. Model
5.6. Case Study
5.7. Conclusions
Chapter 6. Communication-Based Cooperative Control Strategy for Public-Transport Transfer Synchronization
6.1. Abstract
6.2. Introduction
6.3. Optimization Framework
6.4. Formulation of Control Strategies
6.5. Monte Carlo Method for Network Simulation
6.6. Numerical Example
6.7. Case Study
6.8. Conclusions
Chapter 7. Optimal Synchronized Transfers in Schedule-based Public-Transport Networks Using Online Operational Tactics 
7.1. Abstract
7.2. Introduction
7.3. Optimization Framework
7.4. Methodology
7.5. Examples
7.6. Conclusions
Chapter 8. Analysis of a New Public-Transport-Service Concept: Customized Bus in China 
8.1. Abstract
8.2. Introduction
8.3. CB Development in China
8.4. Demand-Based CB Service Design
8.5. CB Operation-Planning Process
8.6. CB Fare Design and Collection
8.7. Advantages of CB
8.8. Difficulties and Recommendations
8.9. Conclusions
Chapter 9. Commuting by Customized Bus: A Comparative Analysis with Private Car and Conventional Public Transport in Two Cities
9.1. Abstract
9.2. Introduction
9.3. Related Literature Review
9.4. Methodological Framework
9.5. Study Area
9.6. Data Collection
9.7. Data Processing
9.8. Results
9.9. Conclusions
Chapter 10. Conclusions and Future Research 
10.1. Concluding Remarks
10.2. Limitations and Future Research
Transfer Optimization in Public Transport Networks: Timetable Synchronization, Operational Control and a New Service-Design Concept

Related Posts