Optimal Routing Design for

Shuttle Bus Service

Shai Jerby and Avishai Ceder

A growing concern for public transit is its inability to encourage people In contrast, designers using the operations research approach input
to switch their mode of transportation from solo to shared driving. For a demand matrix into the model and receive a route network as out-
example, most people arrive at rail stations via private cars; this creates put. These models are based on a combinatorial problem being solved
traffic congestion and parking overloading in station areas. As a means via methods such as linear or integer programming while defined
of overcoming this problem, automated methods for designing circu- constraints are taken into consideration. The method of operation is
lated (shuttle, feeder) bus routes were developed. The problem input usually based on the definition of an initial feasible network, fol-
comprised an urban network with trip generation links and a single des- lowed by implementation of heuristic procedures for route improve-
tination (main) node, average travel time between each link to the main ment and examination up to a local optimum (6–9). Marwah et al.
node, and a constraint defining the maximal travel time along the route. (10) presented heuristic algorithms for route constructing based on
The research components were threefold: (a) a method for estimating controlled extensions of the shortest-path routes between various
potential passenger demand for a circulated (shuttle) bus route, (b) an origin–destination couplings. Hasselstrom (11) focused on a reduced
operations research model focusing on optimal route design, and (c) a network in which he defined a wide set of possible routes between
heuristic algorithm designed to account for road networks of all sizes. demand centers according to route-length minimum and maximum
The optimal model and its heuristic alternative were compared in dif- constraints. From this set, he chose the best routes according to an
ferent scenarios on a small real-life road network. It was shown that the
objective function of minimum transfers. Ceder and Israeli (12) cal-
heuristic algorithm indeed provides good (optimal in the test case) results.
culated all possible routes and transfers connecting each node with
The heuristic procedure was also implemented with medium and large
all others. They then created a set of alternative route networks and
networks, generated randomly, and found to provide good results
selected the most suitable one by solving a multi-objective opti-
within a reasonable running time.
mization problem based on a combination of passenger and operator
considerations.
Designing optimal public transit routes is a complex undertaking It has been noted that operations research models for public tran-
that has attracted the attention of both researchers and practitioners. sit system optimization often do not emphasize geographic fea-
Most previous researchers have addressed the issue using operations tures sufficiently and tend to simplify them into schematic network
research models. However, problems associated with public transit structures. Recent research has placed greater emphasis on optimiz-
exist in a dynamic urban environment, which makes it difficult to ing public transit networks and adjusting them to urban dynamics
define an optimal route given the numerous factors influencing effi- (13, 14). Ramirez and Seneviratne (15) proposed using a geographic
ciency and functioning. Therefore, in practice, route design is usu- information system to plan public transit routes in an urban network.
ally the responsibility of experienced practitioners or urban planners. The research method was simple: On the basis of demand and travel
There is little evidence of efforts to combine operations research distance data existing in the system, these researchers selected the
tools with urban planning considerations. road links in which demand potential was high and then connected
Urban planning researchers (1–3) have offered a number of ideas the links according to the shortest possible routes. In this manner, it
and approaches for dealing with the complexity of integrating an effi- is apparently possible to integrate the maximum response to a demand
cient public transit system into a dynamic urban environment. How- and the need for a route of a reasonable length. Still, this research
ever, these approaches often do not take into account detailed planning does not provide an answer to the problem of selecting the best
and optimization considerations. Even when they do, they are often routes; rather, it leaves the issue to the planner’s discretion accord-
based on simulation models (4, 5). In these models, the question is ing to a trial-and-error approach. The authors further mentioned
how to distribute a given level of demand over a given network of that the shortest routes between demand centers are not always
routes. The nature of the network to be fed into the model remains efficient in terms of demand coverage. In summary, there are two
open to different planning variations according to the planner’s sub- streams of works concerning transit route design: (a) algorithmic
jectivity, and thus there is no certainty that the proposed network is approaches using optimization criteria and excluding urban planning
the optimal (or even nearly optimal) one. considerations and (b) urban planning models excluding efficiency
(optimization) perspectives.
Use of heuristics is inevitable in the models just mentioned as a
Transportation Research Institute, Civil and Environmental Engineering Faculty, result of their high level of complexity. Malucelli et al. (16) noted that
Technion-Israel Institute of Technology, Haifa 32000, Israel. heuristics might be required even when one is addressing the sim-
Transportation Research Record: Journal of the Transportation Research Board,
plest version of the model: the single-vehicle, single-line case. The
No. 1971, Transportation Research Board of the National Academies, Washington, present research focused on such a problem, developing a method for
D.C., 2006, pp. 14–22. the automatic design of a circulated (shuttle, feeder) bus route. The

