23-06-2012, 11:32 AM
A GENETIC ALGORITHM BASED BUS SCHEDULING MODEL FOR
TRANSIT NETWORK
[attachment=25193]
INTRODUCTION
The design of bus transit system may be considered as a systematic decision process consisting
of five stages: network design, frequency setting, time table development, bus scheduling and
driver scheduling. However, the two most fundamental elements, namely, the design of routes
and setting of frequencies, critically determine the system’s performance from both the operator
and user point of view. Significant savings in resources can be made by reorganization of bus
Proceedings of the Eastern Asia Society for Transportation Studies,
routes and frequency to suit the actual travel demand. In Kidwai (1998) the solution framework
for transit network design consists of three major components, namely, transit route design,
transit assignment and transit scheduling. In this paper transit bus scheduling problem is
formulated and solved in two phases. In the first phase, buses are assigned to individual routes by
an interactive procedure.
REVIEW OF PAST STUDIES
A review of literature reveals various approaches and different computational tools for
scheduling of urban bus transit problem. Lampkin and Saalmans (1967) formulated a constrained
optimization problem for frequency determination. Their objective was to minimize the total
travel time for a given fleet size constraint and a random search procedure was used for solution.
Rea's (1972) model search for an optimum bus network by adjusting iteratively the frequencies
and type of buses on each link to correspond to the link flow level, such that the service on some
links is enhanced whilst on others it is depleted. The optimum situation is reached when no
further change in link service levels is detected. Silman et al. (1974) determined optimum
frequencies for a set of bus routes and fleet size, which could minimize the total travel time and
discomfort (travelling without a seat) by a gradient method procedure. Hsu and Surti (1977) used
the concept of marginal ridership (ridership provided by an additional unit of service frequency)
to determine adequate frequency for each route for a given fleet size.
PROPOSED METHODOLOGY
First general formulation for optimal bus allocation problem is given. In the present methodology
a bi-level optimization is used to solve this problem. In the first level, minimum frequency of
buses (then the number of buses) required on each route with the guarantee of load feasibility is
determined by considering each route individually. Then by summing up the number of buses on
each route fleet size is determined. In second level by taking the fleet size of first level as a lower
bound, the fleet size is again minimized by considering all routes together and using GAs.
Model for Transit Network Assignment
The assignment model is crucial in transit network analysis because it determines the passenger
flows on each links, which are used to calculate various costs and performance measures. This
requires the assignment of passenger demand matrix to the set of routes that define any feasible
transit network configuration. Han and Wilson (1982) used multi-path transit assignment, with
transfer avoidance and/ or minimization acting as the primary choice criterion. Baaj and
Mahmassani (1990) adopted this feature and developed a procedure for transit network analysis,
and a similar procedure is adopted in the present study.
Second Level Optimization
In the first level optimization, the base fleet size has been determined by considering individual
route's capacity and no attempt is made to get the minimum fleet size on global bases (i.e.
considering all the routes together). The reason why one can still reduce the fleet size below the
base fleet size may be attributed to the extensive overlapping of the routes. If there is no
overlapping of the routes, one can't hope to reduce the fleet size below the base value. Though
there are various reasons of, how extensive overlapping of routes may help to reduce the fleet
size, two reasons are discussed below.
GENETIC ALGORITHMS
The idea of genetic algorithms (GAs) was first conceived by Professor John Holland of the
University of Michigan in 1975. Genetic algorithms are computer based search and optimization
algorithms which work on the mechanics of natural genetics and natural selection (Goldberg,
1989). The mechanics of a simple genetic algorithm are simple involving copying strings and
swapping partial strings. The explanation of why this simple process works is subtle yet
powerful. Simplicity of operation and implicit parallelization are two of the main attractions of
the genetic algorithm approach.
Working Principle
GAs begin with a population of string structures created at random. Thereafter, each string in the
population is evaluated. The population is then operated by three main operators - reproduction,
crossovers and mutation - to create a hopefully better population. The population is further
evaluated and tested for termination. If the termination criteria are not met, the population is
again operated by above three operators and evaluated. This procedure is continued until the
termination criteria are met. One cycle of these operators and the evaluation procedure is known
as a generation in GA terminology. Figure 3 illustrates a pseudo code for a simple genetic
algorithm.
TRANSIT NETWORK
[attachment=25193]
INTRODUCTION
The design of bus transit system may be considered as a systematic decision process consisting
of five stages: network design, frequency setting, time table development, bus scheduling and
driver scheduling. However, the two most fundamental elements, namely, the design of routes
and setting of frequencies, critically determine the system’s performance from both the operator
and user point of view. Significant savings in resources can be made by reorganization of bus
Proceedings of the Eastern Asia Society for Transportation Studies,
routes and frequency to suit the actual travel demand. In Kidwai (1998) the solution framework
for transit network design consists of three major components, namely, transit route design,
transit assignment and transit scheduling. In this paper transit bus scheduling problem is
formulated and solved in two phases. In the first phase, buses are assigned to individual routes by
an interactive procedure.
REVIEW OF PAST STUDIES
A review of literature reveals various approaches and different computational tools for
scheduling of urban bus transit problem. Lampkin and Saalmans (1967) formulated a constrained
optimization problem for frequency determination. Their objective was to minimize the total
travel time for a given fleet size constraint and a random search procedure was used for solution.
Rea's (1972) model search for an optimum bus network by adjusting iteratively the frequencies
and type of buses on each link to correspond to the link flow level, such that the service on some
links is enhanced whilst on others it is depleted. The optimum situation is reached when no
further change in link service levels is detected. Silman et al. (1974) determined optimum
frequencies for a set of bus routes and fleet size, which could minimize the total travel time and
discomfort (travelling without a seat) by a gradient method procedure. Hsu and Surti (1977) used
the concept of marginal ridership (ridership provided by an additional unit of service frequency)
to determine adequate frequency for each route for a given fleet size.
PROPOSED METHODOLOGY
First general formulation for optimal bus allocation problem is given. In the present methodology
a bi-level optimization is used to solve this problem. In the first level, minimum frequency of
buses (then the number of buses) required on each route with the guarantee of load feasibility is
determined by considering each route individually. Then by summing up the number of buses on
each route fleet size is determined. In second level by taking the fleet size of first level as a lower
bound, the fleet size is again minimized by considering all routes together and using GAs.
Model for Transit Network Assignment
The assignment model is crucial in transit network analysis because it determines the passenger
flows on each links, which are used to calculate various costs and performance measures. This
requires the assignment of passenger demand matrix to the set of routes that define any feasible
transit network configuration. Han and Wilson (1982) used multi-path transit assignment, with
transfer avoidance and/ or minimization acting as the primary choice criterion. Baaj and
Mahmassani (1990) adopted this feature and developed a procedure for transit network analysis,
and a similar procedure is adopted in the present study.
Second Level Optimization
In the first level optimization, the base fleet size has been determined by considering individual
route's capacity and no attempt is made to get the minimum fleet size on global bases (i.e.
considering all the routes together). The reason why one can still reduce the fleet size below the
base fleet size may be attributed to the extensive overlapping of the routes. If there is no
overlapping of the routes, one can't hope to reduce the fleet size below the base value. Though
there are various reasons of, how extensive overlapping of routes may help to reduce the fleet
size, two reasons are discussed below.
GENETIC ALGORITHMS
The idea of genetic algorithms (GAs) was first conceived by Professor John Holland of the
University of Michigan in 1975. Genetic algorithms are computer based search and optimization
algorithms which work on the mechanics of natural genetics and natural selection (Goldberg,
1989). The mechanics of a simple genetic algorithm are simple involving copying strings and
swapping partial strings. The explanation of why this simple process works is subtle yet
powerful. Simplicity of operation and implicit parallelization are two of the main attractions of
the genetic algorithm approach.
Working Principle
GAs begin with a population of string structures created at random. Thereafter, each string in the
population is evaluated. The population is then operated by three main operators - reproduction,
crossovers and mutation - to create a hopefully better population. The population is further
evaluated and tested for termination. If the termination criteria are not met, the population is
again operated by above three operators and evaluated. This procedure is continued until the
termination criteria are met. One cycle of these operators and the evaluation procedure is known
as a generation in GA terminology. Figure 3 illustrates a pseudo code for a simple genetic
algorithm.