Investigating Optimal Bus Routes. Planning and Operation in Urban Areas

LIST OF CONTENTS

ACKNOWLEDGMENTS

ABSTRACT

LIST OF FIGURES

LIST OF TABLES

ABBREVIATIONS AND NOTATIONS

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,
2.2.2. Silman and et al
2.2.3. Dubois and et al
2.2.4. Mandl,
2.2.5. Ceder and Wilson
2.2.6. Baaj and Mahmassani’s 1990, 1991, and
2.2.7. Shin and Mahmassani’s
2.2.8. Pattnnik et al
2.2.9. Gao and et al
2.2.10. Guan and et al
2.2.11. Cipriani and et al
2.2.12. Yu and Yang
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

References:

Appendices

ACKNOWLEDGMENTS

All gratitude is due to all mighty ALLAH who guided me to produce this work into light and aided me for the achievement of this Thesis.

I would like to acknowledge and thank Prof. Dr. Mohammed El- Shabrawy at El-Mansoura University; for his efforts, valuable assistance and comments which has helped tremendously in guiding me during his supervision of research.

I would like to express my sincere gratitude and very much appreciation to Prof. Dr. Youssef Aly Abbas at Civil Engineering Department, Faculty of Engineering, Assuit University; for his efforts, valuable assistance and guidance during his supervision of this research work.

I would like to express my deep thanks and grateful appreciation to Dr. Ghada Salah Moussa at Civil Engineering Department, Faculty of Engineering, Assuit University; for her guidance and valuable suggestions during carrying out this research.

I would like to express my gratitude to Prof. Dr. Mohamed Ahmed Owais Professor of Transportation Planning and Traffic Engineering at Civil Engineering Department, Faculty of Engineering, Assuit University; for his valuable advices and recommendations which contributed to this research work.

Thanks are also due to the Civil Engineering Department administration for offering all the facilities that made this research possible.

ABSTRACT

With increasing private traffic on roads, more mobility-related problems such as congestion, air pollution, noise pollution, and accidents are created. Public transportation is very important means to reduce traffic congestions, to improve urban environmental conditions and consequently affects people social lives. Therefore, the need for new public transportation infrastructures for serving new towns and/or improving existing transportation structures to cope with such increase is an urge. Planning, designing and management of public transportation are the key issues for offering a competitive mode that can compete with the private transportation. These transportation planning, designing and management issues are addressed in the Transit Network Design Problem (TNDP).

The main purpose of this research is to develop a novel solution methodology for the TNDP, which goes beyond previous traditional sophisticated approaches. The solution methodology adopted in this research for the TNDP is based on partitioning the solution into two consecutive stages; Transit route Network Design Problem “ TrNDP ” stage (planning side) and frequency setting stage (operational side).

In first stage, a deterministic solution for TrNDP is tackled to construct bus routes. The deterministic manner of the TrNDP solution relies on using linear and integer mathematical formulations that can give an exact solution for the TrNDP. The main objective of the route design stage is to maximize direct demand coverage without violating other parameters of design, such as maximum route length and route network directness.

In second stage, the planner is interested in setting bus frequency on the network in the most precise way regarding which routes to be used and loaded according to passengers ’ interests. So, bus frequencies would be optimally distributed among bus routes (obtained in stage 1) via Genetic Algorithm for a total bus fleet representing operator's main cost. The main objective of frequency setting stage is to minimize user's total travel time while taking into account users' reaction to the given transit network routes.

The novelty of the solution methodology for the TNDP presented in this research stands on the deterministic manner of the TrNDP solution as a primary component for solving the TNDP. A simple procedure for generating directed transit network with criterion defined over links is proposed. This criterion represents the possibility of choosing these links in final transit route configuration. This criterion would reflect Transit route Network Design objective of maximizing direct demand coverage. Frequency setting stage is mainly considered to evaluate the proposed TrNDP solution methodology in solving TNDP in terms of planning and operational aspects.

TNDP proposed solution methodology was tested using popular Mandl ’ s benchmark network problem and compared with previous work results. Compared results showed that the methodology developed in this research is capable of improving transit network solution in terms of planning and operational parameters. Based on the presented methodology, a more robust transit network optimization tool would be produced for public transportation planning and operation purposes.

LIST OF FIGURES

illustration not visible in this excerpt

LIST OF TABLES

illustration not visible in this excerpt

ABBREVIATIONS AND NOTATIONS

Abbreviations:

illustration not visible in this excerpt

Notations:

illustration not visible in this excerpt

CHAPTER 1 INTRODUCTION

1.1. Problem Statement:

It is recognized a remarkable increase in traffic related problems, such as; traffic congestion, air pollution, energy consumption and road accidents. These problems are produced by the large increase of private car ownership. More private car mobility would cost the society high economic and environmental costs¹.

The basic difference between private and public transportation can be illustrated by Fig. 1.1. Assuming that an acceptable level of service is always maintained and that the supply of the public transit capacity is adequate (i.e. the route frequency is determined by the transit demand on any route), it is expected that as demand increases, the level of service provided by a transit system might improve because lower headways might be provided [2, 3].

illustration not visible in this excerpt

Fig.1.1: Relationship between Level of Service and Demand Volume for Auto and Transit

Public transportation is very important means to reduce traffic congestions, to improve urban environmental conditions and consequently affects people social lives. Therefore, the need for new public transportation infrastructures for serving new towns and/or improving existing transportation structures to cope with such increase is an urge⁴. Planning, designing and management of public transportation are the key issues for offering a competitive mode that can compete with the private transportation⁵.

The bulk of the transportation network research mainly focuses on the private transport. (e.g., traffic assignment and network design procedures). However, most of this work studies are not applicable to the transit industry. This gives the possibility of acquiring more efficient usage of the transit systems by more research investigation. Therefore, it stands out as an urban travel solution that deserves more attention and more research effort².

1.2. Transit Planning and Operation

The transit planning and operation process commonly includes five basic activities, usually performed in sequence: (1) network route design, (2) frequency setting, (3) timetable development, (4) vehicle scheduling, and (5) crew scheduling [6-8]. Fig. 1.2 shows the systematic decision sequence of these four planning activities. The output of each activity positioned higher in the sequence becomes an important input for lower-level decisions. Clearly the independence and orderliness of the separate activities exist only in the diagram; i.e. decisions made further down the sequence will have some effect on higher level decisions⁹.