14
Jerby and Ceder 15

route aimed at collecting passengers from different origins in an urban URBAN ENVIRONMENT BASE ROAD NETWORK
network, transporting them to a predefined destination point (e.g., rail-
way station), and then distributing them from that central point to var- Stage 1. Creating a Base Network
ious other destinations. To ensure an adequate level of service, trip
times were required to comply with predefined time constraints. The first stage in the process of route design is to scan the urban street
The research methodology relied primarily on operations research network input and filter out all links that will not be used for the pas-
techniques implemented within an urban planning environment. sage of buses. Such actions will result in determinations of more
reduced road networks (base networks) to be used for public transit,
in addition to—or separately from—regular traffic. Working with a
METHODOLOGY AND SCOPE base network allows the planner to reduce the complexity of the prob-
lem and enables the transit agency and passengers to rely on a simpler
In this work, the transit authority’s goal of maximum response to network that is easier to understand and operate.
demand, passengers’ goal of minimum walking distances, and the The aspects considered in the network reduction process are street
transit agency’s constraints regarding maximum route length were characteristics (width, slope, parking arrangements), spacing between
combined. Integration of these goals and constraints can be expressed parallel streets, safety considerations, and any other criteria accord-
in the following problem definition: Given an urban network, a circu- ing to the transit agency’s constraints on a case-by-case basis. The
lar route should be designed to maximally cover passenger potential outcome is a base network that forms the input for the short-term and
from various network demand centers to a transportation center, with long-term planning process.
travel time along the route not exceeding a certain threshold value.
Generally, an objective function with a goal of maximum cover-
age should create a long and winding route; however, in this case a Stage 2. Determining Average Travel
route-time constraint is in place in which timetables must be met and Time Values
an adequate level of service maintained. In addition, this constraint
does not allow the feeder route to cover all demand centers. The pres- After creation of the base network, the travel time in each network link
should be determined. This value can be calculated by direct mea-
ent research goal was to develop a model, or computerized algorithm,
surement or according to the length of the link and the average travel
that would enable the automatic design (at a reasonable running
speed. Average travel speeds vary according to levels of congestion
time) of an optimal circular route in an urban environment for a large
in the link and time of day. When a road link is exclusively allocated
number of examples.
for public transit, travel speeds uninfluenced by congestion can be
The problem input comprised an urban network with trip genera-
assumed. In the present framework, average travel times, without
tion nodes and a single destination (main) node, an average travel
distribution, were input into the model.
time vector between each segment in the network to the main node,
and a constraint defining the maximal travel time along the route. It
was assumed that the transit vehicle would travel in a designated lane
and hence would not be part of any traffic congestion. Therefore, Stage 3. Determining the Service Area
only average travel time was considered (deterministically), without Next, the “service area” that can be served reasonably with a single
its statistical characteristics such as variance. circular route should be defined. The size of the service area depends
The methodology was based on a modular approach allowing the on route travel time constraints (i.e., links that cannot be covered in
complex problem under examination to be partitioned into a chain the framework of time allocated for the travel should be eliminated
of subproblems. Each subproblem can be referred to as an indepen- from the base network). The proposed process includes testing each
dent component. The approach involves the stages shown in Figure 1. of the base network links to determine whether a circular route can
The first stage includes characterization of urban network attrib- be created from the link to the transportation center and back while
utes for deriving a base network for route design. The second stage complying with time constraints. Should the duration of the shortest
involves insertion of average travel times to the links of the road net- route (in travel time values) from the link to the transportation cen-
work, and the service area is defined in the third stage. The fourth stage ter and back exceed the time constraint, the link should be eliminated
focuses on a method for estimating potential demand for trips on a from the network. Applying this procedure to all of the links of the
designed bus (shuttle) route. base network will result in further reductions in the network and
A potential demand measure for each link on the road network, elimination of distant links that should not have been taken into
based on urban and spatial criteria, is developed through the use of consideration at any point.
density and walking distance parameters. This measure is used as
an input to an integer programming model developed in the fifth
stage. The model enables the automated design of an optimal circu- Stage 4. Determining Priority Indexes
lar route complying with a given total travel time constraint. Test Based on Potential Demand
runs using the operations research model are performed in the sixth
stage, which shows whether the complexity level is too high for the The goal of this stage is to determine potential public transit demand
model to be used efficiently with medium-sized and large networks. from every link of the urban network to the transportation center.
In the seventh stage, if necessary, an alternative heuristic algorithm This assessment is made on the basis of spatial data from the urban
is developed and proposed. This algorithm enables the automatic network, and it is subject to a number of assumptions (as detailed sub-
design of circular routes intended to ensure good (but not always sequently). Next, a “priority index” is calculated for each network
optimal) results. The eighth stage examines the heuristic algorithm link; this index reflects the extent to which inclusion of the link in a
with different networks. future route would be profitable. The demand estimation method
16 Transportation Research Record 1971

