Capacity Expansion Problem for Large Urban Transportation Networks
Tom V. Mathew1 and Sushant Sharma2
Abstract: A traf?c network design problem attempts to ?nd optimal network expansion policies under budget constraints. This can be formulated as a bilevel optimization problem: the upper level determines the optimal link capacity expansion vector and the lower level determines the link ?ows subject to user equilibrium conditions. The upper level is a capacity expansion problem which minimizes the total system cost and can be solved using any optimization algorithm. In the present study, genetic algorithm ?GA? is used in the upper level because of its modeling simplicity and ability to handle large problems. The proposed model is ?rst applied to a small sized network and then to a medium sized test network and the results are compared with other existing solution approaches. The sensitivity analysis of the model is performed by designing the networks at different demand levels. The resilience of the solution when demand increases the design demand is also carried out. Finally, the network design for the city of Pune, India was taken as a case study. This is a large sized network having 1,131 links and 370 nodes. The capacity expansion is carried out under various budget scenarios and the results are discussed. This study shows the potential of GA to obtain a high quality solution for large network design problems. DOI: 10.1061/?ASCE?0733-947X?2009?135:7?406? CE Database subject headings: Network design; Optimization; Computation; Traf?c assignment; Urban areas; Traf?c capacity.
Downloaded from ascelibrary.org by Columbia University on 12/02/16. Copyright ASCE. For personal use only; all rights reserved.
Introduction
One of the options that strikes transportation engineers and planners, alike, while considering the growth in traf?c demand is to expand the capacity of existing congested links or build new links. Traf?c planners experience a number of constraints, while designing for urban areas. They have to overcome some of the invaluable socio-economic, environmental, budget, and space impediments to further development. The planner has to make a decision while considering, on the one hand, maximization of bene?ts derived and minimization of total system cost under limited budget and on the other hand, behavior of the road users. In such cases, selecting new links and adding capacity to existing links of a network becomes an important problem. This problem is stated as a network design problem ?NDP?. The objective of NDP is to achieve a system optimal solution by choosing optimal decision variables in terms of capacity expansion values. This decision, taken by the planner, affects the route choice behavior of road users and needs to be considered while assigning traf?c to the network. In general, NDP can be formulated as a bilevel problem which has an upper level representing a system optimal design and a lower level representing
1 Associate Professor, Transportation Systems Engineering, Dept. of Civil Engineering, Indian Institute of Technology Bombay, Powai, Mumbai 400 076, India ?corresponding author?. E-mail: vmtom@civil. iitb.ac.in 2 Research Scholar, Transportation Systems Engineering, Dept. of Civil Engineering, Indian Institute of Technology Bombay, Powai, Mumbai 400 076, India. E-mail: sushantsharma@iitb.ac.in Note. This manuscript was submitted on June 15, 2006; approved on December 22, 2008; published online on June 15, 2009. Discussion period open until December 1, 2009; separate discussions must be submitted for individual papers. This paper is part of the Journal of Transportation Engineering, Vol. 135, No. 7, July 1, 2009. ?ASCE, ISSN 0733-947X/2009/7-406–415/$25.00.
travelers route choice behavior. We may classify the lower level problem as the Nash game and whole NDP as the Stackelberg game. In game theory, the Nash equilibrium ?named after John Nash, who proposed it? is a kind of optimal collective strategy in a game involving two or more players, where no player has anything to gain by changing only his or her own strategy ?Fisk 1984?. On the other hand, a Stackelberg game, named after the German economist Heinrich von Stackelberg, is a leader-follower game where the leader takes a move and the follower responds to it ?Lim et al. 2005?. The key assumption is that the leader must have perfect information of the responses of the follower. Although the leader cannot intervene in the follower’s decision, he can modify the follower’s decision for his own advantage. In network design problems, the Nash game refers to the traf?c assignment based on Wardrop’s user equilibrium principle. The Stackelberg game, then, refers to the link expansion decisions where the system designer anticipates the responses of the road users ?Lim et al. 2005?. Network design models that are concerned with adding indivisible facilities ?for example, a lane addition? are said to be discrete NDP, whereas those dealing with divisible capacity enhancements ?for example road widening? are said to be continuous NDP. It should be noted that discrete models can easily allow the investment to signi?cantly affect the mean free speed of proposed links; this seems to be dif?cult in the case of continuous models. Continuous models, on the other hand, have the advantage that the optimal levels of improvement ?with the corresponding investment? for each link is determined by the model. Continuous network design models with convex investment costs usually result in minor increases in practical capacity of many links proposed for the improvement. This may be desirable if the purpose of the model is to improve or maintain the existing transportation network rather than to construct new roads ?Abdulaal and LeBlanc 1979?. In practice, networks used in transportation planning are quite large, and so the continuous network design
406 / JOURNAL OF TRANSPORTATION ENGINEERING ? ASCE / JULY 2009
J. Transp. Eng., 2009, 135(7): 406-415
model appears to be a good compromise between network accuracy and model sophistication. Due to the intrinsic complexity of model formulation the network design problem has been recognized as one of the most dif?cult and challenging problem in transportation. In spite of substantial research in this area there is still a scope for improvement. In particular, an ef?cient convergent algorithm for large scale bilevel traf?c modeling and optimization is yet to be developed ?Yang and Bell 2001?. Therefore, this study is an attempt to ?nd optimal capacity expansion for a large city network.
Literature Review
Downloaded from ascelibrary.org by Columbia University on 12/02/16. Copyright ASCE. For personal use only; all rights reserved.
The ?rst discrete network design formulation was proposed by LeBlanc ?1975? and later Abdulaal and LeBlanc ?1979? extended it to a continuous version. This network design problem with continuous investment variables subject to equilibrium assignment was formulated as a nonlinear unconstrained optimization problem. Hook–Jeeves pattern search algorithm ?H-J algorithm? and Powell’s algorithm were used for solving these models on a medium sized realistic network ?Abdulaal and LeBlanc 1979?. Since then, several variations of the network design problem were studied extensively. Optimization of road tolls under condition of queuing and congestion ?Yan and Lam 1996; Yin 2000?, optimization of reserve capacity of a whole signal controlled network ?Wong 1997; Yin 2000?, estimation of trip matrix ?Maher et al. 2001?, and optimization of traf?c signal ?Maher et al. 2001? are some variations of the network design problems. All these problems are normally formulated as a bilevel programming problem in which the lower lever problems are either deterministic or stochastic user equilibrium. The upper level problems are variants of system optimum design with decision variables speci?c to the problem at hand. There are some attempts to formulate them as an equivalent single level problem. For example, Meng et al. ?2001? proposed an equivalent single level continuously differentiable optimization model for the conventional bilevel continuous network design problem and solved it using Lagrangian algorithm. Bilevel formulations of the network design problem are nonconvex and nondifferentiable and therefore getting global optimum solution is not easy ?Yan and Lam 1996?. These problems are dif?cult to solve and designing ef?cient algorithms is still considered to be one of the most challenging tasks in transportation ?Meng et al. 2001?. Therefore, several solution approaches have evolved over the past few decades. Initial approaches used heuristic algorithms, which may give near optimal solution or local optimum solutions ?Steenbrink 1974; Allsop 1974?, or methods like equilibrium decomposed optimization ?EDO? ?Suwansirikul et al. 1987?, which are computationally ef?cient but result in suboptimal solutions. Sensitivity analysis of user equilibrium assignment was proposed by Tobin and Friesz ?1988?. Yang ?1995, 1997? developed ef?cient sensitivity analysis based models for the traf?c control problem. A similar approach is adopted to ?nd reserve capacity of signal controlled networks ?Wong and Yang 1997?. However, the sensitivity analysis based algorithm lacks theoretical guarantees ?Meng et al. 2004?. Chiou ?1999? explored a mixed search procedure to solve an area traf?c control optimization problem con?ned to equilibrium ?ows where local optimum solution can be effectively found using the gradient search method. Chiou ?2005? exploited a descent approach by implementing gradient based methods. Lim et al. ?2005? followed a bilevel formulation similar to a Stackelberg game approach. The
relation between link ?ows and design parameters were formed as a closed form function by using a logit route choice model. The heuristic solution approaches also have their own limitations as they are not suitable for large real networks problems since they require the approximate derivatives to have the same sign as original derivatives, which is dif?cult to verify in many cases ?Meng et al. 2001?. In a bilevel formulation, user equilibrium problems at a lower level can be formulated as variational inequality problems ?Dafermos 1980; Smith 1979? and this approach was attempted by Marcotte ?1983?. However, it suffers from the limitation of using path ?ows in the formulation, which makes it dif?cult to use in large network problems ?Meng et al. 2001?. With the advent of computing power, computationally demanding tools with potential for easy implementation and global optimum solution are becoming increasingly popular. For instance, the simulated annealing ?SA? algorithm is applied by Friesz et al. ?1992? for network design problems. Although simulated annealing has the potential to obtain good solutions in a short time, it is not able to improve these solutions even if more time is given. In spite of various intriguing attempts to solve the bilevel programming problem, these algorithms are unfortunately either incapable of ?nding the global optimum or require very complex gradient computation or unable to handle networks of realistic size ?Yin 2000?. Therefore, designing an ef?cient solution algorithm for a large scale continuous NDP remains a challenging task ?Meng et al. 2001?. Genetic algorithm ?GA? is yet another tool that has emerged as an ef?cient and simple implementation of several nonsmooth optimization problems ?Yin 2000?. GA was successfully utilized for optimal road pricing and reserve capacity of a signal controlled road network ?Yin 2000?. The motivation of using GAs is due to its globality, parallelism, and robustness. In addition, GAs are simple and powerful in their search for improvement and not fundamentally limited by restrictive assumptions about the search space ?assumptions concerning continuity, existence of derivatives, and other matters? ?Yin 2000?. Unlike simulated annealing, GA is a slow starter and is able to improve the solution consistently given suf?cient time. Ceylan and Bell ?2004? used a GAbased approach for traf?c signal control problems. The GA based model is also used for very large transit route network design and frequency setting problems ?Aggarwal and Mathew 2004?. All the bilevel algorithms have been tested only on very small test networks and few have attempted medium size networks. However, there appears to be no study on the application of the model on large real networks. Therefore, this paper is an attempt to use genetic algorithm for capacity expansion problems, an important extension to bilevel network design problems focusing on its application to a real large scale network.
Model Formulation
Determining the optimal link capacity expansions is formulated as a bilevel continuous network design problem ?CNDP? with the upper level problem minimizing the system travel cost subject to user’s travel behavior. This behavior is represented in the lower level using the Wardropian user equilibrium principles. The upper level problem is an example of system optimum assignment and can be solved using any ef?cient algorithm. The following notation has been used for CNDP formulation: A = set of links in the network, q = vector of ?xed origin destination ?OD? pair demands, qrs ? q = demand from node r to node s; K = set of paths or routes between OD pair r and s; f = vector of
JOURNAL OF TRANSPORTATION ENGINEERING ? ASCE / JULY 2009 / 407
J. Transp. Eng., 2009, 135(7): 406-415
path ?ows, f = ? f rs k ?; x = vector of equilibrium link ?ows; x = ?xa?, y = vector of link capacity expansions; y = ?y a?, ?rs a,k = 1 if route k between OD pair rs uses link a; and 0 otherwise; and ga?ya? = improvement cost function for arc a. The upper level problem is to minimize the total system travel time under a budget constraint and is formulated as Upper level Minimize Zy = ?a?xata?xa, y a?? subject to ? ?ag a? y a? ? B
Downloaded from ascelibrary.org by Columbia University on 12/02/16. Copyright ASCE. For personal use only; all rights reserved.
Investment Function Convergence Criteria OD Matrix Network Data
Upper Level
Minimize System
Cost y’ y’’
Travel Time Function
User Equilibrium Traffic Assignment (Lower Level) x’
GA Operations
?1? ?2? ?3?
Link Capacity Flows Cost of Construction Yes
y’ Converged
No
y a ? 0: ? a ? A
Stop
It should be noted that the term ?ga?y a? represents the total improvement expenditure and the budget constraints can be written as ??aga?y a? ? B. The upper level will give a trial capacity expansion vector ya and will be translated into new link capacities. Based on the new link capacity values, the link ?ows can be computed by solving the following formulation: Lower level Minimize Zx = ?a subject to ??k f rs k = qrs:k ? K ;
rs xa = ?r?s?k?rs a,k f k : r , s ? q ;
Fig. 1. Flowchart representing solution approach
?
xa
ta?xa, y a?dx
?4?
0
r, s ? q; a ? A; k?K k?K
?5? ?6? ?7? ?8?
f rs k ? 0:r, s ? q ;
xa ? 0:a ? A
Note that the solution to the above formulation will give Wardrop’s user equilibrium link ?ows. The link cost function that this study uses is the popular Bureau of Public Roads ?BPR? equation which is given by t a? x a, y a? = t o a 1 + ?a
? ? ??
xa ca + y a
?a
?9?
where to a = free ?ow time on link a; xa = link ?ow; and ?a and ?a = link speci?c constants. The sum of the capacity expansion y a and the base capacity ca represents the improved link capacity. Since BPR Eq. ?9?, is a monotonically increasing convex function and the travel time on the link a depends on the ?ows on that link alone, the lower level formulation given by Eqs. ?4?–?8? is convex. Therefore, there is a unique global solution and can be computed by any ef?cient convex combination method, like the Frank–Wolfe algorithm. One should note that the key model assumptions that have been considered are as follows: 1. The assignment is static, i.e., deterministic user equilibrium assignment; 2. The OD matrix is ?xed and for peak hour traf?c; and 3. The road geometries other than width and length have not been considered while calculating the improvement scheme.
Fig. 1. The algorithm starts in the upper level by reading all the inputs, like network details, demand matrix, budget, link expansion cost functions, and travel time function. The upper level algorithm will give a trial capacity expansion vector y? and will be translated into new network capacities. The upper level then invokes the lower level with these new link capacities. At the lower level, the demand matrix is assigned to the network based on the user equilibrium principles. This is accomplished by solving the lower level problem given by Eqs. ?4?–?8?, using the Frank–Wolfe algorithm. The application of this algorithm provides user equilibrium link ?ows x?. These link ?ows are passed to the upper level. From the link ?ow, the objective function, which is the sum of system travel time and the total link expansion cost, is computed. This objective function value is passed to the genetic algorithm operators, which then computes a new trial capacity expansion vector y? based on the objective function values. This new trial capacity expansion vector is passed to the lower level. This procedure is repeated until convergence. An important step in this method is the transformation of the problem into an equivalent formulation on which GA can apply its operators. Suppose the capacity expansion vector y = ?y 1 , y 2 , y 3 ? y n? : Rn → R is mapped to the objective function value Zy ??tness function in GA parlance?. Suppose further that each decision variable y a can take the value from a domain max bounded by ?y min a , y a ? ? R. Then, the decision variable y a requires ? binary bites to represent it in a binary form. This string length ? is the minimum value that satis?es the following relation: ? y min ?y max a a ? ? ?2? ? 1? ? ?10?
where ? = required precision ?Goldberg 1989; Deb 1998?. To convert this binary string back to a decimal, the following linear mapping can be used: ya = y min a + ?y max ? y min a a ? ? ?2 ? 1?
?? ?
??1 j=0
b j2 j ,
b j ? ?0,1?
?11?
Solution Approach
A genetic algorithm based iterative procedure is adopted to get the solution. The ?owchart of the solution approach is given in
where b j represents the binary digit at jth position ?Goldberg 1989?. Similarly, each variable of the y can be represented as a binary string. The binary string of each variable is concatenated to get the solution string or the chromosome which forms an instance of the solution ?Fig. 2?. The above coding is necessary as the GA operators can work only on the coded variable to generate
408 / JOURNAL OF TRANSPORTATION ENGINEERING ? ASCE / JULY 2009
J. Transp. Eng., 2009, 135(7): 406-415
y
y1
y2 . . . . . . . . . . . . . . . . . . yn
Chromosome (coded y)
11011 10011 . . . . . . . . . . . . 11001
The network details, link parameters, and demand data are adopted from the study by Suwansirikul et al. ?1987?. For the purpose of comparison, the upper level formulation given by Eqs. ?1?–?3? is rewritten as follows: Minimize Zy = ?a?xata?xa, y a? + ?ga?y a?? subject to y a ? 0: ? ? A ?14? ?13?
Fig. 2. Representation of decision variables
Downloaded from ascelibrary.org by Columbia University on 12/02/16. Copyright ASCE. For personal use only; all rights reserved.
a new trial solution. The decoded variables are used in evaluating the trial solution by computing the corresponding objective function value. The most important GA operators are reproduction, crossover, and mutation ?Goldberg 1989?. The second aspect is to handle the budget constraint ???aga?y a? ? B? in the upper level formulation ?Eqs. ?1?–?3??. GA is naturally suited for handling the unconstrained functions. Here, the constrained formulation is transformed into an equivalent unconstrained function ?k by an exterior penalty function method ?Rao 1996? as follows: ?k = ??x, r? = ?xata?xa, y a?? + r? Max 0, ? ga?y a? ? B ? a ?a
?
??
?12? where, ?k = unconstrained objective; r = penalty parameter; and Max?0 , ??aga?y a? ? B? = constraint violation term. The function value ?k is passed to GA to compute ?tness function. Example Network 1 To investigate whether the solution of the bilevel problem using genetic algorithm gives the global optimum value, an example network having four nodes and ?ve links ?Fig. 3? is considered.
d14 = 100 c1 = 40 x1
2
4 a ta = Aa + Ba ( cax +ya )
x4 c3 = 60
c4 = 40
1
c2 = 40 x2
x3
4
c5 = 40
x5
3
Fig. 3. Example 1: network having four nodes ?ve links
It should be noted that the term ?ga?y a? represents the total improvement expenditure. The parameter ? = relative weight of improvement costs and travel costs, or dual variable for the budget constraints ?Suwansirikul et al. 1987?. The lower level formulation is the same as reported by Eqs. ?4?–?8?. In order to ascertain the effect of the genetic algorithm input values, a parameter study was conducted on this network. It was found from the study that the model gave the best performance at a crossover probability of 0.4, mutation probability of 0.05, and a population size of 10 and 100 generations. First, the genetic algorithm model is applied to this network. Then, a complete enumeration ?or exhaustive search? method is adopted to ?nd the global optimal solution. Finally, these results are compared with solutions from other existing major algorithms like modular in-core nonlinear optimization system ?MINOS?, Hook-Jeeves ?H-J?, and equilibrium decomposition optimization ?EDO? ?Suwansirikul et al. 1987?. The results are tabulated in Table 1. The ?rst column of Table 1 shows the optimum solution obtained by solving the problem by complete enumeration. Note that the complete enumeration gives the global optimum solution, and the objective function value obtained is 1,200.58 units. The objective function values obtained by MINOS and genetic algorithm is the same as the solution obtained by complete enumeration. This shows the ability of GA to obtain a global optimum solution of NDP. Although MINOS is able to obtain global optimal solution it is not suitable for large networks ?Suwansirikul et al. 1987?. Similarly, complete enumeration is prohibitively computational expensive even for small networks. Further, all three solutions gave different link capacities for the same objective function values, suggesting multiple optimum solutions. In order to check the sensitivity of the demand, a sensitivity analysis was performed by varying the demands and compared with the solutions from existing algorithms ?Suwansirikul et al. 1987?, and the results are reported in Table 2. Since the computational effort needed to get the complete enumeration solu-
Table 1. Comparison of Results from Solving Example Network 1 with Complete Enumeration and GA and Other Existing Algorithms Case demand 100 y1 y2 y3 y4 y5 Zy Equilibrium decomposition optimization ?EDO? 1.31 1.19 0.06 0.94 1.06 1,200.64 Genetic algorithm ?GA? 1.33 1.22 0.02 0.96 1.10 1,200.58
Complete enumeration 1.35 1.20 0.00 0.95 1.10 1,200.58
MINOS 1.34 1.21 0.00 0.97 1.10 1,200.58
Hook-Jeeves ?H-J? 1.25 1.20 0.00 0.95 1.10 1,200.61
JOURNAL OF TRANSPORTATION ENGINEERING ? ASCE / JULY 2009 / 409
J. Transp. Eng., 2009, 135(7): 406-415
Table 2. Sensitivity Analysis of Solution for Example Network 1 with GA and Various Other Existing Algorithms Equilibrium decomposition optimization ?EDO? 1.31 1.19 0.06 0.94 1.06 1,200.64 5.98 5.52 0.02 4.60 5.20 3,156.24 12.86 12.02 0.02 10.33 11.77 7,086.45 28.11 26.03 0.01 23.39 26.58 21,210.54 Genetic algorithm ?GA? 1.33 1.22 0.02 0.96 1.10 1,200.58 6.08 5.51 0.00 4.65 5.27 3,156.23 13.04 11.73 0.01 10.33 11.78 7,086.16 28.48 25.82 0.08 23.39 26.48 21,210.06
Case Demand= 100 y1 y2 y3 y4 y5 Zy Demand= 150 y1 y2 y3 y4 y5 Zy Demand= 200 y1 y2 y3 y4 y5 Zy Demand= 300 y1 y2 y3 y4 y5 Zy
MINOS 1.34 1.21 0.00 0.97 1.10 1,200.58 6.05 5.47 0.00 4.64 5.27 3,156.21 12.98 11.73 0.00 4.64 5.27 7,086.12 28.45 25.73 0.00 23.40 26.57 21,209.90
Hook-Jeeves ?H-J? 1.25 1.20 0.00 0.95 1.10 1,200.61 5.95 5.65 0.00 4.60 5.20 3,156.38 13.00 11.75 0.00 10.34 1175 7,086.21 28.44 28.75 0.00 23.44 26.56 21,209.91
Downloaded from ascelibrary.org by Columbia University on 12/02/16. Copyright ASCE. For personal use only; all rights reserved.
tion for all the demand levels of 150, 200, and 300 is quite high, the values reported in Table 2 do not include solutions by complete enumeration. The computational effort is high because the precision required is 0.01. The result shows the solutions obtained by the GA models consistently outperforms the HookJeeves and EDO solutions and reaches very close to that of MINOS. This analysis also con?rms the possibility of multiple optimal solutions. Example Network 2: Sioux Falls Network The second test network taken for the study is the Sioux Falls network, which is probably the most extensively used test network for the continuous network design problem. The Sioux falls network, as shown in Fig. 4, has 24 nodes, 76 links, and 528 nonzero OD pairs. Among the 76 links, ten links ?Links 16, 17, 19, 20, 25, 26, 29, 39, 48 and 74? are the candidate links for capacity expansion. The network details and input parameters are adopted from the study by Suwansirikul et al. ?1987?. The optimal capacity expansion vector and the corresponding system cost is found using the proposed genetic algorithm model and compared with other existing algorithms such as Hook-Jeeves ?H-J?, EDO, SA, sensitivity analysis based ?SAB?, gradient projection ?GP?, conjugate gradient projection ?CG?, quasi-Newton projection ?Qnew?, and Paratan version of gradient projection ?PT? ?Chiou 2005?. The link expansion values and the objective
function values from all these models and GA solution are tabulated in Table 3. GA being a probabilistic model, the optimal solution is selected as the best outcome of several trials by varying the random seed. GA* in Table 3 is the optimum solution thus obtained. It can be seen clearly from these results that the SA and GA are able to produce relatively good results; and among all the models GA is able to produce the best solution. It should be noted that in spite of relative closeness of objective function values the links expansion values are not consistent. This again con?rms that the problem has multiple optimal solutions. In addition to the optimum solution, a suboptimal solution from one of the trial random seed reported in Table 3 as GA+. These two solutions have very close objective function values, but different expansion values. The purpose of reporting GA+ is to study the sensitivity of the solution when demand exceeds the design value. The solution from SAB is noteworthy because it has very high expansion values for almost all the links. In order to study the performance of the GA model with respect to other models, two types of sensitivity studies are conducted. First, network design is done at several demand levels. The base demand is multiplied by a factor ?0.8, 1.2, 1.4, and 1.6? and the model is applied. The total system cost and the number of Frank–Wolfe iterations performed under these demand levels are tabulated in Table 4.
410 / JOURNAL OF TRANSPORTATION ENGINEERING ? ASCE / JULY 2009
J. Transp. Eng., 2009, 135(7): 406-415
3 1 1 2 3 6 5 8 4 9 13 10 7 35 26 33 12 36 11 32 30 34 40 28 43 27 10 29 51 49 52 17 53 41 37 38 14 44 42 71 72 23 70 73 74 13 39 24 75 76 66 21 64 69 65 63 68 62 20 22 59 61 46 67 15 45 31 9 24 25 48 16 22 47 55 18 50 23 21 11 5 12 16 8 20 18 54 19 17 7 15 6 4 2 14
Downloaded from ascelibrary.org by Columbia University on 12/02/16. Copyright ASCE. For personal use only; all rights reserved.
58 56 19 60
57
other algorithms, its solution obtained gives the lowest objective function value. The time taken by the GA model at a single demand level for network design of Sioux Falls was about 122 s. The second sensitivity analysis is carried out to study the resilience of the solution. This is done by loading a scalar product of the base demand matrix in the already expanded network ?that is the y a values are the same as that shown in Table 3? and compute the system cost under user equilibrium conditions. This will show the sensitivity of the solution when the demand changes after the construction. The system cost under various demand levels ?0.8–1.6? is shown in Table 5. A lower value indicates lower system travel time, and is an indication of higher model resilience when the demand varies. In this respect, the SAB model is least affected by the demand variation. However, this is due to ?as noted earlier? the overestimation of expansion values at the expense of construction cost. To verify this, we have used the alternate GA solution ?GA+?, which incidentally gave higher values of expansion with slightly higher system cost. As expected, the solution obtained in this case was much closer to the one obtained by SAB solution ?Tables 3 and 5?. Thus, the difference between objective function values obtained by GA ?alternate solution? and SAB is quite marginal. Overall, one can observe that the GA model is very resilient to the demand function.
Case Study
The objective of the case study is to demonstrate the ef?cacy of a GA based model for large capacity expansion problems. The network of Pune city in Maharastra state, India, is considered for the case study. This city has an area of 138 km2. The city is divided into 97 zones out of which 85 are internal zones and 12 are external zones. There are 273 road nodes and 97 zone centroids with 1,131 road links. Fig. 5 shows the network of the city. The demand data includes 4,083 nonzero origin-destination pairs. The peak hour trips within the network are 118,428 passenger car units ?PCU?. Various traf?c ?ow parameters like ?a, ?a, free ?ow speed, and running speed for all the links were found after surveying. The parameters for the link travel time functions were developed for various classes of roads based on extensive
Fig. 4. Example 2: Sioux Falls network having 24 nodes, 76 links
The computational performance of these models is compared by observing the number of Frank–Wolfe ?FW? evaluations, which eliminates the bias of the computing platforms. In addition, the literature supports such comparison in the form of a number of FW evaluations for design ?Chiou 2005?. The values written in parenthesis in Table 4 are the number of FW iterations. Although the number of FW evaluations by GA is much higher than the
Table 3. Comparison of Results from Solving Sioux Falls Network with GA and Solution of Various Existing Algorithms Case Init. y a y 16 y 17 y 19 y 20 y 25 y 26 y 29 y 39 y 48 y 74 Zy H-J 2.0 4.8 1.2 4.8 0.8 2.0 2.6 4.8 4.4 4.8 4.4 82.50 H-J 1.0 3.8 3.6 3.8 2.4 2.8 1.4 3.2 4.0 4.0 4.0 82.61 EDO 12.5 4.59 1.52 5.45 2.33 1.27 2.33 0.41 4.59 2.71 2.71 84.50 SA 6.25 5.38 2.26 5.50 2.01 2.64 2.47 4.54 4.45 4.21 4.67 81.89 SAB 12.5 5.74 5.72 4.96 4.96 5.51 5.52 5.80 5.59 5.84 5.87 84.38 GP 12.5 4.87 4.89 1.87 1.53 2.72 2.71 6.25 5.03 3.76 3.57 84.15 CG 12.5 4.77 4.86 3.07 2.68 2.84 2.98 5.68 4.27 4.40 5.52 84.86 QNew 12.5 5.30 5.05 2.44 2.54 3.93 4.09 4.35 5.24 4.77 4.02 83.19 PT 12.5 5.02 5.22 1.83 1.57 2.79 2.66 6.19 4.96 4.07 3.92 84.19 GA* — 5.17 2.94 4.72 1.76 2.39 2.91 2.92 5.99 3.63 4.43 81.74 GA+ — 5.24 3.54 4.85 2.89 1.75 2.04 6.03 5.47 5.77 5.68 82.88
Note: GA* = optimal solution obtained by GA, GA+=alternate solution generated to compare with SAB algorithm. In order for a uniform comparison, the objective function values computed from the capacity expansion values are by using the Frank–Wolfe algorithm implemented by the writers for this study. Therefore, the results may slightly differ from the one’s reported by Chiou ?2005?, but are on the same scale. Hook-Jeeves ?H-J?, equilibrium decomposition optimization ?EDO?, simulated annealing ?SA?, sensitivity analysis based ?SAB?, gradient projection ?GP?, conjugate gradient ?CG?, quasi-Newton projection ?QNew?, Partan ?PT?, and genetic algorithm ?GA?.
JOURNAL OF TRANSPORTATION ENGINEERING ? ASCE / JULY 2009 / 411
J. Transp. Eng., 2009, 135(7): 406-415
Table 4. Sensitivity Analysis of Different Solutions Obtained for Sioux Falls Network with GA and Various Other Existing Algorithms at Various Values of Demand Scalar/algorithm 0.80 SAB GP CG QNew PT EDO IOA GA
Downloaded from ascelibrary.org by Columbia University on 12/02/16. Copyright ASCE. For personal use only; all rights reserved.
51.76 48.38 48.78 48.84 48.81 49.51 53.58 48.92 ?14? ?10? ?3? ?4? ?9? ?7? ?28? ?59? 1.00 84.21 82.71 82.53 83.07 82.53 83.57 87.34 81.74 ?11? ?9? ?6? ?4? ?7? ?12? ?31? ?77? 1.20 144.86 141.53 141.04 141.62 142.27 149.39 150.99 137.92 ?9? ?11? ?10? ?7? ?9? ?12? ?31? ?67? 1.40 247.8 246.04 246.04 242.74 241.08 253.39 279.39 232.76 ?15? ?9? ?6? ?5? ?7? ?17? ?16? ?78? 1.60 452.01 433.64 408.45 409.04 431.11 427.56 475.08 390.54 ?14? ?9? ?9? ?9? ?11? ?19? ?40? ?83? Note: Values written in bracket are number of Frank–Wolfe iterations performed. The different objective function values are for optimal expansion in each case, i.e., every time the expansion values generated will be different for different demands. Sensitivity analysis based ?SAB?; gradient projection ?GP?; conjugate gradient ?CG?; Partan ?PT?, equilibrium decomposition optimization ?EDO?, iterative optimization assignment ?IOA?, and genetic algorithm ?GA?.
?eld data. Link characteristics were collected and a trip table was generated for the whole network after validating the OD counts. Sample link parameters are shown in Table 6. In order to study the performance of the CNDP on this network, different scenarios, with budgets of 25, 50, 100, and 250 crores rupees ?1 crore rupee= $ 0.22 million? have been considered. The maximum capacity expansion of each link is assumed to be 100%. The model is applied with GA parameters like population size of 100, two point crossover with a probability of 0.8, and a mutation probability of 0.01. These parameters of the genetic algorithm run are chosen based on the experience gained from the study of the example networks and the values suggested in the literature for similar problems ?Yin 2000?. The convergence criteria adopted is the completion of 10,000 generations. This large value is suggested to ensure the convergence of the problem. The computation was carried out in a Intel Xeon processor with four clusters and the clock speed of 3.2 GHz, 1 GB RAM and LINUX Fedora Core 4 operating system. The computation time taken by a single run for ?nding optimal capacity expansion was about 72 h. The optimal capacity expansion values under each budget scenario was obtained by the proposed CNDP algorithm The absolute network performance for all the budget scenarios is shown in Table 7 and the relative improvement with the base case is shown in parenthesis. From these results, it can be inferred that the average travel time is reduced by 26% with a spending of rupees 25 crore ?$5.5 million? and it continues to reduce until it reaches 39% at higher budget. However, with a budget beyond rupees 100 crore, there is only a marginal increase in the average travel time improvement. The corresponding improvements in the average
Table 5. Sensitivity Analysis of Solutions Obtained by Varying Demand Scalar/case Init. y a 0.8 1.0 1.2 1.4 1.6 H-J 2.0 49.92 82.61 144.49 260.64 463.02 H-J 1.0 50.27 82.50 141.75 253.32 448.84 EDO 12.5 50.11 84.50 150.40 273.30 485.83 SA 6.25 50.58 81.89 140.48 248.99 439.05 SAB 12.5 54.94 84.83 139.84 240.8 416.69
link speeds are about 5–9% and the maximum link speeds are only about 2–3%. On the other hand, in the case of minimum link speeds, the improvement is in the range of 16–96%. This is expected since the algorithm selected the heavily congested links ?rst and maximum expansions were made. Therefore, the minimum travel time improved signi?cantly when the speed is improved under higher capacity. This in turn might result in diversion of traf?c to such links. Furthermore, the parameters of the BPR function were calibrated at the base capacity values. In reality, these values may change at higher capacities. However, this aspect is not considered, which may result in relatively low improvement of travel speed. In addition, this analysis also gives an insight into the optimal budget allocation level. The performance of the network improved signi?cantly at lower budget as evident from Table 7. However, the increase in budget beyond about 100 crore does not make any signi?cant difference to the network. The actual spending for each scenario is also shown in Table 7. The actual spending is the product of the unit cost of construction and the proposed capacity expansion. Ideally, one would expect the budget and actual spending to match even at a very low and very high budget, but it is dif?cult to ensure constraint satisfaction at a very low and very high budget ?see Table 7 for 25 crore and rupees 250 crore scenario?. At 25 crore, the constraints are clearly violated. This is not unexpected, since we have adopted an exterior penalty function method to handle the constraints where the intermediate solution may lie in the infeasible region. It only suggests that the solution has not converged within speci?ed iterations. This is understandable since the budget of rupees 25 crore is extremely low for such a big and congested network. It is quite clear from the table that even at a
GP 12.5 51.68 84.75 147.95 264.89 465.21
CG 12.5 51.79 83.37 143.56 253.48 447.21
QNew 12.5 51.88 83.84 143.58 258.19 458.56
PT 12.5 51.85 84.77 146.95 263.09 469.98
GA* — 50.62 81.74 143.09 255.10 446.05
GA+ — 52.43 82.88 140.49 246.05 427.83
Note: GA* = final solution obtained by GA; GA+=alternate solution generated to compare with SAB algorithm. Hook-Jeeves ?H-J?; equilibrium decomposition optimization ?EDO?; simulated annealing ?SA?; sensitivity analysis based ?SAB?; gradient projection ?GP?; conjugate gradient ?CG?; quasiNewton projection ?QNew?, Partan ?PT?, and genetic algorithm ?GA?.
412 / JOURNAL OF TRANSPORTATION ENGINEERING ? ASCE / JULY 2009
J. Transp. Eng., 2009, 135(7): 406-415
2e+07
PUNE CITY
N
85 50
1.8e+07
86
Downloaded from ascelibrary.org by Columbia University on 12/02/16. Copyright ASCE. For personal use only; all rights reserved.
87 69 72 67 68 70 66 52 71 73 81 82 83 74 75 56 54 806379 8476 53 55 64 78 77 96 62 57 65 59 1 49 6158 51 60 2 0 95 7 8 23 9 10 11 6 48 24 22 29 30 25 12 32 94 4631 47 33 20 21 28 39 13 40 42 45 41 38 43 44 19 5 37 3635 14 3 34 15 27 26 4 93 18 97 16 17 92 1Km 91
Total System Travel Cost
1.6e+07 1.4e+07 1.2e+07 1e+07 8e+06 6e+06 4e+06 2e+06 0 2000 4000
B B B B
= 25 crore = 50 crore = 100 crore = 250 crore
88
89 90
6000
8000
10000
Number of Iterations
Fig. 5. Pune city network with links and zone centroids
Fig. 6. Convergence history for typical budgets
higher budget the actual spending are much less than the amount allotted. This may be attributed to the fact that only congested links are expanded and spending beyond this will result only in the escalation of construction cost. Further, this analysis also give an insight into the desirable budget for network improvement. The convergence history for each budget scenario is shown in Fig. 6. From the graph, one can observe a very good convergence, especially at higher budget levels. This may be because demand pairs have very few alternate paths, whereas at a lower budget the shortest path will change even when there is only a slight change in the capacity, which results in several more iterations converging.
Conclusion
This study is an attempt to solve large network capacity expansion problem using genetic algorithm. This network design problem has been formulated as a bilevel problem where the upper level determines the optimal link capacity expansion vector and the lower level determines the link ?ows subject to user equilibrium conditions. The upper level is solved by genetic algorithm and the lower is solved using the Frank–Wolfe algorithm. The upper level module will give a trial capacity expansion vector and will be translated into new network capacities. This then invokes the lower level problem which gives user equilibrium
Table 6. Sample Link Input Parameters for Pune Network Link length ?km? 1.00 2.24 1.70 2.02 1.68 1.00 1.10 Number of lanes 1 1 1 1 1 1 1 Alpha ?a 0.70 0.68 0.65 0.68 0.70 0.65 0.68 Beta ?a 2.0 2.0 2.2 2.5 1.5 1.5 2.5 Initial capacity ?PCU/h? 3,200 2,600 1,100 600 2,600 1,000 4,350 Free ?ow speed ?km/h? 40 35 35 40 50 35 40
From 128 114 222 211 98 12 178
To 340 258 254 253 255 367 138
Table 7. Comparison of Improvement in Traf?c Flow Characteristics with Different Budgets Budget in rupees. ?crores?a Base case 25 Average travel time ?min? Average link speed ?km/h? 25.79 27.09 ?5%? 27.35 ?6%? 28.05 ?9%? 28.21 ?9%? Minimum link speed ?km/h? 6.63 7.79 ?17%? 9.16 ?38%? 13.03 ?97%? 12.57 ?89%? Maximum link speed ?km/h? 52.91 53.84 ?2%? 54.38 ?3%? 53.45 ?1%? 53.92 ?2%? Total system cost ?veh./h? 49,799 36,781 ?26%? 33,846 ?32%? 30,597 ?39%? 30.298 ?39%? Actual spendings ?crores? — 48.15 — 50.01 — 99.81 — 122.63 —
25.23 18.63 ?26%? 50 17.14 ?32%? 100 15.50 ?39%? 250 15.34 ?39%? a Crore rupees= $ 0.22 million.
JOURNAL OF TRANSPORTATION ENGINEERING ? ASCE / JULY 2009 / 413
J. Transp. Eng., 2009, 135(7): 406-415
?ows. The link ?ows are then passed to upper level. The upper level then computes the objective function value, which is the total system travel cost and the investment cost. This objective function value is given to the genetic operators, which supplies a new capacity expansion vector, and the process is repeated until convergence. The working of the proposed model is ?rst tested with the help of a hypothetical network reported in the literature. This study demonstrates the ability of genetic algorithm to arrive at global optimal solution. Next, a medium sized network, Sioux Falls, is tested with the present model. The solution from this is compared to all major existing solution approaches reported in the literature. This study showed that the present model is able to give a solution much better than the rest of the approaches. Only the solution using the simulated annealing approach is coming closer to the present model. Although simulated annealing has the potential to obtain good solutions in a short time, it is not able to improve these solutions even if more time is given, while GA is a slow starter that is able to improve the solution consistently when given suf?cient time. In addition it is possible that SA may discard potentially “good” solutions because it retains only a single solution unlike GA which retains a population of solutions ?Thompson and Bilbro 2000?. The sensitivity analysis of the model is performed by designing the networks at different demand levels. The resilience of the solution when demand increases the design demand is also carried out. This advocates the use of GA as it offers a resilient solution. Finally, to achieve the objective of developing a network design procedure for the large transportation network, a case study is considered. Accordingly, the network of Pune city, India having 1,131 road links and 370 nodes is solved under different budget levels. The results shows a large reduction in total system cost and average travel time with respect to the base case. The signi?cant increase in minimum speed of the links shows the ef?cacy of algorithm to select the most congested links for improvement. The proposed model will be a very useful tool for planners for allocation of budgets and prioritization of links for improvements. Although GA may be computationally intensive and may take more time in ?nding the optimal solution for a realistic large network design the computation time can be signi?cantly reduced. Simple or canonical genetic algorithm is used in the present study. There are several ways of reducing the computational time of GA like dynamic population size, distributed computing, hybrid systems, etc. Further, one should consider the fact that capacity expansion designs are not done frequently. Therefore, the limitation of high computational time may be offset by the bene?t from a better solution. Finally, GAs are identically suited for various extensions of the network design problem like considering emission cost, demand uncertainty, etc. One more important aspect of network design is the timing and prioritization of improvements. Modeling the timing and prioritization of improvements will de?nitely improve bene?ts. For example, the projected demand will not be realized immediately. This can be accommodated by considering the demand realization over several horizon years. This approach will optimally decide, for instance, the links to be extended and so during various time periods within the study duration. However, this requires much more complex modeling. The complexity is attributed to factors like: ?1? incorporation of multiple OD matrices in a single optimization problem; ?2? resulting computation time and variable explosion; and ?3? consideration of time value of money typically the net present value ?NPV?. Some other possible extensions of the problem are to consider the variability
in the demand ?Ukkusuri et al. 2007? and variability in travel time ?Chen et al. 2002; Clark and Watling 2005?. Finally, improvement in computational time by ef?cient GA implementation, the hybrid GA model, distributed computing, etc., need to be explored.
Acknowledgments
The writers are grateful to Mr. Mallikarjun Setty and Dr. Tagore of the CES organization for providing Pune city data. They are also grateful to reviewers for their useful comments and suggestions.
Downloaded from ascelibrary.org by Columbia University on 12/02/16. Copyright ASCE. For personal use only; all rights reserved.
References
Abdulaal, M., and LeBlanc, L. J. ?1979?. “Continuous equilibrium network design problem.” Transp. Res., Part B: Methodol., 13, 19–32. Aggarwal, J., and Mathew, T. V. ?2004?. “Transit route network design using genetic algorithms.” J. Comput. Civ. Eng., 18?3?, 248–256. Allsop, R. E. ?1974?. “Some possibilities for using traf?c control to in?uence trip distribution and route choice.” Proc., 6th Int. Symp. on Transportation and Traf?c Theory, D. J. Buckley, ed., Elsevier, New York, 345–375. Ceylan, H., and Bell, M. G. H. ?2004?. “Traf?c signal timing optimization based on genetic algorithm approach, including driver’s routing.” Transp. Res., Part B: Methodol., 38, 329–342. Chen, A., Ji, Z., and Recker, W. ?2002?. “Travel time reliability with risk sensitive travelers.” Transportation Research Record. 1783, Transportation Research Board, Washington, D.C., 27–33. Chiou, S. W. ?1999?. “Optimization of area traf?c control for equilibrium network ?ows.” Transp. Sci., 33?3?, 279–289. Chiou, S. W. ?2005?. “Bilevel programming for continuous network design problem.” Transp. Res., Part B: Methodol., 39, 361–383. Clark, S., and Watling, D. ?2005?. “Modeling network travel time reliability under stochastic demand.” Transp. Res., Part B: Methodol., 39, 119–140. Dafermos, S. ?1980?. “Traf?c equilibrium and variational inequalities.” Transp. Sci., 14?1?, 42–54. Deb, K. ?1998?. Optimization for engineering design: Algorithms and examples, Prentice-Hall, New Delhi, India. Fisk, C. S. ?1984?. “Game theory and transportation systems modelling.” Transp. Res., Part B: Methodol., 18, 301–313. Friesz, T. L., Cho, H. J., Mehta, N. J., Tobin, R. L., and Anandalingam, G. ?1992?. “A simulated annealing approach to the network design problem with variational inequality constraints.” Transp. Sci., 26?1?, 18–26. Goldberg, D. E. ?1989?. Genetic algorithms in search, optimization and machine learning, Addison-Wesley, Reading, Mass. LeBlanc, L. J. ?1975?. “An algorithm for discrete network design problem.” Transp. Sci., 9, 183–199. Lim, Y., Heydecker, B. G., and Lee, S. ?2005?. “A continuous network design model in stochastic user equilibrium based on sensitivity analysis.” J. Adv. Transp., 39?1?, 63–79. Maher, M. J., Zhang, X., and Vleit, D. V. ?2001?. “A bilevel programming approach for trip matrix estimation and traf?c control problems with stochastic user equilibrium link ?ows.” Transp. Res., Part B: Methodol., 35, 23–40. Marcotte, P. ?1983?. “Network optimization with continuous control parameters.” Transp. Sci., 17, 181–197. Meng, Q., Lee, D.-H., Yang, H., and Huang, H.-J. ?2004?. “Transportation network optimization problems with stochastic user equilibrium constraints.” Transportation Research Record. 1882, Transportation Research Board, Washington, D.C., 113–119. Meng, Q., Yang, H., and Bell, M. G. H. ?2001?. “An equivalent con-
414 / JOURNAL OF TRANSPORTATION ENGINEERING ? ASCE / JULY 2009
J. Transp. Eng., 2009, 135(7): 406-415
Downloaded from ascelibrary.org by Columbia University on 12/02/16. Copyright ASCE. For personal use only; all rights reserved.
tinuously differentiable model and a locally convergent algorithm for the continuous network design problem.” Transp. Res., Part B: Methodol., 35, 83–105. Rao, S. S. ?1996?. Engineering optimization: Theory and practice, Wiley, New York. Smith, M. J. ?1979?. “Existence, uniqueness, and stability of traf?c equilibria.” Transp. Res., Part B: Methodol., 13, 295–304. Steenbrink, P. A. ?1974?. Optimization of transport network, Wiley, West Sussex, U.K. Suwansirikul, C., Friesz, T. L., and Tobin, R. L. ?1987?. “Equilibrium decomposed optimization: A continuous network design problem.” Transp. Sci., 21?4?, 254–263. Thompson, D. R., and Bilbro, G. L. ?2000?. “Comparison of genetic algorithm with simulated annealing algorithm for design of an ATM network.” IEEE Commun. Lett., 4?8?, 267–269. Tobin, R. L., and Friesz, T. L. ?1988?. “Sensitivity analysis for equilibrium network ?ows.” Transp. Sci., 22?4?, 242–250. Ukkusuri, S. V., Mathew, T. V., and Waller, S. T. ?2007?. “Robust network design problem under demand uncertainty.” Comput. Aided Civ. Infrastruct. Eng., 22, 6–18.
Wong, S. C. ?1997?. “Group-based optimisation of signal timings using parallel computing.” Transp. Res., Part C: Emerg. Technol., 5?2?, 123–129. Wong, S. C., and Yang, H. ?1997?. “Reserve capacity of a signal controlled road network.” Transp. Res., Part B: Methodol., 31?5?, 397– 402. Yan, H., and Lam, W. H. K. ?1996?. “Optimal road tolls under conditions of queuing and congestion.” Transp. Res., Part A: Policy Pract., 30?5?, 319–332. Yang, H. ?1995?. “Sensitivity analysis for queuing equilibrium and network ?ows and its application to traf?c control.” Math. Comput. Modell., 22, 247–258. Yang, H. ?1997?. “Sensitivity analysis for elastic demand network equilibrium problem with applications.” Transp. Res., Part B: Methodol., 31, 55–70. Yang, H., and Bell, M. G. H. ?2001?. “Transport bilevel programming problems: Recent methodological advances.” Transp. Res., Part B: Methodol., 35, 1–4. Yin, Y. ?2000?. “Genetic algorithms based approach for bi-level programming models.” J. Transp. Eng., 126?2?, 115–120.
JOURNAL OF TRANSPORTATION ENGINEERING ? ASCE / JULY 2009 / 415
J. Transp. Eng., 2009, 135(7): 406-415