illustration not visible in this excerpt

Fig.1.2: Transit planning and operation process⁹

Transit Network Design Problem (TNDP) is the most important component in Transit planning, in which the overall cost of the public transportation system highly depends on it. The TNDP aims to design a set of bus routes and manage these routes operation in an efficient manner for both users and operators. Different system functions and targets, required for each group of participants, have to be met through solution methodology. TNDP, stated simply, relates to the determination of a set of routes defined over the street network with their corresponding schedules to deal with demand trips ¹⁰.

TNDP deals with a complete hierarchy of decision making process. It includes strategic, tactical and operational decisions. Strategic decisions are long-term decisions related to the infrastructures of transit networks, which including urban route networks; tactical decisions are those concerned with the effective utilization of infrastructures and resources of existing transit networks; and operational decisions are short-term decisions, which are mostly related to frequency setting problem [11-13].

1.3. Transit Network Design Problem (TNDP):

Over the last five decades, the TNDP have been under study for many researchers, most likely because the problem is practically important, theoretically interesting, highly complicated, and multi-disciplinary as well. Solving TNDP depends on solving two sub-problems, namely, transit route design problem and frequency setting problem. Transit route design aims to find efficient transit routes that combine maximum demand coverage and route network directness. Frequency setting aims to find optimal bus frequency on each transit route which minimizes users and operators costs. Optimality of TNDP solution depends on how these sub-problems have been tackled [6, 11, 14].

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. Good TNDP solution should trade off between these inherently multi-objective problems. To alleviate the complexity of solving TNDP multi-objective nature, some researchers would use weighted terms. Operator and users objectives are summed and multiplied by weight factors. The value of any weight factor denotes the relative importance of the term which it multiplied by in the model.

1.3.2. TNDP Solution Methodology Approaches:

Wu and Szeto¹⁸, stated that there are two main approaches to handle TNDP; First approach is to solve the two sub-problems simultaneously taking into account the interaction between them, second approach is to solve route design and frequency setting by separate procedures in a sequential manner [18, 19].

Solving TNDP in one stage usually appears as bi-level problem. It stems from the trend to balance between operator’s decision (upper level) and users decision (lower level). Upper level would concern with route design problem (operator decision) and lower level would concern with frequency setting problem (user reaction). The model tries to take into account the interaction between supply side and demand side²⁰.

It is an accepted approximation to take frequency setting phase after route design to alleviate the complexity of TNDP. This trend of solution was accepted by many researches [10, 21-24].

It is argued that bus routes network design and frequencies setting should not be dealt with simultaneously, since the routes network is a more stable component in a transit system. Transit route design constitutes indeed the strategic stage of TNDP, with a validity range of 5-15 years. The next step in the process is to set the routes frequencies. Theses frequencies may vary according to the following criteria: time of the day (peak/off-peak period), day of the week (Monday- Friday/Saturday-Sunday), time of the year (seasons/vacation periods/others). Thus, route construction should not be influenced by flexible parameters such as frequencies [13, 25].

1.3.3. Transit Network basic concepts

In this part, we would illustrate some transit network basic concepts which are recognized by transit research community. These basic concepts would help in getting a good grasp of the remainder of research work. a. Demand coverage classification The demand for each node pair (d i-j) is classified as -0- transfer, -1- transfer, -2- transfer or unsatisfied demand. Node pair demand d i-j is considered to be satisfied directly (i.e. 0-transfer demand), if there is, at least, one bus route traversed both node (i) and (j). d i-j is considered to be satisfied with -1- transfer, if , at least, one bus route traversed node (i) intersected with other route traversed node (j). d i-j is considered to be satisfied with -2- transfer, if , at least, there is one bus route intersected with route traverse (i) and route traverse (j). Remaining node pairs demand are considered unsatisfied demand. Fig.1.3 illustrates demand coverage classification.

illustration not visible in this excerpt

Fig.1.3: Example of demand coverage types

It is obvious that, d 1-2 is -0- transfer demand, d 1-3 is -1- transfer demand and d 1-5 is -2- transfer demand.

b. Route network directness

Route directness (d(R)) is an indicator to measure bus route deviation from the shortest path among main transit nodes pairs since; d(R) = 1 indicates that all bus users would take the shortest path along their travel between origin and destination. Value of d(R) which exceeds one, it would indicate the delay caused by the set of bus routes to all users.

illustration not visible in this excerpt

where, represents in vehicle travel time between (i) and (j) for passengers’ demand (di-j) using bus route (r); represents travel time between node (i) and node (j) through the shortest path and represents network Total Demand (TD) [14, 17, 26].

c. Transit route length

Transit route length is measured, either in kilometers or in minutes. It is more appealing and practical to deal with routes length in minutes. There is a constraint on maximum transit route length based on either heuristic guidelines, past experience or common practice accepted by transit planners. Longer bus routes may cause bus driver fatigue and consequently result in safety hazards. Maximum round trip shouldn’t exceed 2 hours²⁷.

d. Maximum link flow

After passenger assignment on the transit network, each bus route (r) would have a maximum link flow (Qrax ). It is considered the ruler in setting bus route frequency and bus size to accommodate this maximum flow. Since in large networks, it is too difficult o keep track of all link flows for each bus route, Qrax could be approximately obtained by multiplying the route’s directly satisfied flow with the flowing factors;

illustration not visible in this excerpt

ftf is transferring flow factor which accounts for the transferring flow on the route. f lf is maximum link flow fraction and it would be estimated as flows;

illustration not visible in this excerpt

where is direct demand satisfied by route (r) and n is the number of nodes of bus route²⁸.

e. Service Frequency

The most commonly used service frequencies in the transit industry can be grouped into three categories; supply frequency, policy frequency, and demand frequency. Supply frequency is dependent on the operator’s resources including limited fleet size. It is the maximum frequency that the operator can provide under current resource and economic constraints. Demand frequency is determined by transit demand. This frequency is the minimum frequency that provides just enough capacity to meet the demand on the maximum link flow so that on the other links of this route, the demand is always less than the capacity. Policy frequency can serve as a lower bound and an upper bound for service frequency. It reflects transit network operation constraints and is usually used by transit operators when the demand is too high or too low. In the real world, as well as in the bus transit route network design process, the demand frequency approach is preferred because it reflects the purpose of transit operations, which is to provide customer- oriented service. Furthermore, generally speaking, the maximum bus route frequency and the minimum bus route frequency have been chosen as 30 bus/hr and 6bus/hr [2, 22].