Input Component Output

Urban planning framework

Urban street Stage one – reducing to Base network
network basic network

Average travel Stage two – insert of Base network with

speeds travel times to the links travel times
network

Constraint of
Stage three – definition Base network in the
maximum travel
of service area framework of a defined
time
service area

Assumptions as to Network with time

network demands Stage four – determining values and demand
and walking demand indexes potential at every link,
distances forming a planning
model input

Analytical framework

Problem definition Stage five – formulating Optimal model

an optimal model

Sample networks Stage six – testing the Identifying the model’s

of different sizes model strengths and
weaknesses

Heuristic Stage seven – developing Heuristic principles

algorithm a heuristic algorithm

Identifying the
Sample networks Stage eight – testing the
algorithm’s strengths
of different sizes algorithm
and weaknesses

Result: a computerized
method of planning a
circular public
transportation route

FIGURE 1 Solution methodology for public transit route design problem.

comprises two stages: calculation of average walking distance per link areas for pedestrians, in the case study area of downtown Haifa, as
and assessment of demand potential according to walking distances. polygons on the base network. This case refers to a catchment area
of 300 m from each side of the route. Determination in this case stems
from what seems to be poor-level passability for pedestrians in view
Calculating Average Walking Distance per Link of the regional slopes and the large number of road links scattered in
a small area.
The first stage refers to the maximum walking distance of potential Examination of Figure 2 shows areas where overlapping is cre-
passengers to the public transit route. This variable, which is subject ated between two or more polygons. In these cases, every point in the
to policy decisions, is known in the literature as “catchment area.” overlapping area is attributed to the nearest link. This is based on
It is customary to assume areas of up to 400 m from each side of the the assumption that passengers will choose the road link nearest to
road link (3), although under certain conditions some passengers the origin point as the waiting point and will walk there via the short-
will be willing to walk a longer distance. [Many studies have demon- est direct distance (e.g., through parks or alleys between houses).
strated the connection between level of service of a public transit route This approach is more realistic than the operations research approach
and maximum distance a passenger is willing to walk to gain access according to which it is assumed that walking is possible only on
to it. Demographic, socioeconomic, weather, environmental, and network links (roads). Average walking distance in the catchment
regional urban design parameters are influences as well. Cervero (17) area, which is influenced by land uses within the area, is calculated
discussed this matter extensively.] Figure 2 presents the catchment according to Equation 1.
Jerby and Ceder 17

Central
railway station

Subway
station

CBD

Bahai
Gardens

0…....200.…..400
meters

FIGURE 2 Catchment areas for network segments in the case study area (CBD  central business
district).

m
popb ∗ wd b less the potential for person-trips originating from the public transit
wd(i , j ) = ∑ (1)
b =1 pop(i , j ) link passing through it.

where On the basis of these assumptions, Equation 2 can be used to

