Transportation Research Part C 20 (2012) 3–14
Contents lists available at ScienceDirect
Transportation Research Part C journal homepage: www.elsevier.com/locate/trc
Transit network design: A procedure and an application to a large urban area Ernesto Cipriani ⇑, Stefano Gori, Marco Petrelli University of Roma TRE, Civil Engineering Department, 62, Via Vito Volterra, 00146 Rome, Italy
a r t i c l e
i n f o
Keywords: Transit network design Genetic algorithms Flow concentration
a b s t r a c t This paper describes a procedure for solving the bus network design problem and its application in a large urban area (the city of Rome), characterized by: (a) a complex road network topology; (b) a multimodal public transport system (rapid rail transit system, buses and tramways lines); (c) a many-to-many transit demand. The solving procedure consists of a set of heuristics, which includes a first routine for the route generation based on the flow concentration process and a parallel genetic algorithm for finding a suboptimal set of routes with the associated frequencies. The final goal of the research is to develop an operative tool to support the mobility agency of Rome for the bus network design phase. Ó 2010 Elsevier Ltd. All rights reserved.
1. Introduction It is widely recognized that the remarkable increase in traffic congestion, air pollution, energy consumption and road accidents is produced by the large increase of individual car traffic. Such a high social cost can be faced by introducing transport demand management policies aimed at shifting the modal split towards the public transport. This type of transport makes a better use of land, air and energy sources than individual transport mode. Based on such issues, the present paper deals with the bus network design problem in a multimodal transit context. This design problem consists in determining the optimal (or near-optimal) network configuration in terms of bus routes and service frequencies in order to minimize an objective function representing the total costs involved with the transport system. The main novelties of the paper are the introduction of the flow concentration procedure, initially proposed in Carrese and Gori (2002), in a wider route generation process, and the application of the transit network design methodology originally presented in Cipriani et al. (2006) to a large real-life size urban area (Rome), characterized by: (a) a complex road network topology, not simply represented as radial or grid network; (b) a multimodal public transport system (rapid rail transit system, buses and tramways lines); (c) a many-to-many transit demand. The design criteria are chosen in order to develop an intensive rather extensive bus network in order to improve efficiency, integration among direct routes, and effective transfer points that strongly affect service quality and ridership. The basic framework of the procedure is based on two stages: (1) a heuristic algorithm that generates a set of feasible routes and (2) a genetic algorithm that finds the optimal network in terms of routes and their associated frequencies. The paper is structured as follows: a state-of-the-art on transit network design problem is presented in Section 2. Section 3 describes the mathematical formulation of the optimization problem. Section 4 presents the solution procedure. Section 5 presents the results of the application of the procedure to a real-life size network while the last section offers some concluding remarks and possible further research developments. ⇑ Corresponding author. Tel.: +39 0657333406. E-mail address:
[email protected] (E. Cipriani). 0968-090X/$ - see front matter Ó 2010 Elsevier Ltd. All rights reserved. doi:10.1016/j.trc.2010.09.003
4
E. Cipriani et al. / Transportation Research Part C 20 (2012) 3–14
2. State of the art The transit network design is a complex non convex problem (Newell, 1979; Baaj and Mahmassani, 1991). It is usually formulated as a non linear optimization problem with both discrete and continuous variables and constraints. The best and most efficient solution methods are based on heuristic procedures but their applications are mainly limited to test cases or real-life networks of small size. In recent years, the evolution of operational research and the increasing power of computational machines have produced great and renewed interest for this problem. A global review about route design, frequency setting, timetabling of transit lines, and their combination is proposed by Desaulniers and Hickman (2007), Guihaire and Hao (2008), and Kepaptsoglou and Karlaftis (2009). Among the most remarkable works on this matter, we should mention Ceder and Israeli (1993), Baaj and Mahmassani (1995), Carrese and Gori (2002) and Lee and Vuchic (2005). Ceder and Israeli (1993) proposed a transit network design procedure based on a mathematical programming approach. The first step generates a very large set of feasible routes connecting every node to all others. Then, the system creates the minimal sub-sets of routes solving a Set Covering Problem and selects the most suitable sub-set by applying a multi-objective analysis. Baaj and Mahmassani (1995) used an ArtificialIntelligent heuristic algorithm for route generation. This algorithm selects a given number of high-demand node pairs and builds an initial network skeleton by connecting these node pairs through the shortest paths. The skeleton is then progressively expanded to routes according to a node selection strategy that reflects different trade-offs between performance measures and users’ and operators’ costs. Carrese and Gori (2002) proposed a bus network design model for the development of a hierarchical transit system. The design procedure is subdivided in two phases: in the 1st one, the skeleton of the bus network as resulting from a flow concentration process is identified. Then, in the 2nd phase, integrated bus network levels, hierarchically articulated in express, main and feeder lines, are defined. Lee and Vuchic (2005) proposed an iterative procedure that, starting from an initial set of routes composed by the shortest paths for all the origin–destination pairs, tries to improve it by realigning the routes and eliminating the less efficient ones, explicitly taking into account the change of modal split. To our knowledge, many approaches adopted in the literature ignore the multi-objective nature of the problem. Only three contributions face the multi-objective nature of the problem performing a Pareto optimality analysis. Anyhow, such approach is restricted to cases where (a) an optimization procedure, utilizing weights, has been previously executed (Ceder and Israeli, 1993) or (b) a limited number of solutions deriving from a former route generation algorithm has to be evaluated (Baaj and Mahmassani, 1991; Mauttone and Urquhart, 2009). Over the last years, the evolution of operational research and computer technology has produced great and renewed attention for the transit network design problem. New approaches based on metaheuristic techniques (genetic algorithm – GA, Simulated Annealing or Tabu Search) have been frequently applied to solve optimization problems. Due to the discrete nature of several variables of transit design network problem as well as the nonlinearity and the non-convexity of its objective function, probabilistic optimization techniques such as GAs seem to be appropriate. Xiong and Schneider (1993) showed that GA efficiently solves the transport network design problem; Chakroborty (2003) highlighted that in GA-based optimization technique it is possible to include problem-specific information and obtain optimal or near-optimal solutions with low computational effort. Other authors applied GA to solve specific transit network design problems (routing, scheduling, etc.). Specifically, Pattnaik et al. (1998) implemented a two phases procedure for the transit network design. First, a set of feasible routes is generated and then a GA selects the optimal (or near-optimal) routes network. Different coding schemes can be applied to represent the number of network routes by using fixed or variable string length. Dhingra et al. (2000) used GA technique to solve sequentially the routing and scheduling problems by means of two different applications of GAs. Ngamchai and Lovell (2003) proposed new genetic operators specifically designed for the routing problem. Fan and Machemehl (2006) developed a three stages transit network design procedure. First, a set of candidate routes is generated using the shortest paths between pairs of nodes. Then, a network analysis procedure is applied to compute performance measures taking into account transit demand as a variable. At last, a GA is employed to select the optimal set of routes. This paper adopts a design approach analogous to the one proposed by Fusco et al. (2002), Cipriani et al. (2006) and Beltran et al. (2009). Specifically, Fusco et al. (2002) developed a methodology for transit network design for medium size towns that applies several heuristics to individuate a set of reasonable routes and then a genetic algorithm that combines and modifies them in order to find a sub-optimal network of transit services. Cipriani et al. (2006) and Beltran et al. (2009) propose an evolution of previous methodology taking into account the effects that transit supply modifications induce on modal shift. 3. Problem formulation The urban bus network design is formulated as an optimization problem consisting in the minimization of all resources and costs related to the public transport system with fixed demand. The optimization problem is subject to route choice model on transit network as well as to the bus capacity constraints and a set of feasibility constraints on route length and line frequency. The optimization problem can be formally defined as follows:
ð^r ; ^f Þ ¼ arg min z r; f ; qt
ð1Þ
5
E. Cipriani et al. / Transportation Research Part C 20 (2012) 3–14
subject to user equilibrium on transit network
qt ¼ K½C t ðr; f Þ
ð2Þ
as well as to the bus capacity constraints
qhk;i 6 fcmax fi C V
ð3Þ
and a set of feasibility constraints that define both minimum and maximal values for route length and bus frequency
Lmin 6 Li 6 Lmax
ð4Þ
fmin 6 fi 6 fmax
ð5Þ
where the following notations have been introduced: z is the objective function; r is the vector of routes; ^r is the vector of optimal routes; f is the vector of lines frequencies; ^f is the vector of optimal lines frequencies; qt is the equilibrium vector of segment flows on the transit network; K is the user route choice model function; Ct is the vector of path generalized costs on the transit network; qhk,i is the number of transit passengers on segment (hk,i) of line i; fcmax is the maximum load factor; Cv is the vehicle capacity; fi is the frequency of line i and fmin and fmax are its minimum and maximum value; Li is the length of line i and Lmin and Lmax are its minimum and maximum value. The road network is represented with the definition of a unidirectional graph G = (N, E), where N is the set of nodes and E is the set of links representing connections between nodes. A route is a sequence of adjacent nodes in G while a line is specified as a pair (r, f). The public transport supply is represented as a frequency based service. Eq. (2) represents the demand–supply consistency constraints (assignment constraints). Such constraint corresponds to a hyperpath approach for the simulation of user choice behaviour on transit (see Spiess and Florian, 1989). Transit capacity constraints are not considered, as they are included in the heuristic design procedure. The feasibility constraints for route length and line frequency have been introduced. The required frequency of service on the resulting route does not exceed the maximum operationally implementable value because it is impractical to maintain as well as the length does not exceed a maximum allowable value because schedules are too difficult to maintain. Analogously, both frequency and length are not lower than a minimum value because it is not possible to serve a very close OD demand pair with a bus (walking would be a better option and no operator would maintain such a line) or to offer a very low frequency service in an urban context (it would be perceived by users as no service availability). The objective function z is defined as the sum of operator’s costs z1 and users’ costs z2 plus an additional penalty related to the level of unsatisfied demand z3:
zðr; f ; qt Þ ¼ z1 ðr; f Þ þ z2 r; f ; qt þ z3 r; f ; qt
ð6Þ
The transit users’ costs are a weighted sum of in-vehicle travel time, access time, waiting time and a transfer penalty. Transit operator’s costs are computed as a combination of total bus travel distance and total bus travel time. To provide transit services to as many transit users as possible, another additional component is included in the objective function z. This supplementary term represents a penalty that is proportional to the unsatisfied transit demand of the design network. The third term reflects the need to reject the banal solution of minimum cost (‘‘zero users and zero service”). Solutions characterized by large increase of the unsatisfied transit demand are also discarded. Thus, the terms of the objective function z can be written as follows:
0 z1 ¼ W 1 @C km
X
Li fi þ C h
i2Ii
0 z2 ¼ W 2 C u @
X X i2Ii hk;i2Iw;i
z3 ¼ W 3 C u ðpu Du Þ
X X
1 tphk;i fi A
ð7Þ
i2Ii hk;i2Iw;i
tphk;i qhk;i þ
X X i2Ii hk;i2Iw;i
twhk;i qwhk;i þ pt
X n2In
nt n þ
X
1 tahk qahk A
ð8Þ
hk2Ia
ð9Þ
6
E. Cipriani et al. / Transportation Research Part C 20 (2012) 3–14
where Ia, Ii, Iw,i, In are respectively the set of links hk of the road network, the set of the network lines i, the set of the segments (hk,i) of line i and the set of the nodes of the transit network; qwhk,i shows the boarding passengers on segment (hk,i) of line i; tphk,i, twhk,i indicate, respectively, the travel time and the waiting time for segment (hk,i) of line i; ntn is the number of transfers carried out at node n; pt is the time penalty associated to a transfer; qahk shows the pedestrians flow on link hk of the road network; tahk indicates the access travel time on link hk of the road network; pu is the time penalty associated with an unsatisfied transit user; Du is the unsatisfied transit demand; Ckm is the unit cost factor depending on the total bus distance travelled, namely the vehicle operating cost; Ch is the unit cost factor depending on the total time of bus service, namely the travelling personnel’s cost; Cu is the average monetary value of time for the users; W1, W2, W3 is the set of weights that reflect the relative importance that the decision maker assigns to each of the three cost components. The input data are the public transport demand matrix, the characteristics of the road network and the rapid rail transit system, the operating and users’ unit costs. Outputs are bus routes and their frequency as well as the total costs and the vector of flows on the public transport network. Notice that route terminals are not defined as input data but are identified by the model. 4. Solution approach The proposed solution framework consists of two main stages: (a) a heuristic route generation algorithm (HRGA) that generates a large and rational set of feasible routes, by applying different design criteria and practical rules; (b) a genetic algorithm (GA) that finds the optimal network of routes and their frequencies. Of course, given the well-known non-convexity of the problem and the heuristic nature of the method, there is no guarantee that the solution found, indicated as ½^r; ^f in Eq. (1), will be optimal. In other words, the outcome of the heuristic procedure corresponds to a (known) minimum that is local respect to the (unknown) global one. In the first phase of the solution procedure (Stage 1), a heuristic algorithm generates three different and complementary sets of rational and realistic routes (‘‘A”, ‘‘B” and ‘‘C” type routes). This provides a large set of feasible routes that are nevertheless quite diversified among them, because they are built according to different criteria of efficiency and effectiveness (user or operator point of view) and incorporating the professional judgement and practical experience for the route spatial layout (service directness, route length, route duplication, etc.). The A-type routes are composed by direct routes connecting the highest demand node pairs not served by rail system. The B-type routes connect main transit centers (possibly rail stations) and links carrying highest passengers’ volume levels. Finally, C-type routes consist of the routes of the existing bus network. The resulting set of feasible routes is the basin from which the GA select routes to build a network (Stage 2). The design variables are transit routes and the GA is implemented in the C# language as a parallel genetic algorithm (PGA) while the fitness evaluation requires computing, for each solution generated, the three terms of the objective function by simulating the public transport network with the EMME software (EMME User’s manual, 2008). As the performance of the transit system depends on the service frequencies, which should be optimized depending on the passenger volumes, an iterative assignment and frequency setting procedure, first introduced by Baaj and Mahmassani (1992), is applied. Specific details of the solving procedure are reported in Cipriani et al. (2006). 4.1. Heuristic route generation algorithm The first component of the solution framework is the HRGA. Three complementary sets of candidate routes are generated by HRGA applying different design criteria and practical rules. The HRGA is divided into the following five sequential steps: Step 1: Generation of the A-type routes; Step 2: Generation of the B-type routes; Step 3: Storage of the A-type and B-type routes in the overall set of feasible routes in addition to the existing network routes (C-type routes); Step 4: Check of the feasibility constraints (maximum and minimum allowable route length) for all routes stored in the set of feasible routes; Step 5: Save all routes that satisfy the feasibility constraints as input data for the GA.
E. Cipriani et al. / Transportation Research Part C 20 (2012) 3–14
7
The first set of feasible routes is called A-type. The route generation criterion reflects the users’ point of view and is addressed to reduce transfers and develop direct lines; it is composed by the shortest paths connecting the highest demand node pairs not served by the rail rapid transit system. For this reason, the transit demand matrix is simplified by erasing: (1) all trips mainly occurring on the rapid rail system according to a prefixed percentage level with respect to the total trip distance and (2) all trips characterized by a trip distance lower than a prefixed value. This last operation is also implemented to reduce the generation of significant overlapping routes. Main steps of A-type route generation algorithm are sketched in Fig. 1. The second set of feasible routes is based on a completely different approach, which aims at improving the network efficiency and developing a coordinated intermodal public transport network. The design strategy seeks to reduce unused capacity on vehicles and to provide suitable transfer points. From the operator’s point of view, the network composed by this family of routes is more efficient than that composed by all A-type routes. From the user’s point of view, the obvious increase of transfers with respect to the A-type routes should be balanced by some positive expected aspects, as higher frequencies on the main routes due to the demand aggregation process as well as simpler use and easier learning of the network topology, especially for the occasional traveller. With respect to the method originally proposed in Cipriani et al. (2006) and in Beltran et al. (2009), the generation of the second set of feasible routes is transformed adopting the flow concentration procedure initially presented in Carrese and Gori (2002). Specifically, the generation of B-type routes is organized in two steps: identification of the skeleton of the bus network; generation of the routes of the bus network. The skeleton construction algorithm consists of an iterative All-or-Nothing (A/N) demand assignments (see Ortuzar and Willumsen, 1996) procedure on the road network available for buses. At each iteration, the link travel speed is modified according to the level of link passengers volumes thus promoting demand aggregation on certain links. In this way, it is possible to exploit the peculiarities of the public transport supply function where the Level of Service increases as the demand level increases. This is due to the decrease in headways required to satisfy a growing demand and to the opportunity of using public transport systems with higher performances (see Fig. 2). The flow chart of the procedure for the skeleton definition is shown in Fig. 3. Starting from this skeleton, the routes are defined using a link selection and insertion strategy based on a link’s passengers volume. The routes construction algorithm exploits the information about the flow concentration process and, at each step, performs a specific analysis of the link flows provided by the previous step. The routes generation process is divided into the following three sequential steps: Step 1: Identification of the starting points of the routes; Step 2: Selection of the first link of the routes; Step 3: Expansion of the routes. Starting points of the routes can be: (a) directly identified by the designer according to the characteristics of the existing network in terms of main transit centers or main stations of the rapid rail transit system and (b) automatically identified as link with the highest passengers volume on the basis of the results of flow concentration process. The construction of the
Fig. 1. A-type routes generation.
8
E. Cipriani et al. / Transportation Research Part C 20 (2012) 3–14
Fig. 2. Flow-speed design function.
Fig. 3. Procedure for the definition of the network skeleton.
routes starts, for each identified starting point, by selecting the entering links having the highest link volume. The selected link represents the first item of the generic route i. The route is then expanded by inserting other links starting from the node just reached by the route. The algorithm selects the entering link having the highest volume and, if some constraints for link insertion are satisfied, adds it to the route. The process is then repeated from the end node of the new link. During the procedure, the passengers volumes which are served are deleted. The constraints for link insertion consist of the following conditions: (1) the link volume is larger than a prefixed threshold (Vmin); (2) every node of the route is strictly closer to the destination terminal than the preceding one. This rule is adopted to avoid generating loops or too longer routes with respect to the shortest paths between terminals. After a route has been generated, the link selection from the same destination terminal and/or an intermediate reached node is extended to the remaining entering links. Among those links obeying the insertion rules, the one with the maximum volume is selected and the route generation procedure restarts.
E. Cipriani et al. / Transportation Research Part C 20 (2012) 3–14
9
At the end of A-type and B-type routes generation, all routes generated with the addition of the existing network routes set (C-type routes) are checked to verify if feasibility route constraints are satisfied. In particular, the constraints concerning the maximum and minimum allowable route lengths are investigated. If the constraints are satisfied the routes are stored in the set of feasible routes as input data for the second phase of the solution framework. 4.2. Application of genetic algorithms The second stage of the solution framework is characterized by the use of the genetic algorithm (GA) to find the optimal sub-set of routes and their frequencies. Genetic Algorithms are stochastic optimization algorithms founded on the applications of concepts of natural selection and natural genetics (Goldberg, 1989) and have been used in recent years to solve many optimization problems. The transition scheme of GA simulates the natural evolution of a population and investigates the solution space by applying a probabilistic search process to all the individuals representing a population of solutions simultaneously. In general, the ‘‘best” individuals of any population of solutions tend to reproduce themselves and survive to the next generation, thus improving successive generations. GAs explore all regions of the solution space by applying genetic operators (mutation, crossover, selection and elitism) that simulate the reproduction of individuals in the population. Crossover takes a pair of individuals and generates two new individuals (their offsprings) by combining their chromosomes’ sets. Mutation provides a probabilistic modification of the chromosomes that may alter the reproduction process. Elitism is used to save the few best individuals that tend to reproduce and survive to the next iteration, thus improving successive generations. In our application (Section 5), resulting from the HRGA procedure are about 500 ‘‘A”, ‘‘B” and ‘‘C” type routes. The set containing these routes is the basin from which the GA picks to build up a network; for example, in case of 40 lines networks, the initial population of GA is composed by 50 networks (individuals); any network is composed by 40 lines (chromosomes) randomly picked from the basin containing the 500 lines. Any route is identified by a code (line number); any network is represented as a string (in this example, 40 characters long). For any individual (network) the objective function value is computed. Then, a linear fitness scaling is performed in order to convert the raw objective function scores to values ranging in an interval suitable for the roulette wheel selection that has been implemented in the present algorithm. Once two parents have been selected, the crossover operator randomly selects half of the chromosomes from the first parent and half from the second one, and combines the selected chromosomes to generate the offspring. Mutation operator replaces, with a mutation probability equal to 1.5%, each chromosome of the individual with a new chromosome (line) chosen randomly from the basin. Reproduction options that have been utilized to create the next generation are: elitism fraction equal to 10%; crossover fraction, other than elite fraction, equal to 85%; mutation fraction equal to 15%. The final version of the algorithm is implemented as a parallel genetic algorithm (PGA) to take advantage of the available technology of modern computers with a dual-core processor and to maximize the exploration capacity of the solution space. The PGA utilizes two GAs working in parallel and is based on the following steps, depicted in Fig. 4:
Fig. 4. Parallel genetic algorithm (PGA).
10
E. Cipriani et al. / Transportation Research Part C 20 (2012) 3–14
(a) initialize the population by randomly selecting a set of m individuals (i.e.: a set of transit networks), whose chromosomes identify the routes of the network. This operation is performed for each algorithm; (b) parallel execution of two GAs creating next generations; (c) merging of the two populations (Union) and generation of a new starting population composed by the best individuals selected ranking the merged populations (Classification); (d) return to step (b) or stop, if a fixed number of iterations is reached. The PGA has been implemented in the C# language; the Emme scripting language is used to perform transit assignments required for the evaluation of the objective function. The whole design procedure has been realized as a tool whose graphic user interface (GUI) is showed in Fig. 5. This tool helps transport planners offering a very easy way to set the input data, such as the parameters of genetic operators and the weights of the objective function. The fitness evaluation requires computing, for each solution generated, the three components of the objective function by simulating the public transport network. As the performance of the transit system depends on the service frequencies, which should be optimized depending on the passenger volumes, an iterative assignment and frequency setting procedure, first introduced by Baaj and Mahmassani (1992), is applied. The procedure, depicted in Fig. 6, consists of an iterative process between the transit demand assignment and the route frequency setting equation:
fi ¼
qhk;i;max fcmax C V
ð10Þ
where qhk,i,max is the maximum segment volume of line i as resulting from the assignment. The procedure stops when the maximum difference among route frequencies in two consecutive iterations is lower than a given threshold. The convergence of the iterative frequency setting procedure is not guaranteed, but all computational tests performed converged in few iterations. 5. Real size test network application The proposed procedure has been implemented on a large sized real-life network (the urban area of Rome), in order to compare its effectiveness versus the performance of the existing transit network. The study area is subdivided in 450 traffic
Fig. 5. Graphical user interface for the PGA tool.
E. Cipriani et al. / Transportation Research Part C 20 (2012) 3–14
Assign initial frequencies
11
For each route
Hyperpaths transit demand assignment
Determine route frequency For each route
No Verify frequency convergence Yes End procedure Fig. 6. Assignment and frequency setting procedure.
zones. The road network is composed of more than 1300 nodes and 7000 unidirectional links. The existing transit network is composed of more than 200 bus lines, with many overlapping routes and not very high frequencies (average lines headway is about 15 min), and of two subway rail lines. The potential transit demand, including components of the car demand, amounts to about 230,000 trips in the morning peak hour. The HRGA has allowed the identification of a set of feasible routes composed by more than 500 elements (100 A-type routes, 338 B-type routes and 99 C-type routes). Short preliminary tests have been performed to calibrate the parameters of the algorithm: best performances have been obtained by adopting a crossover probability equal to 0.5, a mutation probability equal to 0.015, and a population composed by 50 individuals. After these first tests, the PGA has been used to evaluate: (a) the sensibility of the solution search process to the weights adopted in the objective function and (b) the best network configuration varying the number of bus lines (from 40 to 160). Each term of the objective function has been computed according to the combination of weights used to: (1) make the objective function terms homogeneous and (2) reflect the trade-offs between different subjects involved (users, operators, and public administration). Such weights have been calibrated applying a detailed and exhaustive sensitivity analysis that has allowed to underline some important aspects (Cipriani et al., 2008): high sensitivity of identified solutions with respect to the changes of operator’s cost weights (value adopted equal to 2); low sensitivity of identified solutions when using high values for the transfers’ penalty weight (value adopted equal to 0.4); high values of access time weight (value adopted equal to 0.1) with respect to other users cost components are needed to avoid underestimation of the disutility related to this trip phase; low variance of the waiting and in-vehicle travel times with respect to the change of their associated weights (values adopted equal to 0.04 and 0.02, respectively). PGA was run on a PC Pentium 4 with a 2.8 Ghz processor and 1 GB of RAM for a computation time of about 12 h for 250 iterations. Such computation time depends on the number of iterations needed for the GA to obtain a significant reduction of the objective function when executed in parallel (otherwise, about a double number of iterations is needed) and with a basin where to pick from containing selected (‘‘A”, ‘‘B” and ‘‘C” type) routes (otherwise, much longer computational times are needed). Tables 1 and 2 summarize the results obtained by applying the PGA to design different networks varying the number of bus lines. Table 1 shows the values of the different terms of the objective function, while Table 2 provides the comparison among these solutions in terms of percentage differences calculated with respect to the design network with 160 bus lines. As it can be seen, the best result in terms of objective function value is associated with the network with 130 bus lines. Moreover, it is important to highlight that, regardless of the number of lines of the transit network, the procedure provides comparable and satisfactory results for all the generated solutions. As shown in Table 2, the changes of the components vary in a very limited range with the exception of the operator costs (vehicles-km) and the unsatisfied demand for the solutions with small number of lines (from 40 to 70). In fact, the first term decreases with the reduction of the number of lines composing the network (35% for the 40 bus lines network with respect to the 160 lines network) while the second term presents a significant increase (about 20%) only for the 40 and 55 lines networks. Remaining terms of the objective function indicate that design networks with few lines highly rely on rapid rail system.
12
E. Cipriani et al. / Transportation Research Part C 20 (2012) 3–14
Table 1 Objective function terms for the different design networks. Number of lines (n)
Objective funcion value
Vehicles-km (n)
Transfers (n)
In-vehicle time (h)
Access time* (h)
Waiting time (h)
Unsatisfied demand (n)
40 55 70 85 100 115 130 145 160
984,259 977,756 971,163 963,474 961,298 958,158 956,223 962,394 966,453
11,583 12,349 14,854 15,027 16,110 16,485 16,818 17,448 17,920
322,615 328,981 329,602 332,682 331,992 333,761 329,108 329,433 332,112
81,670 82,206 82,478 83,281 83,980 84,135 82,849 83,943 84,121
103,419 101,233 99,122 97,410 96,182 95,450 95,773 95,859 95,673
22,766 22,823 22,297 22,242 22,375 22,236 22,295 21,962 21,783
6950 6874 5703 5802 5742 5475 5044 5434 5734
*
Access time includes access/egress time from/to centroids which is fixed and is equal for any zone.
Table 2 Objective function terms: comparison among different design networks with respect to ‘‘160 bus lines” design network. Number of lines (n)
Operator costs (%)
Transfers (%)
In-vehicle time (%)
Access time (%)
Waiting time (%)
Unsatisfied demand (%)
40 55 70 85 100 115 130 145 160
35 31 17 16 10 8 6 3 0
3 1 1 0 0 0 1 1 0
3 2 2 1 0 0 2 0 0
8 6 4 2 1 0 0 0 0
5 5 2 2 3 2 2 1 0
21 20 1 1 0 5 12 5 0
Table 3 Performance comparison between existing and best design networks.
Existing(A) Design (B) Design (C) Diff. B–A (%) Diff. C–A (%) *
Number of lines (n)
Objective Funcion value
Vehicles, km (n)
Transfers (n)
In-vehicle time (h)
Access time* (h)
Waiting time (h)
Unsatisfied demand (n)
214 85 130 60.3
1102,602 963,474 956,223 12.6
18,912 15,027 16,818 20.5
320,817 332,682 329,108 +3.7
99,906 83,281 82,849 16.6
101,656 97,410 95,773 4.2
33,131 22,242 22,295 32.9
14,206 5802 5044 59.2
39.3
13.3
11.1
2.6
17.1
5.8
32.7
64.5
Access time includes access/egress time from/to centroids which is fixed and is equal for any zone.
The comparison (see Table 3) between the existing network and the two best design networks (85 and 130 lines networks), shows that Rome transit demand can be served effectively (reduction of 30% of the waiting time) by a bus network composed by a lower number of lines (reduction of more than 50%) in a more efficient way (reduction of 20% of the operating costs), while still guaranteeing the same service area coverage as the current system. It is important to underline as well that the design network provides significant improvements with respect to the existing in terms of in-vehicle time (reduction equal to about 16%) due to the increase of direct lines. A small reduction is recorded for the number of transfers. This occurrence is related to the completely different nature of the two networks: the design network is a hierarchical high frequency network strongly integrated with the rapid rail system; while the existing network is characterized by spread low frequency services. Detailed comparison between the existing and the ‘‘85 lines” design network in terms of line frequency are reported in Table 4. It is possible to see, as expected, that the intensive design network is mostly composed by high frequency lines Table 4 Classification of actual and 85 lines design network in terms of headway.
Existing (A) Design (B)
Number of lines (n)
Headway 6 4 min (% veh-km)
4 min < Headway 6 10 min (% veh-km)
10 min < Headway 6 20 min (% veh-km)
20 min < Headway 6 30 min (% veh-km)
Headway > 30 min (% veh-km)
214 85
1 (3%) 40 (75%)
68 (57%) 20 (18%)
91 (30%) 9 (5%)
35 (8%) 5 (1%)
19 (2%) 13 (1%)
E. Cipriani et al. / Transportation Research Part C 20 (2012) 3–14
13
(headway equal to 10 min or less) involving highly concentrated transit supply with more than 90% of total amount of vehicles-km spent on these lines. Significant changes are recorded with respect to the existing network where the vehicleskm used for high frequency lines are less than 60% of the total amount and the number of lines with low frequency is greater than 100. The ‘‘85 lines” design network is composed by a combination of A-type routes (21 lines and 33% of vehicles-km), B-type routes (42 lines and 32% of vehicles-km) and C-type routes (the remaining 22 lines and 34% of vehicles-km). These results support the choice of using the HRGA with different generation criteria to define the set of feasible routes as input to the PGA. It is also important to remember that the design network has also been evaluated in terms of modal split that is currently under investigation by ATAC, the mobility agency of Rome, for the implementation of the design network; this process, external to the design procedure, shows an increase of the transit demand of about 2.5%. 6. Conclusions and further developments In this paper, authors propose a procedure for solving the bus network design problem in a large urban area characterized by a multimodal transit system. The solving procedure consists of a set of heuristics, which includes a first routine for route generation based on the flow concentration process and a parallel genetic algorithm for finding a optimal or near-optimal network of routes with the associated frequencies. Main novelties introduced by this paper are the adoption of a flow concentration procedure in a wider route generation process and the application of the transit network design methodology to a large real-life urban area (the city of Rome), characterized by: (a) a complex road network topology, not simply represented as radial or grid network; (b) a multimodal public transport system (rapid rail transit system, buses and tramways lines); (c) a many-to-many transit demand. The application of various generation criteria in the HRGA has led to a consistent, diversified and exhaustive set of feasible routes. The implemented parallel genetic algorithm has proved to be robust and effective in producing reasonable solutions. Numerical experiments carried out on network of the city of Rome highlighted that transit demand can be served effectively (reduction of 30% of waiting time) by a bus network composed by a lower number of lines (reduction of 50%) in a more efficient way (reduction of 20% of the operating costs), while still guaranteeing the same service area coverage as the current system. ATAC, the mobility agency of Rome, has started the implementation of the ‘‘85 lines” design network; this process, external to the design procedure, shows an increase of the transit demand of about 2.5%. Further developments will be focused on supplementary analysis for the definition of feasible routes and suitable transfer points represent basic issues to be considered. Additional effort has to be spent in the specification of the objective function in terms of components and weights to improve the effectiveness of the procedure by the transportation point of view. Additional refinements and improvements of PGA efficiency or the use of other metaheuristics techniques are necessary for the reduction of computational times. References Baaj, M.H., Mahmassani, H.S., 1991. An AI-based approach for transit route system planning and design. Journal of Advanced Transportation 25 (2), 187– 210. Baaj, M.H., Mahmassani, H.S., 1992. TRUST: a LISP program for the analysis of transit route configurations. Transportation Research Record 1283, 125–135. Baaj, M.H., Mahmassani, H.S., 1995. Hybrid route generation heuristic algorithm for the design of transit networks. Transportation Research Part C 3, 31–50. Beltran, B., Carrese, S., Cipriani, E., Petrelli, M., 2009. Transit network design with allocation of green vehicles: a genetic algorithm approach. Transportation Research Part C 17C (5), 475–483. Carrese, S., Gori, S., 2002. An urban bus network design procedure. Applied Optimization 64, 177–196. Ceder, A., Israeli, Y., 1993. Design and evaluation of transit routes in urban networks. In: Proceedings of the 3rd International Conference on Competition and Ownership in Surface Passenger Transport, Ontario, Canada. Chakroborty, P., 2003. Genetic algorithms for optimal urban transit network design. Computer-Aided Civil and Infrastructure Engineering 18, 184–200. Cipriani, E., Fusco, G., Petrelli, M., 2006. A multimodal transit network design procedure for urban areas. Journal of Advances in Transportation Studies, Section A 10, 5–20. Cipriani, E., Fusco, G., Petrelli, M., 2008. Transit network design in large urban areas. ‘‘Transportation decision making: issues, tools, models and case studies”, November 13th–14th, 2008, Venice, Italy. Desaulniers, G., Hickman, M., 2007. Public transit. Handbooks in Operation Research and Management Science, 69–120. Dhingra, S.L., Muralidhar, S., Krishna Rao, K.V., 2000. Public transport routing and scheduling using genetic algorithms. In: Proceedings Presented at the CASPT 8th International Conference, Berlin, Germany. INRO Consultants Inc., EMME User’s Manual, Montreal, Quebec, 2008. Fan, W., Machemehl, R.B., 2006. Optimal transit route network design problem with variable transit demand: genetic algorithm approach. Journal of Transportation Engineering 132 (1), 40–51. Fusco, G., Gori, S., Petrelli, M., 2002. A heuristic transit network design algorithm for medium size towns. In: Proceedings of 9th Euro Working Group on Transportation, Bari, Italy, pp. 652–656. Goldberg, D.E., 1989. Genetic Algorithms in Search, Optimization and Machine Learning. Addison-Wesley, Reading, Mass. Guihaire, V., Hao, J., 2008. Transit network design and scheduling: a global review. Transportation Research Part A 42, 1251–1273. Kepaptsoglou, K., Karlaftis, M., 2009. Transit route network design problem: review. Journal of Transportation Engineering 135 (8), 491–505. Lee, Y., Vuchic, V.R., 2005. Transit network design with variable demand. Journal of Transportation Engineering 131 (1), 1–10. Mauttone, A., Urquhart, M.E., 2009. A route set construction algorithm for the transit network design problem. Computer & Operations Research 36, 2440– 2449. Newell, G., 1979. Some issue relating to the optimal design of bus lines. Transportation Science 13 (1), 20–35. Ngamchai, S., Lovell, D.J., 2003. Optimal time transfer in bus transit route network design using a genetic algorithm. Journal of Transportation Engineering 129 (5), 510–521.
14
E. Cipriani et al. / Transportation Research Part C 20 (2012) 3–14
Ortuzar, J.D., Willumsen, L., 1996. Modelling transport. Wiley, New York. Pattnaik, S.B., Mohan, S., Tom, V.M., 1998. Urban bus transit network design using genetic algorithm. Journal of Transportation Engineering 124 (4), 368– 375. Spiess, H., Florian, M., 1989. Optimal strategies: a new assignment model for transit networks. Transportation Research Part B 23 (2), 83–102. Xiong, Y.E., Schneider, J.B., 1993. Transportation network design using a cumulative genetic algorithm and neural network. Transportation Research Record 1364, 37–44.