f. Bus route capacity

Bus route capacity concept differs from the ordinary concept of street-link capacity. The route capacity is based on the idea that the route service frequency shouldn’t exceed predefined value and buses have a limit seating capacity, thus maximum allowable flow on bus route-link

illustration not visible in this excerpt

Where X a is the link passenger flow, L.F is desired load factor, f max is maximum allowable frequency and V s is bus seating capacity.

g. Transfer penalty

Transfer penalty is a term which reflects transit users’ inconvenience to make transfer. Transfer penalty is measured by equivalent in-vehicle time units. Penalty values are likely to vary across different geographic areas and change with demographics, socioeconomics, topography, climate, quality of transfer facilities, etc.

h. User cost

Total user cost can be easily expressed by the following expression;

illustration not visible in this excerpt

Where;

UC k users costs associated with mode (k) of travel

TAT total passengers access time in minutes

TWT total passengers waiting time in minutes

TB total passengers boarding time in minutes TIVT total passengers in vehicle time in minutes a w v; weighting values of access, waiting, in-vehicle time⁵.

i. Operator cost Operator main cost (OC k) is the total bus fleet required for operating.

Vehicles operating costs for vehicle type (k) are taken as the sum of the direct costs plus the indirect costs for the given input parameters such as:

The direct costs; (DC) are considered as three factors:

a- Costs of direct travelled distance (L) in kilometer; (CK).
b- Costs associated with time spent at bus stops; (CS).
c- Costs associated with personnel costs; (CP).

Indirect costs; (CF) were found in other studies to be nearly 12% of the direct costs these costs include maintaining buses license, insurance …etc. Total operator cost can be easily expressed by the following expression²⁹ ;

OC k = CK + CS + CP + CF (1.7)

1.3.4. TNDP objectives

As mentioned before, TNDP aims to minimize both users and operators costs under satisfying some constraints. One can derive a general mathematical formulation to clarify TNDP objectives;

illustration not visible in this excerpt

Where

d i-j the transit demand from (i) to (j) expressed as trips per unit time total user travel time between (i) and (j) = (waiting + in- vehicle time) minimum in vehicle travel time between (i) and (j) for passengers’ demand (d i-j) using route (r), r R, where R=(r1, r2,…,rn) a set of bus routes travel time between node (i) and node (j) through the shortest path

R the set of bus routes

r bus route r R

D o min minimum passengers demand within service area to be covered directly (without transfer)

D o1 max maximum passengers demand within service area to be covered indirectly (with one transfer)

D tot total passengers demand within service area to be covered by bus service

D tot min minimum total passengers demand within service area to be covered by set of bus routes

d(R) Bus routes directness indicator

d(R) max maximum allowable directness value for bus routes

T r Bus route (r) travel time

m is the number of nodes on route (r) = (n1, n2, n3,….., nm)

T rmax maximum allowable bus route travel time

N the set of transit network nodes

C 1 & C 2 weighting factors

TBF total bus fleet maximum flow on any link of route (r)

V s Bus vehicle capacity

L.F Bus allowable load factor

Equation (1.8) represents the general objectives of TNDP. First term concerns with users costs. Second term concerns with operator’s cost. C1& C2 weighting factors reflect the relative importance of two cost components. By varying C1& C2, one can generate different trade-offs between users and operator costs. Eqs. (1.9 - 1.11) represent demand coverage constraints. Eq. (1.12) represents route directness. Eqs. (1.13-1.15) reflect operational parameters.

1.4. Research Motivation and Objectives:

The motivation of this research is to develop a novel solution methodology for solving TNDP depending mainly on linear and integer mathematical programming models that can give an exact solution for TNDP and would be solved with their standard solvers. Linear and integer programming models can be solved in large scale problems. Their computational time is very small comparing with other mathematical programming types for the same problem scale. This would help to provide a robust user-friendly software tool for optimizing real size transit networks.

Transit route Network Design Problem (TrNDP) is the most important component in TNDP, where the overall cost of the public transportation system highly depends on it. Once the transit network is defined, a set of routes is identified over the street network and subsequently all decisions about timetable development, bus and driver scheduling are conditioned to it. So developing a new approach for designing transit routes was given high concern in this research to meet these objectives;

1- The development of a solution methodology for optimal bus route construction, which would be applicable for small, medium and large size urban networks, and also confirm to several network routes configurations.
2- The main objective is to design a set of bus routes that minimizes both users and operators costs and satisfies some constraints, such as; route directness, minimum demand to be covered directly and maximum bus route length.
3- Adopted solution methodology should be flexible; since planner can classify generated bus routes according to demand coverage, which enables operator to execute selected routes according to available resources.

Transit passengers, in many cases, deal with overlapping bus routes with some routes sharing common sections and stops. Passenger assignment problem is a major task in frequency setting of bus service which aims to minimize passengers and operator costs. In this work, we are seeking for an explicit assignment model to track each proportion of passengers’ in selecting bus routes for -0- and -1- trips transfer which is the primary task. The proposed model should help for a given transit network and total bus fleet size to minimize network total travel time. This would happen by optimally distributing bus frequencies among bus routes, regarding passengers’ interests in selecting bus routes.

The standards of evaluation for the global solution methodology, involving final transit route configuration, frequency setting and other design issues, should be clearly defined, so that the output supply system of bus transport system could be produced at lower social cost.

1.5. Thesis Organization:

The thesis has been organized in the following seven chapters; these are:

illustration not visible in this excerpt

CHAPTER 2 BACKGROUND OF TRANSIT NETWORK DESIGN PROBLEM

2.1. Introduction:

The Transit Network Design Problem (TNDP) is an important component of urban transportation planning. It deals mainly with investigating optimal planning and operation of transit networks in urban areas. Therefore, TNDP can be divided into sub-problems, namely, Transit route Network Design Problem (TrNDP) which is representing the planning side and frequency setting problem which is representing the operational side³⁰. TrNDP deals with transit routes layout configuration. Resulted transit routes should satisfy some requirements for both users and operators. Frequency setting problem deals with transit vehicle scheduling and vehicle assignment time table. Its main problem is passenger reaction towards a given transit service. This problem is called passenger assignment.