create a demand potential index for each network link.
m = total number of buildings in the catchment area,
b = a certain building in the catchment area between node i pop(i , j )
and node j, and pd(i , j ) = (2)
wd(i , j )
popb = population size (residents, employees) of building b.
The walking distance from building b to the nearest road link is rep- It can be observed that demand potential is in direct proportion
––– to population density and in opposite proportion to average walk-
resented by wdb, whereas pop (i,j) is the population size (e.g., resi-
dents, ing distance. Phrasing the index in this manner combines two plan-
–– employees) of the catchment area. The result of the equation
is wd (i,j), which is the average distance to the road link between node ning goals: “maximum response to demand potential” and “minimum
i and node j from land uses in its catchment area. walking distances.” The result is an index indicating preference for
any (i, j) link over other links in terms of the advisability (from the
perspective of both passenger and operator) of integrating it into
Assessing Demand Potential as Dependent the suggested route. In the later research stages, this index serves
on Walking Distances as a model input and thus assists in the design of a computerized
optimal route.
At this stage, demand potential for trips from a given catchment area The method of operation in this clause has an advantage over
can be assessed. For this purpose, two assumptions are made. typical methods of assessing demand (counting passengers or con-
ducting surveys at transportation centers) in that these methods some-
Assumption 1. When the public transit network in a certain area times involve sample size constraints or problems arising from
operates at a high service level, all persons in the catchment area can questionnaire bias. However, the present method cannot be imple-
be considered potential users, regardless of their socioeconomic level mented without a geographic information layer of high resolution.
or the extent to which they use automobiles. In other words, in such In the case study, the method was implemented with TransCAD to
a situation there is a correlation between building density and demand create bands around each network link. When there were no exact
potential for public transit. data regarding the number of residents on each block, assessments
Assumption 2. The demand for trips from a certain road link were carried out by estimating numbers of building floors, numbers
depends on the walking distances from the land uses around the road of apartments per floor, and approximate household sizes. The
to the road itself. The farther the land uses are from the road link, the model outcome for the sample network is presented in Figure 3.
18 Transportation Research Record 1971

To Tel Aviv Haifa Central railway station To Haifa CBD

1
2,5 6,3
5,3 5,9
Hameginim Ave.
7 2
4,3
3,6
7,2
7,2 3,6

Subway
6,3
Alenby St.
6 3
5,3
5,3
2,4 7,3
2,4 7,3

Hagefen St.
5 4 Links value legend
7,4 t(i,i +1) pd(i,i +1)
Bahai Gardens
5,4
t(i +1,i ) pd(i +1,i )

FIGURE 3 Network model for case study area. First digit indicates average
travel time (in minutes); second digit indicates potential demands (in
passengers).

The assumption here was that demand potential is homogeneously ∑y = ∑y ij ki (i, j ) ∈ r (k,i ) ∈r (5)
distributed along a link. In cases in which road links are not homoge- j k

neous from a demand potential aspect, they can be divided into sep-
arate links via dummy nodes. Instances in which there are one-way S = {s1 , s2 , . . . sM } ∃ sm ∈ N , n1 ∉ sm , sm ≥ 2 (6)
links in the network can be expressed by means of a high time value
for the blocked trip direction. (In principle, it is possible to define a ∑y
i ∈sm , j ∈sm
ij ≤ sm − 1 ∀s m ∈ S lu ∈ L (7)
“mixed graph” [i.e., a graph that includes both directed and non- i ∉Lu , j ∉lu
directed links], but in general complex problems are encountered in
dealing with this type of graph [18].) pd ji = 0.2 ∗ pd ij ∀ (i, j ) ∈ r (8)

