Transit route Network Design Problem (TrNDP) is the most important component in Transit planning, in which the overall cost of the public transportation system highly depends on it. The main purpose of this study is to develop a novel solution methodology for the TrNDP, which goes beyond pervious traditional sophisticated approaches. The novelty of the solution methodology, adopted in this studyr, stands on the deterministic operators which are tackled to construct bus routes. The deterministic manner of the TrNDP solution relies on using linear and integer mathematical formulations that can be solved exactly with their standard solvers. The solution methodology has been tested through Mandl’s benchmark network problem. The test results showed that the methodology developed in this research is able to improve the given network solution in terms of number of constructed routes, direct transit service coverage, transfer directness and solution reliability. Although the set of routes resulted from the methodology would stand alone as a final efficient solution for TrNDP, it could be used as an initial solution for meta-heuristic procedures to approach global optimal. Based on the presented methodology, a more robust network optimization tool would be produced for public transportation planning purposes.
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
1.3.1. TNDP Complexity:
TNDP is sorted as one of the most difficult problems to be solved in the field of transportation or in the field of Operation Research (OR) in general. This backs to its high degree of complexity. There are five main sources of complexity that often preclude finding a unique optimal solution for TNDP [10, 15-17];
1. Problem formulation: Formulation complexity results from the difficulty of defining the decision variables and thereby expressing the components of the objective functions.
2. Non-linearity and non-convexity: Most TNDP formulations exhibit non-linear decision variables and constraints. Convexity refers to solution search space domain. For any two points in the domain, if all points in the straight line segments that joints these two points are inside the domain, it is called convex problem. Non-convexity would be illustrated by the fact that a transit designer can deploy more buses in transit network (thereby increasing operator’s costs) and still obtain a higher total travel time (worse users’ costs).
3. Combinatorial complexity: This arises from the discrete nature of TNDP. Discrete variables are always involved in route network design problem. Combinatorial optimization problem is a special case of integer problems. It refers to an integer problem where the unordered integer vector’s component set (i.e. if N {n1, n2, n3,….. nn} is the search set) and solution is ordered subsets from this search set. This make the complexity of the problem grows exponentially with the size of transit network.
4. NP-hard: TNDP optimization is classified NP-hard, which refers to the problem for which the number of elementary numerical operations is not likely to be expressed by function of polynomial form. NP-hard intractability is due to the need to search optimal solutions from a large search space made by all possible solutions.
5. Multi objective Nature of TNDP: Many past approaches have recognized reducing users’ costs or operator’s costs as their sole objective. In practice, users and operators costs are conflicting objectives.
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.
- Arbeit zitieren
- Mahmoud Owais (Autor:in), 2015, Investigating Optimal Bus Routes. Planning and Operation in Urban Areas, München, GRIN Verlag, https://www.grin.com/document/293714