Once the transit network is defined, i.e. a set of routes is identified over the street network, subsequently all decisions about timetable development, bus and driver scheduling are conditioned to it. Frequency setting aims to find optimal bus frequency on each transit route which minimizes users and operators costs⁶.

User costs are often measured by the total travel time which consists of access, waiting, in-vehicle and transfer (if any) time. Operator costs depend on the fleet size, vehicle type, vehicle executing distances in kilometers and vehicle operating hours.

TNDP always associates with feasibility constraints. These constraints may include minimum demand coverage, maximum demand covered indirectly with one or two transfer, route network directness, maximum and minimum bus route time length, minimum and maximum allowable frequency on bus route, vehicle load factor and total fleet size. These constraints may be grouped into two categories of constraints; constraints related to available resources like maximum fleet size and demand coverage and constraints related to practical and operational bounds like maximum and minimum route length and allowable frequency on each bus route.

2.2. Literature Review:

In practice, TNDP may involve multiple conflicting objectives and constraints. TNDP has been tackled in many researches, each research considered different objective function, constraints, problem solution approach, solution methodology and search algorithm to be implemented in the solution [4, 23, 24].

In this section, we would present a brief description of some highlighted TNDP researches. We would describe considered objective function, adopted solution approach and implemented solution methodology for each research work.

2.2.1. Lampkin and Saalmans, 1967

Lampkin and Saalmans³¹ uncoupled the design of transit routes and the setting of frequencies and tackled them separately. They proposed an optimization model to determine the routes of the networks first and then to assign frequencies to the generated set of routes in a second stage. In the first stage, heuristic methods are used to construct “skeleton” routes, and these skeleton routes are expanded to cover the full set of nodes in the network in attempt to transport a maximum number of passengers. Once the routes are defined, the frequencies are determined by minimizing the total passenger travel time, calculated as the sum of the O-D demand multiplied by the travel time ( ) , subject to a constraint on the total fleet size (as a budget constraint):

illustration not visible in this excerpt

In this formulation, RTr is the round-trip time on route r and fr is the frequency on route (r). The travel time ( ) includes the expected waiting time, as a function of frequencies of routes. The objective of the second stage is to allocate service frequencies to the already-generated routes so that the total travel time was minimized given the available number of vehicles. They used a random gradient-based search procedure to determine the final frequency values.

2.2.2. Silman et al. 1974

Silman et al. ³² presented a planning method for urban bus route systems, trying to minimize the sum of journey time (included allowance for transfer times) and discomfort penalties proportional to the number of passengers who cannot find seats. A two-staged approach is employed. First, the candidate routes set are constructed through several repetitions of a route addition and deletion process. Second, the optimal frequencies for a set of already-generated routes were determined by a gradient method under the constraints of a given number of available buses.

2.2.3. Dubois et al. 1979

Dubois et al.³³ decomposed the network generation problem into three sub-problems, i.e., to choose a set of streets, to choose a set of bus lines, and to determine optimal frequencies. In the first step, a traditional network design problem is formulated, using only in-vehicle times as the travel times, subject to a budget constraint on the cost of operating on a street, and binary decision variables indicating whether a street segment is in the final solution. A heuristic procedure is used to solve this problem, beginning with an initial spanning tree to minimize the total travel time and adding links to minimize the total transit network cost. A simple all-or-nothing assignment of the O-D flow on the shortest paths is used to estimate the objective function. Then, in second stage, a model is presented to find the optimal bus lines given the chosen street subset. This set of routes is then subject to heuristic rules to determine the final route structure: (1) routes with heavy transfer flow are joined; (2) route segments are deleted where the demand is effectively served by other routes; and (3) routes that overlap are joined. In the third step, the optimal route frequencies are found using a gradient-based search heuristic, similar to Lampkin, W. and Saalmans. Waiting times were explicitly considered in this last step. The transit demand between any origin-destination pair was treated as a variable that responded to the network design solution. The work included transit trips that required transfers.

2.2.4. Mandl, 1980

Mandl²¹ employed a single path assignment method, assuming that all passengers traveling between a specific origin-destination pair use the single least weighted cost path. In his work, Mandl presented a heuristic algorithm to find the optimal routes. Also, Mandl assumed a constant frequency on all bus routes (policy headway), which made the TNDP a much simpler problem. The optimization process is described as follows. A set of feasible routes is examined and possible reductions in the average cost using this set are attempted. The new set was compared with the older one on the basis of performance and if found better, it is accepted and the search procedure is repeated until no new improvements could be found.

2.2.5. Ceder and Wilson 1986

Ceder and Wilson⁶ would be considered one of earlier researchers to define a conceptual model of bus planning process as systematic decision composed of five sequence levels, namely, bus route construction, frequency setting , time table development, bus scheduling, driver scheduling. Each level output becomes an input to lower level decision. A two level methodological approach was presented for TNDP, in which the first level considered only the passenger viewpoint and the second level accounted for both the passenger and operator viewpoint. Two constraints that are considered include minimum frequency and fleet size. The first level is handled by an optimization program while the second level relies on heuristic techniques.

2.2.6. Baaj and Mahmassanis 1990, 1991, and 1995

Baaj and Mahmassani [16, 22, 34] proposed an AI-based solution approach that consists of three major components. The first part is a hyper route generation algorithm (HRGA) that generated different sets of routes corresponding to different tradeoffs between user cost and operator cost. The second part is a transit route network analysis procedure (TRUST) to evaluate a given transit route network as well as to set its associated route frequencies. The third part is a route improvement algorithm (RIA) to improve the initially generated sets of routes so as to obtain feasible and implementable route networks. RIA includes these actions; route joining, route splitting and routes branch exchange. The code language used for solution methodology development is LISP.

2.2.7. Shin and Mahmassanis 1994

Shin²⁸ proposed essentially the same approach as that of Baaj, in which an artificial intelligence (AI)-based search approach guided by expert knowledge is used to solve TNDP. His work would be considered an extension to Baaj work. The approaches employed in these two works consist of four major procedural components: a route generation procedure, a network evaluation procedure, a transit center selection procedure and a network improvement procedure. The difference between Shin’s work and Baaj’s work is primarily the conventional service concepts. Baaj work depended on providing fixed route, fixed schedule and uncoordinated systems, with the same vehicle size on all routes. Shin work incorporates three additional service design concepts including route coordination, variable vehicle size, and demand responsive service. However, both of these works are heavily dependent on the experience and judgment of the transit planners and knowledge of the existing demand patterns, land use patterns and resource constraints.