⎧⎪ 0 if ( i , j ) ∈ r (i, j ) ∈ A
yij = ⎨ (9)
MODEL AND ALGORITHM ⎪⎩1 if ( i , j ) ∉ r (i, j ) ∈ A
Model Formulation The model is based on a decision variable yij that defines whether
link (i, j) belongs to the route. The objective function (Equation 3)
The model described here produces a circular route, r, that both starts
is aimed at maximizing the demand potential of the route links. This
from an initial node n1 and ends there while covering the maximum
function combines the two objectives of maximizing the number of
potential demand within a travel time of T or less. In other words,
passengers and minimizing walking distances. Equation 4 repre-
the chosen route is the one where the total priority index of its links is
sents the maximum travel time constraints associated with the route.
maximal and the total travel time within these links does not exceed
Equation 5 implements the Euler condition (19) to force the created
the constraint value.
route to be circular. For this purpose, each of the nodes in the subgraph
Graph G(N, A) can be defined as a network of streets in an urban
created by the route should be of dual level. Furthermore, because
area where network nodes are represented by the set N = (1, 2, . . . ,
route links are in the form of a directional graph, the number of incom-
n), and network streets (graph links) can be graphed as A = [(i, j): i,
ing and outgoing links in every node in the subgraph should be equal.
j ∈ N; i ≠ l]. For each of the links i, j ∈ A, a travel time value tij is
Equation 6 defines S as a set of all network node combinations that
defined, as well as a priority index pdij that expresses potential trip
include at least two nodes and do not include node n1. Equation 7
demand:
defines the number of route links connecting the nodes of any sub-
set sm that belongs to S as being smaller than the number of nodes in
max ∑
(i , j ) ∈ r
pd ij yij (3)
that set. Thus, a circular route cannot be built unless it includes the
main node n1. In practice, Equations 5 to 7 require that all chosen
subject to links be connected to one another, thus preventing the formation of
more than one continuous circular route.
∑ty
(i , j ) ∈ r
ij ij ≤T (4) Equation 7 also relates to a situation in which two (or more)
circular routes exist that create overlaps in some of the nodes
Jerby and Ceder 19

(e.g., “8”-shaped routes). To allow for such a situation, L = (l1, l2, ratio, the efficiency criterion can be defined as follows: An efficient
l1, . . . , lU) of all possible one-circle routes passing through node n1 route between two nodes is the shortest one between them from the
is defined, and Constraint 7 (i.e., Equation 7) is in operation for each aspect of the impedance ratio.
set of L routes. In its current formulation, the constraint prevents cre- The proposed algorithm is based on constructing a circular route
ation of additional circular routes detached from the tested lu route from an initial group of links in which potential demand is rela-
but allows subroutes that somewhat overlap with the main route to tively higher in comparison with the remainder of the network. With
be created, such as 1-7-2-3-2-1 in Figure 3. every iteration of the algorithm, a small subgroup of links is selected
According to Equation 8, if the tested link belongs to the route, from the initial link group. The algorithm examines whether it is
then the value of demand potential in the opposite direction is signif- possible to construct an efficient circular route that will pass through
icantly smaller. This condition is reasonable from a practical point the subgroup links and meet the constraint. If a route exists, the algo-
of view given that the same destination is eventually reached on both rithm examines its demand cover value relative to the routes exam-
trip directions. The purpose of this constraint is to prevent the nat- ined to that point and updates the objective function value accordingly.
ural tendency of the model to repeat the same link in both directions, Thereafter, the algorithm continues to examine routes for other sub-
as identified in the initial running of the test, where the demand val- groups. Finally, the algorithm identifies the best circular route found.
ues were identical in both directions. Equation 9 defines decision In the following, the algorithm, which is also shown in Figure 4, is
variable yij, which is in fact the model output. According to the def- described in detail. The algorithm input is a reduced basic urban
inition of this variable, no link can be traveled more than once per network represented by graph G(N, A).
direction. Alternatively, certain network links can be eliminated if
their demand potential is not justifiable.
Theoretically, the model allows optimal routes to be created; Stage 0. Initializing Variables
nevertheless, complexity increases according to the size of network
it is run on. Whereas the number of constraints depending entirely on Substage 0.1. Build an “efficient route matrix” E where each cell
the size of matrix y (i.e., Equations 4 and 8) increases in geometrical contains the most efficient route between two nodes.
progression, and Constraint 5 (Equation 5) relating to a given node Substage 0.2. Define Mpd as the current value of the objective
appears in the model as many times as the number of network nodes, function (maximum potential demand). Set Mpd = 0.
Constraint 7 (Equation 7) increases according to increases in the num- Substage 0.3. Define R as the group of links constituting the
ber of nodes in a manner that cannot be described via a polynomial selected circular route. Set R = {}.
equation, resulting in a high level of complexity. Thus, it can be con- Substage 0.4. Define p as the number of mandatory links in the
cluded that solving the problem on real road networks through an network. Set p = 2.
integer programming model is impractical in the current case. Substage 0.5. Define P as the maximum number of mandatory
This situation requires an examination of heuristic solutions. links in the network. Set P = 4.
There are a number of possible solution directions: Substage 0.6. Define cover coefficient 0 < α < 1. Set α = 0.05.

