Investigating Optimal Bus Routes. Planning and Operation in Urban Areas

Table of Contents

CHAPTER (1) INTRODUCTION

1.1. Problem Statement:

1.2. Transit Planning and Operation

1.3. Transit Network Design Problem (TNDP):

1.3.1. TNDP Complexity:

1.3.2. TNDP Solution Methodology Approaches:

1.3.3. Transit Network basic concepts

a. Demand coverage classification

b. Route network directness

c. Transit route length

d. Maximum link flow

e. Service Frequency

f. Bus route capacity

g. Transfer penalty

h. User cost

i. Operator cost

1.3.4. TNDP objectives

1.4. Research Motivation and Objectives:

1.5. Thesis organization

CHAPTER (2) BACKGROUND OF TRANSIT NETWORK DESIGN PROBLEM

2.1. Introduction:

2.2. Literature Review:

2.2.1. Lampkin and Saalmans, 1967

2.2.2. Silman and et al. 1974

2.2.3. Dubois and et al. 1979

2.2.4. Mandl, 1980

2.2.5. Ceder and Wilson 1986

2.2.6. Baaj and Mahmassani’s 1990, 1991, and 1995

2.2.7. Shin and Mahmassani’s 1994

2.2.8. Pattnnik et al. 1998

2.2.9. Gao and et al. 2004

2.2.10. Guan and et al. 2006

2.2.11. Cipriani and et al. 2012

2.2.12. Yu and Yang 2012

2.2.13. Summary of TNDP Literature Review

2.3. TNDP Solution Methodologies Categorization

2.3.1. Mathematical Optimization

2.3.2. Heuristics

2.3.3. Meta – Heuristics

2.4. Review of a pioneer work

2.4.1. Hybrid Route Generation Algorithm (HRGA)

2.4.2. Network Analysis Procedure (NETAP)

2.5. Draw-backs and Short Comings of previous works

CHAPTER (3) TRANSIT NETWORK DESIGN PROBLEM SOLUTION METHODOLOGY APPROACH

3.1. Introduction

3.2. Street Network representation

3.3. Transit Origin/Destination (O/D) matrix

3.4. Transit route Network Design (TrNDP)

3.5. Frequency setting

3.6. Transit Network

3.6.1. Connectivity of Transit Network

3.6.2. Transit Network structures

3.7. Transit Network Evaluation

3.7.1. Transit Network total demand coverage

3.7.2. Transit Network Standards

3.7.3. Transit Network System efficiency measures and cost structure

CHAPTER (4) DETERMINISTIC SOLUTION METHODOLOGY FOR TRANSIT ROUTE DESIGN PROBLEM

4.1. Introduction:

4.2. Route design techniques

4.2.1. Shortest path Algorithms

4.2.2. K shortest path algorithms

4.2.3. Heuristics route design techniques

4.2.4. Evolutionary route design techniques

4.2.5. Neighbor search route design techniques

4.2.6. Ant colony systems

4.2.7. Exact techniques (Travel Salesman Problem)

a. TSP formulation:

b. TSP complexity:

c. Subtours elimination:

4.3. TrNDP Solution Methodology

4.3.1. Required Input Data

4.3.2. Approximate Transit (O/D) assignment

4.3.3. Optimization of transit network links direction:

4.3.4. Route Design Procedure

4.3.5. Solution algorithms

a. Linear programming (LP) algorithm

b. Integer Programming (IP) Algorithm

4.3.6. Illustrative numerical example

4.4. The Structure of Deterministic Route Design Algorithm

4.5. TrNDP Solution Methodology Main Features

CHAPTER (5) OPTIMAL FREQUENCY SETTING FOR BUS ROUTES

5.1. Introduction:

5.2. Passenger Assignment Problem

5.2.1. -0- Transfer Demand analysis

5.2.2. -1- Transfer Demand analysis

5.2.3. -2- Transfer Demand analysis

5.2.4. General Mathematical Optimization Model for Passenger Assignment Problem

5.2.5. Assignment model simplification

5.2.6. Solution Search Tool

5.3. Genetic algorithm (GA)

5.3.1. Population

5.3.2. Coding

5.3.3. Fitness function

5.3.4. Operators

a. Reproduction (selection)

b. Recombination (cross over)

c. Mutation

5.3.5. Convergence

5.3.6. GA flow chart

CHAPTER (6) COMPUTATIONAL CASE STUDY