2.2.8. Pattnnik et al. 1998

Pattnnik et al.²³ formulated the TNDP with fixed transit demand as an optimization problem of minimizing the overall cost (i.e., the sum of user total travel time cost and operator cost). Constraints included frequency and load factor feasibility. He implemented a two-phase procedure for TNDP. First phase, a set of feasible bus routes are generated through heuristic procedure and second phase Genetic Algorithm (GA) is applied to select optimal (or near - optimal) bus routes network.

2.2.9. Gao et al. 2004

Gao et al.²⁰ proposed a bi - level programming model for TNDP which incorporates upper level objective function (Bus network design model) and lower objective function (transit equilibrium assignment model). Their solution approach focuses on the interaction between supply side and demand side similar to continuous equilibrium network design problem. A solution algorithm based on sensitivity analysis is used for the proposed model.

2.2.10. Guan et al. 2006

Guan et al.³⁵ developed a TNDP solution as an integer Mathematical Programming taking into account transit route configuration and transit passengers assignment simultaneously. Their model consists of three weighted terms representing total route cost, total passenger in - vehicle time and total number of transfers. Their objective function makes a balance between the operator cost and passengers cost through the value of weighted factors. They indicated that the problem could be easily solved by standard branch and bound algorithm, since all model’s variables are integer.

2.2.11. Cipriani and et al. 2012

Cipriani and et al.⁴ developed their TNDP solution methodology in two stages. Their solution depends on the integration among different transit modes in their case study. In the 1st part (stage1), a solution procedure for Rome city Transit network based on heuristic algorithm generates three different and complementary sets of rational and realistic route types, namely; (“A”, “B”, “C”). They are built according to different criteria of efficiency and effectiveness (users and operators point of view);

“A” type: Connecting highest demand node pairs which are not served by rail system

“B” type: Connecting main transit centers (possibly rail stations)

“C” type: Existing bus network routes

The heuristic route generation algorithm is divided into the following three sequential steps:

1- Generation of A, B and C type routes.
2- Check the feasibility constraints (maximum and minimum allowable route length) for all routes stored in the set of feasible routes.
3- Save all routes that satisfy the feasibility constraint as input data for the search scheme (Genetic Algorithm).

At the end of A, B and C route types generation, a construction algorithm consisted of an iterative All - or - Nothing demand assignment is done. In second stage, GA is implemented to find the optimal network routes - from candidate generated routes A, B and C - and their frequencies.

2.2.12. Yu and Yang 2012

Yu and Yang³⁰ used ant Colony Optimization to generate three types of bus routes to cover transit network demand, namely; skeleton, main and branch routes. Their objective function is to maximize demand coverage density. Their solution methodology simulates ants' behavior in searching for food to obtain best transit route network. Then, trips are assigned incrementally to transit network to reach an approximate equilibrium. Each portion is assigned to shortest path between origin and destination according to in-vehicle travel time plus waiting time. After each assignment, the network travel time is updated by the shortest hyper path algorithm calculating the new expected waiting time and the change in the shortest hyper path.

2.2.13. Summary of TNDP Literature Review

Reviewing previous research works, it could be stated that TNDP formulation consists of five main parts, namely,

- Representation of transit network.
- Solution approaches representing design objective functions.
- Identifying transit network constraints.
- Passenger assignment as a major task on frequency setting of bus.
- Solution search space schemes.

Table 2.1 provides a summary of main features for research works reported in the literature. We would distinguish six features that characterize TNDP among previous literature, namely,

- Objective Functions, the most widely used objective function is minimization of generalized cost (or time) or Multi objectives.
- Demand, there are two main types of demand addressed in literature fixed and variable demand.
- Constraints, feasibility constraints often include: minimum operating frequencies, a maximum load factor, a maximum allowable bus fleet size, maximum and minimum route time lengths, maximum and minimum allowable bus frequency on route and constraints of route network directness.
- Decision Variables, network route configuration and service frequency are main decision variables.
- Passenger Behavior, previous transit trip assignment models can be divided into two groups, namely, single path assignment and multiple path assignment models. Another aspect of passenger behavior that is also of interest is the passenger willingness to make transfer trips. In addition to the extra passenger waiting time incurred as a result of transfers, a transfer penalty is also often incorporated.

- Solution approaches, most approaches rely on Mathematical Optimization, Heuristics, Meta-Heuristics or combination of them in solving the TNDP sequentially or simultaneously.

Table 2.1: Main Features of Some Approaches Used in TNDP

illustration not visible in this excerpt

2.3. TNDP Solution Methodologies Categorization

It is obvious that a great deal of researches have been conducted in the area of TNDP. Their adopted solution methodologies may be roughly grouped into three categories, namely; Mathematical optimization, Heuristics and Meta- heuristics. We couldn’t define strict bounds among these groups. A TNDP solution methodology may contain one or combination of these methods.

2.3.1. Mathematical Optimization

Optimization is a process or a technique to search for the best solution for a problem or procedure as effective or perfect as possible. In mathematical terms, optimization is a technique for finding a maximum/minimum value of an objective function of several variables subjecting to a set of constraints.

Mathematical optimization may take several mathematical programming formulations depending on decision variables and constraints. Popular formulations are linear programming, integer programming, non linear - convex programming, non linear - non convex programming, mixed integer linear programming, mixed integer non linear programming and bi-level programming ³⁶.

For transit network design problems, mathematical optimization is usually formulated as constraint mixed non-linear integer optimization problem, which includes integer and continuous variables related in non-convex and non-linear objective function. Integer variables (discrete variables) are usually representing transit route choice, whereas continuous variables are representing frequency setting on transit routes. Objective functions may include minimizing overall user cost or a combination of user and operator costs. Constraints are usually expressed as inequality constraints, such as the maximum allowable bus frequency, bus load factor and bus fleet size³⁷.

Compared with other methods used in transit network design, the mathematical optimization based solution techniques have a complete solution search space. In other words, its solution is not biased toward any predefined transit route network and global optima could be reached.

Mathematical Optimization formulations related to TNDP solution have a crucial disadvantage. It usually has a large solution search space due to its combinatorial intractability. This results in a substantial difficulty in solving it with exact methods. These mathematical formulations always lead to usage of heuristics or Meta - heuristics to reduce the size of solution search space [36- 38].