1. Defining an initial set of demand links and creating the most

worthwhile routes among them, Stage 1. Defining the Main Demand Link
2. Constructing an initial route and then making local improve-
Network (Skeleton Network)
ments,
3. Using a variation of a problem already known in the literature, – –
Define a subset A ⊆ A of  A = α   A size that includes links of the
and highest pdij value.
4. Running the optimal model while eliminating one of the con-
straints and then completing the solution according to a heuristic
method. Stage 2. Testing Different Combinations of
Compulsory Links from the Skeleton Network

Heuristic Algorithm –
Substage 2.1. Choose an arranged combination q ∈ A that contains
p links and has not yet been tested. Construct an efficient circular
In the present framework, an algorithm based on the first option is route r thereof that passes through all p links as well as the main
proposed. The algorithm success index is based on a new criterion
node n1. (Note that for every arranged combination q, only one
for constructing a route, the efficiency criterion. This criterion stems
efficient circular route r at most is possible.)
from the desire to find a route that will provide maximum demand
Substage 2.2. If route r complies with the time constraint, that is,
potential and meet time constraints using simple algorithms based
on the shortest path concept (20, 21). For this purpose, an imped- Σ(i , j )∈r tij ≤ T , move to Substage 2.3; otherwise, move to Substage 2.5.
ance ratio zij should be defined for each network link according to the Substage 2.3. Sum the total demand potential values of the route
following equation: links. Should the route include several passes on the same link, refer
to the demand potential as zero starting from the second pass.
ωtij Substage 2.4. If the total demand in the route links is larger
zij = (10) than the current demand value of the objective function, that is,
λpd ij
Σ(i , j )∈p pd ij ≥ Mpd, substitute R =: r and update the objective function
The impedance ratio grows as the travel time in the link becomes value by Mpd = Σ (i , j )∈r pd ij .
longer and diminishes as the demand potential in the link becomes Substage 2.5. If all possible q-type combinations have been
higher (according to predefined coefficients ωλ). On the basis of this tested, move to Stage 3; otherwise, return to Substage 2.1.
20 Transportation Research Record 1971

Input: Create the group of main demand links

according to the defined demand potential index
a. Basic urban network.
b. “Most Efficient Routes”
matrix between each two
Choose a combination of p
links.
links from the group created and
c. Initial size (p) of a
construct an efficient circular route
mandatory group of links.
that passes through the p
d. Maximal size (P) of the
links and the main node.
mandatory group of links.

Does the tested route No

comply with the time
constraint?

Yes

Is the demand No
potential in the
route the highest
found so far?

Yes

Define the route as optimal among

those already tested

No
Have all the
possible routes for
p been tested?

Yes
No

Does p=P? p=p+1

Yes

Stop

FIGURE 4 Flowchart for heuristic algorithm.

Stage 3. Rechecking with a Larger Group with the heuristic algorithm, to determine whether the same result
of Compulsory Links (route) was produced in both instances. The test was initially per-
formed on the sample network presented in Figure 5 and then on
If p < P, determine p =: p + 1 and return to Stage 1; otherwise, use seven small networks randomly selected by the computer. In Stage 2,
the current Mpd value, and stop. running time was examined; this test was performed on medium-
sized and large networks to assess the algorithm’s applicability to
these networks.
TEST RUNS The small network shown in Figure 3 was used to run both mod-
els and test the heuristic algorithm. The heuristic algorithm created
The algorithm (see Figure 4) was implemented with a Matlab script. the same optimal route output by the model. This result provides an
After completion of encoding, reruns of the computer program were initial indication of the quality of the algorithm. However, to remove
performed to test the algorithm in two stages. In Stage 1, the qual- doubt regarding the possibility that the output route was influenced
ity of the result was examined. This test was carried out with small by the type of network examined, the algorithm was assessed in
networks on which the optimal model was implemented, as well as seven additional test scenarios randomly constructed by the com-
Jerby and Ceder 21

Links value legend

7,6 1 Demand potential – right value
Travel time – left value
9,3

2 1,9 3 5,4 4 3,8 5

2,1 4,9 7,5 1,8

6 7 2,6 8 8,4 9

2,1 4,0 2,2 3,6