6.1. Introduction

6.2. Mandl’s Benchmark transit Network

6.3. Solution procedure for Mandl’s transit network

6.4. Results and Discussions

CHAPTER (7) CONCLUSION

7.1. Summary of research

7.2. Key findings

7.3. Further research

Research Objectives and Core Themes

The primary aim of this research is to develop a novel, deterministic solution methodology for the Transit Network Design Problem (TNDP) that addresses the shortcomings of traditional heuristic approaches. The study focuses on partitioning the design process into two sequential, manageable stages: the Transit route Network Design Problem (TrNDP) for planning and an optimal frequency setting for operational efficiency, thereby minimizing both user travel time and operator costs.

• Deterministic modeling for transit network route construction.
• Sequential optimization of route design and bus frequency setting.
• Maximization of direct demand coverage and transit network directness.
• Minimization of passenger travel time and total operator costs using Genetic Algorithms.
• Validation of the methodology through benchmark testing against established transit network problems (e.g., Mandl's network).

Excerpt from the Book

Chapter Summaries

CHAPTER (1) INTRODUCTION: Summarizes the background, problem statement, and objectives of the TNDP, establishing the research motivation and organizational structure.

CHAPTER (2) BACKGROUND OF TRANSIT NETWORK DESIGN PROBLEM: Provides a comprehensive literature review of previous approaches to the TNDP, categorized by their methodologies, and identifies specific gaps and shortcomings.

CHAPTER (3) TRANSIT NETWORK DESIGN PROBLEM SOLUTION METHODOLOGY APPROACH: Details the proposed two-stage methodology, covering network representation, evaluation standards, and the core philosophy behind the research approach.

CHAPTER (4) DETERMINISTIC SOLUTION METHODOLOGY FOR TRANSIT ROUTE DESIGN PROBLEM: Describes the specific deterministic algorithms developed for constructing efficient bus routes using linear and integer programming.

CHAPTER (5) OPTIMAL FREQUENCY SETTING FOR BUS ROUTES: Focuses on the operational side of transit planning, developing an explicit mathematical model for passenger assignment and frequency optimization using Genetic Algorithms.

CHAPTER (6) COMPUTATIONAL CASE STUDY: Applies the developed methodology to the Mandl benchmark network, comparing results with historical data to validate the effectiveness of the proposed approach.

CHAPTER (7) CONCLUSION: Reviews the research findings and suggests directions for future work in transit network optimization.

Keywords

Transit Network Design Problem, TNDP, TrNDP, Route Construction, Frequency Setting, Genetic Algorithm, Optimization, Passenger Assignment, Demand Coverage, Network Directness, Urban Transportation, Computational Efficiency, Integer Programming, Transportation Planning, Transit Operations.

Frequently Asked Questions

What is the primary focus of this thesis?

The thesis focuses on investigating and developing a robust methodology for the planning and operation of optimal bus routes in urban areas, specifically targeting the Transit Network Design Problem (TNDP).

What are the central themes discussed in this work?

The core themes include transit route network design (TrNDP), frequency setting for bus services, passenger assignment behavior, and the optimization of transit networks to reduce operator costs and improve user service levels.

What is the primary research objective?

The main objective is to develop a novel, deterministic solution methodology for the TNDP that uses linear and integer programming to overcome the limitations of traditional, computationally expensive heuristic approaches.

What scientific methods are utilized in this research?

The research employs deterministic mathematical programming (specifically linear and integer programming) for route construction and uses Genetic Algorithms (GA) to solve the complex, non-linear problems associated with optimal bus frequency setting.

What is covered in the main section of the document?

The main section details the two-stage solution approach: the TrNDP stage (planning) and the frequency setting stage (operational), supported by extensive mathematical formulations and benchmark case studies.

Which keywords characterize this work?

Key terms include Transit Network Design Problem (TNDP), Genetic Algorithms, Optimal Frequency Setting, Passenger Assignment, Route Network Design, and computational optimization.

What makes this methodology unique compared to previous studies?

Unlike previous methods that rely heavily on heuristic guidelines, this approach uses deterministic modeling, which ensures consistent, reproducible results and significantly lower computational effort for large-scale transit networks.

How does the author treat the Passenger Assignment Problem?

The author treats it as a primary operational component, developing an explicit mathematical model that tracks passenger behavior across different routes, ultimately optimizing frequency based on passengers' preferences and route travel times.