2.3.2. Heuristics

Heuristics refer to experience-based techniques for problem solving, learning, and discovery. Where the exhaustive search is impractical, heuristic methods are used to speed up the process of finding a satisfactory solution; mental shortcuts to ease the cognitive load of making a decision. Examples of various heuristics methods that have been widely used in engineering, economics, social and natural science are greedy algorithms, nearest neighbor algorithms, rollout algorithms and Tabu search algorithms.

Heuristics approaches have been used for TNDP in many researches. They are still the most widely used methods in transit planning. They depend heavily on personal knowledge and experiences. They improve the search efficiency or problem solvability. They are considered as a practical tool for problems of which the search space is too large.

In TNDP, heuristics approaches are usually a combination of application of guidelines and procedures for route selections and bus frequency determination. Intuition of transit planner established from past experience as well as some policies out of social and economic consideration should be implemented.

There are several advantages of heuristics approaches. They are always able to provide feasible solution to TNDP for any problem scale. The solution structure obtained from heuristics tends to be conceptually easy to understand. They are applicable to several networks types, for example, radial networks and grid networks.

In other hand, heuristics also have disadvantages. One of the main disadvantages of heuristics approaches is that their results don’t always guarantee global optimal solution or even local optimal solution. Therefore, heuristics approaches are considered as approximate approaches.

2.3.3. Meta - Heuristics

Meta-heuristics approaches could be considered a computational tool for solving optimization problems. They usually don’t depend on any mathematical basis. Meta-heuristics make few assumptions about the problem being optimized and can search very large spaces of problem solution search space. They would be considered stochastic methods.

Meta-heuristics have been established as one of the most practical approach to TNDP solution, because these methods are generally designed for combinatorial optimization problems. They implement efficient mechanisms to explore the search space. Examples of Meta-heuristics approaches are Genetic Algorithm (GA)³⁹, Simulated Annealing (SA)⁴⁰ and Ant Colony Optimization (ACO)⁴¹.

Although Meta-heuristics approaches don’t guarantee global optimal solution, it could guarantee local one. They can get better performance by making change in their nature of design to jump out of local optima to reach the global one. Fig. 2.1 depicts how Meta-heuristics search space work.

illustration not visible in this excerpt

Fig. 2.1: Meta - Heuristics Search Space

2.4. Review of a pioneer work

In this section, we would focus on Baaj and Mahmassani 1995 research work. This because Baaj and Mahmassani work²² was cited by several TNDP researchers. Their work is considered a pioneer work and many researchers were inspired by it. It was developed by many later researches in attempt of attaining better results. A Good Understanding of their solution methodology opens the gate to understand the whole Transit Network Design Problem and difficulties of solution.

They proposed four sequential procedures, as mention before in literature review section, for solving TNDP. We consider two procedures as the primary Skeleton of overall solution of the problem, namely, a Hybrid Route Generation Algorithm (HRGA) and Network Analysis Procedure (NETAP)¹⁶.

2.4.1. Hybrid Route Generation Algorithm (HRGA)

Baaj and Mahmassani ²², proposed HRGA which is a greedy constructive algorithm that generates a set covering formulation to select a suitable set of routes from a previously generated pool of candidate routes, ensuring the fulfillment of demand covering constraints. It also takes care of the interests of users and operators in the produced results. HRGA also allows specifying a predetermined set of routes as an initial partial solution. It proceeds by iteratively adding routes to the solution under construction. Routes are generated by using the shortest path in (G) graph between vertices with high demand. Additional vertices are then inserted in these routes (expansion of routes) according to a predefined criterion such as; the increase in the network’s total demand satisfied directly as result of inserting node in the route under expansion. The algorithm ends when the set of routes under construction fulfils demand covering constraints.

HRGA is a heuristic design algorithm that is heavily guided by the demand matrix, allows the designer’s knowledge to be implemented so as to reduce the search space and generates different sets of routes corresponding to different trade - offs among conflicting objectives. RGA’s input data may be grouped under five categories summarized in Table 2.2

Table 2.2: HRGA Input Data

illustration not visible in this excerpt

The Structure of HRGA, which is explained in the flow chart given in Fig. 2.2, consists of the following steps:

*Note: M= number of initial node pairs, k= number of node pairs visited by route Kth, K=number of route generated N= number of subset node pairs

Step 1: Sorting the demand matrix in decreasing order according to total number of node demand, then identify the M node pairs with the highest demand.

Step 2: Select the 1st M node pair of the sorted demand matrix and then remove it from the matrix; set K=1

Step 3: Design (i.e. specify the nodes of ) the Kth route corresponding to the kth node pairs. In this step, a given high demand node pair along the shortest path would be connected, thus the initial skeleton is defined.

Step 4: Check if all the M node pairs have been specified. If k = M (i.e. the number of node pairs k visited by route K is equal to M), go to step 5, Background of Transit Network Design Problem Chapter 2 otherwise, set K = K+1 and return to step 2.

Step 5: Check the set of K routes for the presence of N subset node pairs. If N = 0 (all K routes are independent an acceptable), go to step 6. Otherwise, identify the N subset routes and remove them from the K routes generated so far. Set k = M - N, return to step2.

Step 6: Compute the total demand satisfied directly using the K independent routes generated so far. If that demand exceeds Domin (minimum percent demand satisfied directly) go to step 7, otherwise, set M = M + 1, and return to step 2.

Step 7: Compute the total demand satisfied by the set of k routes (via 0 or 1 transfer). If that demand exceeds Dtotmin (the minimum percent total demand satisfied) terminate RGA process and output the set of K routes, otherwise, set M = M+1.

illustration not visible in this excerpt

Fig. 2.2: HRGA reproduced from Baaj and Mahmassani²²

We could distinguish three main elements of HRGA which affect its final results. These elements are;

1. Initial number of skeleton routes M

HRGA queries the user for the number of initial skeletons M. The number of M should generate set of routes satisfying minimum percentage of the total demand that has to be satisfied directly by initial expanded skeletons. It is desirable to select M less than the eventual number of routes needed. If non value of M is defined, M is set to 1 and HRGA adds routes one by one until a satisfactory set of routes is found. Different values of M results in different routes configuration.

2. Routes expansion:

The algorithm takes the advantage of previously existed route to cover the demand between vertices which are close to that route and vertices which are already included into it. Thus, the expansion of a route considers the insertion of vertices on it taken from a set of candidate vertices. A feasible candidate is a vertex (V) which is at distance one (measured in number of edges) from the route (r) and fulfils the following constraints;