10 8,8 11 6,3 12 2,7 13

5,9
5,4 8,10 4,2 1,9

14 3,7 15 6,2 16 6,9 17

5,8
10,9 10,6 8,3

18 2,6 19 10,7 20 5,6 21

1,8
3,2 9,4 5,7

22 8,2 23 1,5 24 9,9 25

FIGURE 5 Real-life network route resulting from heuristic algorithm, given T  100.

puter. The results showed complete overlapping between the heuris- For this purpose, the P value of the algorithm should be changed
tic algorithm and the optimal model in all of these scenarios, indicat- from 4 to 2. This will reduce the ratio between the P value and the
ing that the heuristic algorithm created an optimal route in each of total number of links in the network (A), bringing it closer to the ratio
the seven runs. prevailing when runs are performed on large networks. As a result,
On the basis of the results derived from running the algorithm on it will necessarily decrease the algorithm level of accuracy, probably
the eight tested networks, it can be concluded that the algorithm is to the level prevailing during runs on large networks. Table 1 sum-
sufficiently reliable for testing on real networks. Figure 5 presents marizes the results obtained when the heuristic algorithm was run on
the results obtained when the algorithm was run on a 25-node net- all of the tested networks.
work. It can be seen that the algorithm creates a reasonable route
for a real-life network. However, a check of the complexity of the
algorithm showed that only when the maximum number of com- CONCLUDING REMARKS
pulsory links in the network (P) was four or below could the algo-
rithm function within a reasonable running time. In addition, when This article has described the development of a method for the
the algorithm is run over large networks, the quality of the solution automated design of a circulated (shuttle, feeder) bus route. The
and the extent of its proximity to the optimal situation cannot be route sought to collect passengers from different origins in an
accurately assessed. The only way in which the quality of the urban network, transport them to a predefined destination point,
heuristic algorithm can be assessed is by running it on small net- and then distribute them from that central point to various other
works. Therefore, additional results of runs on small networks are destinations. To ensure an adequate level of service, trip times
presented in which the algorithm method of operation was changed complied with predefined time constraints. The research compo-
slightly so that runs on a small network could simulate those on a nents were threefold: (a) a method for estimating the potential
large network. passenger demand for a bus (shuttle) route, (b) a model for optimal
22 Transportation Research Record 1971

TABLE 1 Summary of Heuristic Algorithm Runs Given Different Networks

P Heuristic Algorithm
Ratio
Network Type No. of Nodes A Optimal Model Result Result

Sample network 7 4/9 26.6 26.6

Small Random Network #1 7 4/9 191 191
Small Random Network #2 7 4/7 208.8 208.8
Small Random Network #3 7 4/7 206.4 206.4
Small Random Network #4 7 4/8 79.2 79.2
Small Random Network #5 7 4/9 338 338
Small Random Network #6 7 4/9 243.6 243.6
Small Random Network #7 8 4/9 204 204
Large random network 25 4/42 Cannot be determined 142.2
within reasonable time
Small random network 25 2/20 107 98.4
simulating a large one, #1
Small random network 7 2/22 276 183
simulating a large one, #2