1- It doesn’t already belong to route Kth under expansion.
2- It still has a high percentage of its total originating demand left; uncovered after previous insertions in other routes.
3- The resulting route (after insertion v in r) doesn’t become circuitous.
4- The ratio of the contributed incremental demand value exceeds a minimum value.
5- The required frequency of service on the resulting route doesn’t exceed a maximum operational value.
6- The Round - trip time of the resulting route doesn’t exceed a maximum allowable value.

The routes are expanded to a node selection strategy reflecting different trade - off between performance measures, user and operator costs. Selection of high demand nodes (O/D) pairs is repeated until the pairs of terminal nodes to be connected are all examined and objective goals have to be verified. A route is expanded until the set of feasible candidates to be inserted is empty.

3. Designer ’ s knowledge:

The designer is queried for the value of M and one identifies the M node pairs according to his knowledge of the dominant trip generator and attractors. The designer also implements his knowledge in determining the seeds nodes to each route expansion and the order of route expansion.

2.4.2. Network Analysis Procedure (NETAP)

For the set of routes generated by HRGA¹⁶, the network analysis procedure (NETAP) is then utilized. It utilized to assign the given transit demand, compute network descriptors and determine frequencies for all bus routes.

The NETAP follows an iterative procedure, starting with an initial set of frequencies associated with the given routes. In each iteration, a new set of route frequencies is determined according each route maximum link flow (obtained from incorporated assignment model) and compared to the input frequencies. If the revised frequencies are significantly different from the input values, the NETAP iterates with the revised values serving as input frequencies until they converge. Fig. 2.3 illustrates the procedure of NETAP.

illustration not visible in this excerpt

Fig. 2.3: Network Analysis Procedure¹⁶

Information are determined by the NETAP are;

1. Node information contains originating flow, terminating flow and transferring flow at each demand node.
2. Link information includes link flows along each route. The maximum link flow on each route is used to determine route frequencies and maximum load factor.
3. User cost: the total travel time experienced by users in the system and the respective percentages of in-vehicle, waiting, transfer time and penalty time.
4. Operator cost: the system operation cost and required fleet size.

2.5. Draw-backs and Short Comings of previous works

- Proposed mathematical optimization approaches always suffer from combinatorial intractability.
- Heuristic approaches are always able to provide feasible solutions but they don’t guarantee the global optimal solution or even unique solution to the problem.
- Meta - Heuristic approaches for TNDP are usually take tremendously computational effort and much more CPU time than what deterministic approaches would take.
- The success of the Meta - Heuristic approaches depends heavily on the quality of the chosen representation and the effectiveness of the initialization procedures.
- The implementation of the shortest routes between demand centers in previous literature is not always efficient as far as demand coverage is concerned.
- We couldn’t identify an explicit optimization model for passenger assignment on transit network.

CHAPTER 3 TRANSIT NETWORK DESIGN PROBLEM SOLUTION METHODOLOGY APPROACH

3.1. Introduction

From reviewing previous literature studies regarding Transit Network Design Problem (TNDP), we stated some remarkable draw - backs and short comings in previous problem solution approaches. Therefore, in order to overcome these short comings reviewed so - far in literature, it is essential to provide a consistent solution methodology which contains effective mathematical formulations of the problem and their solution algorithms to reach the best values of maximum service coverage, route directness, minimum transfers and minimum users and operators transport costs.

Aimed objectives of this research part is to reach a simple and efficient methodology for optimal transit route design which gives procedure for solving TNDP and would be rather most applicable to small, medium and large size networks, and also would conform to several network routes configurations. The aimed methodology goes away from sophisticated techniques reviewed so far in the literature. This approach also would overcome solution difficulty for TNDP due to the non - convex nature of the problem, the combinatorial intractability and the confliction between users and operator goals (multi - objective optimization)⁴².

The solution methodology adopted in this research for the TNDP is based on partitioning the solution into two consecutive stages; Transit route Network Design Problem “TrNDP” (planning stage) and optimal frequency setting problem of bus service (operational stage).

In first stage; a deterministic solution for TrNDP is tackled to construct bus routes, while achieving maximum direct demand coverage. The deterministic manner of the TrNDP solution relies on using linear and integer mathematical formulations that can give an exact solution for the TrNDP. The main objective of the route design stage is to maximize direct demand coverage without violating other parameters of design, such as maximum route length and route network directness.

In Second stage; bus frequencies are optimally distributed among bus routes (obtained in stage 1) via Genetic Algorithm for a predefined total bus fleet representing operator's main cost. The main objective of frequency setting stage is to minimize user's total travel time while taking into account users' reaction to the given transit network routes.

Fig. 3.1 presents the main frame work of overall TNDP solution methodology. Street Network representation (see section 3.2) and Transit (O/D) matrix (see section 3.3) represent TNDP dominant input data. The core of TNDP solution methodology is the two stages of route design and frequency setting. Evaluation and feedback are made to stand on the solution methodology efficiency and effectiveness. The remainder of this chapter is dedicated to give a brief description of solution methodology components, whereas route design and frequency setting stages are illustrated, in detail, in chapter 4 and chapter 5 respectively.

illustration not visible in this excerpt

Fig. 3.1: TNDP solution methodology frame work

3.2. Street Network representation

The term "network" in transportation planning is used to describe a structure of streets and intersections (nodes) to be used in Mathematical Programming representation for TNDP. Street network and nodes are considered the infrastructure for TNDP. Representation of transit demand and infrastructure is given in Fig. 3.2.

illustration not visible in this excerpt

Fig. 3.2: Representation of transit demand and the infrastructure⁴³

A network is represented as a graph in which arcs have an associated flow. A graph is a structure that is built by interconnecting nodes and arcs. The graph representation of the urban network can vary from planner to another depending on the level of required detail, available data and analysis technique.

We could classify two basic level types of street network representation for TNDP. First type is zone centroid level where each zone demand is aggregated at its centroid. Second level is node level where each node in the network is considered as a potential bus stop (origin). It isn’t practical solution to consider all these nodes as bus stops, so filtering stage should be provided to select candidate bus stops (nodes) according to each node demand and maximum allowable walking distance. In this research and for purpose of uniqueness and simplicity, bus stops would be considered as street network zone centroids [26, 44].

Two types of graphs are presented in Fig. 3.3. Undirected graph which arcs are bi-directional is depicted in Fig. 3.3.a. A directed graph is a graph in which the arcs have specified directions by arrow heads as shown in Fig. 3.3.b. A directed graph representation is adapted in the proposed solution methodology. For a given urban network, it can be defined as G = (N, A), where (N) is the set of nodes ( directed arcs (links) (⁴⁵.

illustration not visible in this excerpt

Fig. 3.3: Graphs and directed graphs⁴⁵

There are some further definitions associated with graphs and networks:

Chain : a sequence of arcs connecting two nodes i and j. For example, in Fig. 3.3.a, we might connect nodes 1 and 4 via the chains 1-2-3-4 without considering the directions of links.

Path : a sequence of directed arcs connecting two nodes. In this case, one must respect the arc directions. For example, Fig. 3.3.b, a path from 2 to 4 might be 2-1-4 and it can’t be 2-3-4, according to directed links.

Cycle : a chain that connects a node to itself without any retracing. For example, in Fig. 3.3. a, 1-2-3-4-1 is a cycle.

Using computer representation of graphs has enabled planners to handle large networks of huge number of vertices and edges. Computers use matrices as appropriate data structure. Adjacent matrix of dummy variable (*) is presented ⁴⁶.

illustration not visible in this excerpt

their desired (O/D) trips which are concentrated at zone centroid. Transit modes supply services are routed in an environment to pick - up and deliver passengers demand among - what is called - Transit (O/D) locations through selection of efficient bus routes from a given street network representation.

Demand is an essential element for transit network design. The more precise transit O/D demand estimation, the more adequate TNDP solution. In previous researches, we found two approaches for tackling transit demand. First approach considers demand is fixed and independent of service quality. Second approach considers demand is variable and dependent on simultaneous distribution - modal split. However, the variable demand assumption is more appealing, the first assumption is common used for purpose of simplicity. In this research, we would take the first assumption leaving the second for further researches [47, 48].

For certain zone, the number of originated or destinated trips is a product of population, employment, land-use and transit (expected) level of service in this zone. There are two approaches for transit (O/D) matrix estimation. First approach is to use the traditional four-step travel forecasting model as depicted in flow chart, Fig. 3.5. This approach is suitable for networks that would be designed from scratch (new towns without any existing transit systems). Second approach, is to use counting data at existing bus stops.

illustration not visible in this excerpt

Fig. 3.5: Flow chart of the traditional transportation demand analysis⁴⁹

3.4. Transit route Network Design (TrNDP)

The solution methodology for the TNDP presented in this research depends on a deterministic manner for the TrNDP solution, since it is considered as a primary component of solving the TNDP. A simple procedure for generating directed transit network with criterion defined over links is proposed. This criterion represents the possibility of choosing these links in final transit route configuration. This criterion would reflect Transit route Network Design objective of maximizing direct demand coverage. TrNDP solution methodology is described in detail in chapter 4.

3.5. Frequency setting

An explicit mathematical programming for transit passenger assignment problem would be developed. The model would be able to track the behavior of each proportion of transit passengers in selecting bus routes, for a given set of bus routes defined over the transit network and a total available bus fleet. This would be the key for optimal frequency setting on bus routes. Frequency setting stage is mainly considered to evaluate the proposed TrNDP solution methodology in solving TNDP in terms of planning and operational aspects. Frequency setting methodology and procedure is described in detail in chapter 5

3.6. Transit Network

Essential speaking, planners should differ between two terms, namely; street (road) network and transit network. Street network refers to all existing streets and their intersected nodes presented in the studied network. Transit network, as mentioned before, aims to identify a set of bus routes over the road network achieving some transit objectives under some constraints. This set of connected bus routes constitutes the transit network, see Fig. 3.6.

illustration not visible in this excerpt

Fig. 3.6: Street network representation and transit network representation

It should be noted that a particular transit network would differ from the original street network from which it is derived, provided some links presented in the street network are absent from the transit network. As a consequence, shortest path distances for travelers between the various node pairs will need to be recalculated for each new route set that is evaluated, using a distance or time matrix specific to that new transit route network. We will assume that each traveler chooses the shortest path (in the evaluation process of route network) from source to destination node, without regard to the number of transfers. Waiting times are not included in our shortest path calculation. Instead transfers were dealt with separately in frequency setting part.

3.6.1. Connectivity of Transit Network

As stated before, we would simply obtain the transit network by fusing together all the routes in transit route set. Connectivity of transit network is measured in terms of all route set is connected, see Fig. 3.7. In Fig. 3.7.a, all transit nodes is connected, i.e. you can reach all nodes beginning with any node in the network. In Fig. 3.7.b, it is obvious that nodes (2) and (5) are isolated from the network⁵⁰.

illustration not visible in this excerpt

a- connected transit network

illustration not visible in this excerpt

b- unconnected transit network

Fig. 3.7: Transit Network connectivity

Connectivity check can be conducted through this heuristic rules⁵¹:

illustration not visible in this excerpt

3.6.2. Transit Network structures

This section describes different Transit Network structures that are the key component to deliver an accepted accessibility level to transit user. To achieve accessibility standards, transit network must uniformly cover the service region in space and time with well-spaced transit stops and frequent reliable service. Good spatial coverage limits the walking time to/from every point in the service region and thus access/egress time.

We would identify two basic types of transit network shapes, namely; hub-and-spoke (radial) and grid structure, see Fig. 3.8. Hub-and-spoke (radial) routes lead from a central area such as the central business district (CBD) or town centre in radial directions to different suburban or other trip generators. These routes usually coincide with the location of the corridors of heaviest transit travel and are typified by a heavy commercial, residential or industrial development. Grid routes are grid configurations designed generally to increase system flexibility to serve high density areas or numerous activity centers. Each node in the grid system is considered as transfer point. Flexibility of the network is measured in terms of number of transfer that would be made by transit user [42, 52-55].

Thus * = 1 if and if only the two vertices i and j are connected in G. An

example of adjacent matrix for small network is depicted in Fig. 3.4.

illustration not visible in this excerpt

Fig. 3.4 : Adjacent matrix for small network

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

Main TNDP data are the demand trips between different traffic zones of the city and the street network structure. Passengers’ demands for travel among Origin - Destination (O/D) locations represent the need of transport system.

[...]