route design, and (c) a heuristic algorithm for route design for road 7. Silman, L. A., Z. Barzily, and U. Passy. Planning the Route System for
networks of all sizes. Urban Buses. Computers and Operations Research, Vol. 1, 1974,
pp. 201–211.
The optimal model and its heuristic alternative were compared 8. Kuah, G. K., and J. Perl. A Methodology for Feeder-Bus Network
through the use of different scenarios on a small real-life road net- Design. In Transportation Research Record 1120, TRB, National
work. The findings showed that the heuristic algorithm indeed pro- Research Council, Washington, D.C., 1987, pp. 40 –51.
vides good (optimal in the test case) results. The heuristic procedure 9. Dubois, D., G. Bel, and M. Libre. A Set of Methods in Transportation
then was implemented with medium and large networks, generated Network Synthesis and Analysis. Operations Research, Vol. 30, No. 9,
1979, pp. 797–808.
randomly, and found to provide good results within a reasonable 10. Marwah, B. R., F. S. Umrigar, and S. B. Patanik. Optimal Design of Bus
running time. Routes and Frequencies for Ahmedabad. In Transportation Research
The present methodology is based on a modular approach allow- Record 994, TRB, National Research Council, Washington, D.C., 1984,
ing a complex problem to be partitioned into a chain of subproblems. pp. 41–47.
11. Hasselstrom, D. Public Transportation Planning—A Mathematical Pro-
Hence, each subproblem can be referred to as an independent com- gramming Approach. PhD thesis. University of Gothenburg, Gothen-
ponent. This partitioning simplifies the solution effort. The method- burg, Sweden, 1981.
ology proposed here can be implemented within existing transit 12. Ceder, A., and Y. Israeli. Design and Evaluation of Transit Routes in
operation planning procedures. That is, it can be implemented in Urban Networks. Proc., 3rd International Conference on Competition and
designing local urban circular bus routes to feed passengers to railway Ownership in Surface Passenger Transport, Toronto, Ontario, Canada,
1993.
stations and distribute passengers from these stations to the local 13. Chien, S., and P. Schonfeld. Optimization of Grid Transit System in
area. It can also be applied to decisions on where and how to provide Heterogeneous Urban Environment. Journal of Transportation Engi-
preferential treatment for a public transit system. neering, Vol. 123, No. 1, 1997, pp. 28–35.
14. Chien, S., and Z. Yang. Optimal Feeder Bus Routes on Irregular Street
Networks. Journal of Advanced Transportation, Vol. 34, No. 2, 2000,
pp. 213–248.
REFERENCES 15. Ramirez, A., and P. Seneviratne. Transit Route Design Applications
Using GIS. In Transportation Research Record 1557, TRB, National
1. Woyciechowicz, A., and R. Shliselberg. Wayfinding in Public Trans- Research Council, Washington, D.C., 1996, pp. 10–14.
portation. In Transportation Research Record: Journal of the Trans- 16. Malucelli, F., T. G. Crainic, F. Guertin, and M. Nonato. Adaptive Mem-
portation Research Board, No. 1903, Transportation Research Board of ory Programming for a Class of Demand Responsive Transit Systems.
the National Academies, Washington, D.C., 2005, pp. 35–42. In CASPT Lecture Notes in Economics and Mathematical Systems,
2. Cervero, R. The Transit Metropolis: A Global Inquiry. Island Press, Springer-Verlag, Berlin, 2000, pp. 253–273.
Washington, D.C., 1998. 17. Cervero, R. Walk-and-Ride: Factors Influencing Pedestrian Access to
3. van Nes, R., and P. H. L. Bovy. Importance of Objectives in Urban Transit. Journal of Public Transportation, Vol. 3, No. 4, 2001, pp. 1–23.
Transit-Network Design. In Transportation Research Record: Journal 18. Eiselt, H. A., M. Gendreau, and G. Laporte. Link Routing Problems,
of the Transportation Research Board, No. 1735, TRB, National Part I: The Chinese Postman Problem. Operations Research, Vol. 43,
Research Council, Washington, D.C., 2000, pp. 25–34. No. 2, 1995, pp. 231–242.
4. Spiess, H., and M. Florian. Optimal Strategies: A New Assignment 19. Ceder, A. Public Transport Timetabling and Vehicle Scheduling. In
Model for Transit Networks. Transportation Research, Vol. 23B, Advanced Modeling for Transit Operations and Service Planning
No. 2, 1989, pp. 83–102. (W. Lam and M. Bell, eds.), Elsevier Science, New York, 2003, pp. 31–57.
5. Wu, J. H., M. Florian, and P. Marcotte. Transit Equilibrium Assign- 20. Dijkstra, E. W. A Note on Two Problems in Connection with Graphs.
ment: A Model and Solution Algorithms. Transportation Science, Numerische Mathematik, Vol. 1, 1959, pp. 269–271.
Vol. 28, No. 3, 1994, pp. 193–203. 21. Floyd, R. W. Algorithm 97—Shortest Path. Communications of the
6. Lampkin, W., and P. D. Saalmans. The Design of Routes, Service Fre- ACM, Vol. 5, No. 6, 1962, p. 345.
quencies and Schedules for a Municipal Bus Undertaking: A Case
Study. Operations Research, Vol. 18, No. 4, 1967, pp. 375–397. The Bus Transit Systems Committee sponsored publication of this paper.