WIXLIB

Computational Intelligence and Neuroscience3choice behavior, denoting by V(u), is defined in lower-levelmodel. To facilitate the model presentation, the notationsused here and after are summarized in Notations section.(1) The Upper-Level Model. Travel time is a comprehensiveindex used to evaluate the congested and comfortable level ofuser’s trip. This paper uses the total travel time as the globaloptimization objective. It is expected that total travel time isreduced with the network capacity expansion. Following this,the upper model of road network capacity is as the followingformulas:𝑍 𝑡𝑎 (V𝑎 , 𝑢𝑎 ) V𝑎min𝑢𝑎 𝐴s.t.(2)𝑎 𝐴 𝑎 𝐴.(3)Formula (1) minimizes the total travel time in the network. Formula (2) makes sure that the increase of capacitywill never exceed the feasible budget. Formula (3) shows theupper limit and lower limit of increasing capacity of roadsections. To eliminate the constraints of budget, Lagrangetransform is used to simplify the upper model, as shown informulas (4) and (5). Consider the following:𝑍 𝑡𝑎 (V𝑎 , 𝑢𝑎 ) V𝑎 𝛾 𝑔𝑎 (𝑢𝑎 ) ,min𝑢𝑎 𝐴𝑎 𝐴0 𝑢𝑎 𝑢𝑎max ,s.t. 𝑎 𝐴.(4)(5)In formula (4), 𝛾 is the Lagrange multiplier.(2) The Lower-Level Model. In a fixed demand traffic assignment problem, with the given expanded capacity of linksand fixed demand between OD pairs, the lower model is astandard user equilibrium model, which describes the user’srouting choice behavior, as in the following formulas:minVs.t. 𝑡𝑎 (𝑥, 𝑢𝑎 ) 𝑑𝑥𝑎 𝐴 0 𝑟 𝑅𝑤 𝑞𝑤 ,V𝑎 𝑤 𝑊𝑟 𝑅𝑤𝑓𝑟𝑤 0, 𝑤 𝑊𝑤𝑓𝑟𝑤 𝛿𝑎𝑟, 0, if 𝑓𝑟𝑤 0, 0, if 𝑓𝑟𝑤 0, 𝑟 𝑅𝑤 ,(10)𝑤 𝑊.𝑤means the travelIn formula (10), 𝑐𝑟𝑤 (f ) 𝑎 𝑡𝑎 (V𝑎 )𝛿𝑎𝑟time of route 𝑟 in the OD pair numbered 𝑤. 𝜋𝑤 (f ) min{𝑐𝑟𝑤 (f ), 𝑟 𝑅𝑤 } means the minimum travel time ofroutes between the OD pair numbered 𝑤. 𝑎 𝐴 𝑟 𝑅𝑤 , 𝑤 𝑊.Variables of capacity expansion in upper-level model arenecessary to solve lower-level model. Thus, upper-level mathematical model is not a linear optimization model, whichis hard to solve by traditional integral equation methodas least square method. Genetic algorithm (GA) does notdepend on gradient information and experiential knowledgeand is able to find global optimum. And, hence, Yin usedgenetic algorithm to solve network design problem, andintroduced bionic mechanisms such as simulated annealing,ants feeding, and particle swam preying to improve thelocal search ability of simple genetic algorithms [12]. However, the improved genetic algorithm has disadvantages ascomplicated structure or large calculation, which may causeinefficiency and poor portability. Considering nonlinearityand nonconvexity of bilevel expansion models, this paperintroduces the golden ratio to integrate with an improvedgenetic algorithm to solve upper-level model, and the classicFrank-Wolfe algorithm is used to solve lower-level model.4.1. Frank-Wolfe Algorithm. Use Frank-Wolfe algorithm tocalculate the lower-level model under fixed OD traveldemand. Main steps are as follows [13].(6)Step 1 (initialization). Set the iteration number 𝑛 1 and finda feasible traffic mode {V𝑎(1) }.(7)Step 2 (update the travel time). Calculate 𝑡𝑎(𝑛) 𝑡𝑎 (V𝑎(𝑛) ), 𝑎 𝐴.(8)Step 3 (find direction). According to 𝑡𝑎(𝑛) , use all-or-none(AON) algorithm to get the auxiliary flow collection 𝑦𝑎(𝑛) .V𝑎𝑓𝑟𝑤𝑐𝑟𝑤 (f ) 𝜋𝑤 (f ) {4. Solution Algorithm 𝑔𝑎 (𝑢𝑎 ) 𝐵0 𝑢𝑎 𝑢𝑎max ,(1)minimum travel time, the route traffic is more than zero; thatis to say, this route is occupied:(9)Formula (6) describes the assignment problem of Wardrop user equilibrium (UE). Formula (7) meets the needof the conservation of traffic flow. Formula (8) shows therelationship between section and route traffic. Formula (9)describes the nonnegativity of route traffic. The optimalsolution f (. . . , 𝑓𝑟𝑤 , . . . )𝑇 meets the user equilibrium condition as in formula (10). When the travel time of route 𝑟 ismore than or equal to the minimum travel time, the routetraffic is zero. When the travel time of route 𝑟 is equal to theStep 4 (displacement distance). As in formula (11), finda better 𝛼(𝑛) along the direction of the objective functionminimized:min V𝑎(𝑛) 𝛼(𝑛) (𝑦𝑎(𝑛) V𝑎(𝑛) )𝛼(𝑛) 𝑎 𝐴 0𝑡𝑎 (𝑥, 𝑢𝑎 ) 𝑑𝑥.(11)Step 5. Update road traffic network flow, which is to calculatenew traffic volume in links as in the following formula:V𝑎(𝑛 1) V𝑎(𝑛) 𝛼(𝑛) (𝑦𝑎(𝑛) V𝑎(𝑛) ) , 𝑎 𝐴.(12)

4Computational Intelligence and Neuroscience AC CACB CB 0.618 C C C B 0.618Figure 1: The searching of the opposite golden ratio based localpositions.Step 6 (judge the end condition). If the algorithm reaches thespecific judging criteria (such as maximum iterations), endthe Frank-Wolfe algorithm. Otherwise 𝑛 𝑛 1 and returnsback to Step 1.4.2. Golden Ratio-Based Heuristic Genetic Algorithm. Agolden ratio-based heuristic genetic algorithm (GRGA) hasbeen proposed to yield approximate solutions for expandedcapacities of urban road network [14]. The proposed heuristicis able to find the closest solution to the best solution byintroducing golden ratio (GR) to enhance the local optimalcapability of an improved real-coded genetic algorithm [15].(1) Golden Ratio Based Local Search. When genetic algorithmscome to the later evolution process, individuals of thepopulation might trap into local minima especially for theoptimization problems with a big problem space and manyminima. Hence, it is more possible that the fitness valuerelated to the current individual is lower than the randomsearch, and it can be expected that two individual neighbors,which are different from each other in the topology, arelocated in the same concave in the searching space. There arepotential genes between the two closest individual neighborswhich have lower fitness value than these two individuals.In recent years, the golden ratio has also been applied tooptimize timings of traffic signal systems with good results[16]. Here, the golden ratio is introduced to find the genes ofthe local search position. As in Figure 1, Point 𝐴 and Point𝐵 are two adjacent individual neighbors, and Point 𝐶 is thepotential local position determined by the golden ratio of𝐴 and 𝐵; that is the relationship between the segment 𝐴𝐶and the segment 𝐴𝐵 satisfies the golden ratio definition.In addition, to expand the local searching area around thecurrent individual positions during the whole searchingprocess, the local position Point 𝐶 can also be determinedby the opposite golden ratio as the opposition concept hasbeen used in evolution optimization algorithm and goodperformance was obtained. Here, the concept of the oppositegolden ratio is to rotate the Point 𝐶 by 180 degrees, and therelationship between the segment 𝐶 𝐶 and the segment 𝐶 𝐵still meets the golden ratio definition.(2) Decoding of Decision Variables. Decision variables ofexpanded capacity in the upper-level model are consideredas an individual. Thus, the chromosome of individuals canbe expressed by a vector of decision variables, denoting byu (𝑢𝑎1 , 𝑢𝑎2 , . . . , 𝑢𝑎 𝐴 ). Here, the 𝐴 is the total number oflinks with expanded capacity.(3) The Hybrid Genetic Algorithm Integrated with GoldenRatio. The hybrid genetic algorithm integrated with goldenratio (HGAGR) has been developed to obtain optimal solutions for the expanded capacity of available links in theurban road network. The process of the HGAGR is shown inFigure 2.Step 1 (initialization). Initialize the HGAGR parameters,including population size 𝑀, evolution generation Gen, GRlocal optimum size 𝑚, and the excellent subpopulation size𝑀𝑠. The cross rate and mutation rate are adaptive to thegeneration and fitness value. Then, generate the real-codedinitial population that meets the constraints in formula (5)and the principle of having individuals different from eachother.Step 2 (fitness evaluation). According to the expanded planof each individual 𝑋, the OD of a specific network isreassigned by Frank-Wolfe algorithm and then calculates thetotal network travel time (𝑍) by formula (1), and then thefitness value of this individual is computed in the followingformula:𝑓 (𝑍) 1.1 𝑍(13)Step 3 (selection). Use the roulette wheel selection.Step 4 (crossing). Use the nonuniform arithmetic crossoveroperator.Step 5 (mutation). Use the nonuniform mutation operator,by which the degree of mutation is still adaptively adjustedwith the generation and fitness value. Denote 𝑈𝑖𝑛𝑘 as the 𝑖thgene on chromosome 𝑘 to be mutated; then descendant 𝐶𝑖 𝑛𝑘is computed in the following formula:𝐶𝑖 𝑛𝑘 {𝑈𝑖𝑛𝑘 Δ (𝑡, 0 𝑈𝑖𝑛𝑘 ) ,𝑈𝑖𝑛𝑘 Δ (𝑡, 𝑈𝑎max 𝑈𝑖𝑛𝑘 ) ,if 𝛾 0,if 𝛾 1, (14)𝑏while, Δ (𝑡, 𝑦) 𝑦 (1 𝑟1/(1 𝑛/Gen) (1 𝑓 (𝑍)/𝐹max ) ) .In formula (14), 𝛾 is a 0-1 variable; 𝑓 (𝑍) is the fitness ofindividual, 𝐹max is the maximum fitness in cur-generation, 𝑟is a random number within [0, 1], and 𝑏 is a genetic parameterto control the degree of dependence on fitness; here 𝑏 is 0.5.Step 6 (elitist strategy). Replace the worst individual incurrent-generation with the best one in parent generation.Step 7 (golden ratio-based local optimization). To increasethe population diversity, choose the best 𝑀𝑠 individuals inthe above improved real-coded genetic algorithm to generatean excellent subpopulation, and select the best 2𝑚 individualsrandomly from this subpopulation as initial vector; thenconduct the local optimization of the IRGA via the followinggolden ratio operator.(1) Denote the excellent pair of individuals as 𝐴 and 𝐵,respectively, and generate new individuals (𝐶 and 𝐶 )by the function of GR as in Figure 1.(2) Evaluate each new individual by Step 2.

Computational Intelligence and Neuroscience5Start (problems)Parameter initializationPopulation initializationYesMeet the terminationprinciple?NoThe best solutionFitness calculation:store-and-forwardbased delay modelG G 1Output performanceand resultsSelectionCrossingLocal optimization via GRMutationEnd (improve or solve thepractical issues)Produce new individuals via GR statefunctionsCalculate fitness value of newproduced individualsAccept new individuals viametropolis principleG: current generation numberGen: maximum generation numberFigure 2: Golden ratio based hybrid genetic algorithm.(3) Select these new generated individuals by metropolisprinciple. The acceptance probability of individual𝑋(𝑃(𝑋)) is calculated by formula (15), in which 𝑃(𝑋)increases parallel with the evolutional generation andfitness value to approximate the better solution inaccelerating convergence; that is, the HGAGR givesmore belief on local optimization in later evolutionprocess: 𝛼(1 𝐺 𝑓(𝑍)/Gen)𝑃 (𝑈) 𝑒.(15)In formula (15), 𝛼 is the proportional coefficient thatcontrols the dependent degree on the evolutional generation;here 𝛼 is 0.6.(4) Replace the current-generation worst individuals ofthe IRGA by those selected new individuals and thengo to Step 8.Step 8 (judgment of termination principle). If 𝑛 Gen, go toStep 2. Otherwise, output the best solution and the value ofevaluation indices.5. Numerical Analysis5.1. Case Description. Use the Suwansirikul one-way networkverification to establish the bilevel programming and solve3142Figure 3: Suwansirikul one-way network.the algorithm [17]. As is shown in Figure 3, the networkcontains an OD pair. The traffic flow from node 1 to node4 is 60; 𝑞14 60. The values of free flow travel time 𝑡0 ,section capacity 𝑐𝑎 , and capacity expansion cost coefficient 𝜏𝑎are shown in Table 1. The impedance function used is BPRimpedance function, whose 𝛼 equals 0.15 and 𝛽 equals 4. 𝛾in the objective function is 1.5. The value range of expandedcapacity is [0, 30].The parameter settings of the HGAGR are as follows: population size 𝑀 50; generation times Gen 100; golden section optimal algorithm 𝑚 6; subpopulation size 𝑀𝑠 3𝑚;dependence of evolution algebra 𝛼 0.6; dependence ofindividual fitness 𝑏 0.5.

6Computational Intelligence and NeuroscienceTable 1: Section attribution, objective function, and impedancefunction.Section𝑡0𝑐𝑎𝜏𝑎1 21 32 43 23 in𝑍 𝑡𝑎 (V𝑎 , 𝑢𝑎 ) V𝑎 1.5𝜏𝑎 (𝑢𝑎 ) ,𝑢Impedancefunction𝑎 𝐴𝑡𝑎 𝑡0 [1 𝛼 (𝛽V𝑎) ],𝑐𝑎 0.9𝑎 𝐴𝑎 𝐴5.2. Result Analysis(1) Capacity Expansion of Suwansirikul Road Network. FlankWolfe algorithm is used to divide the specified OD capacityinto each link section in the lower-level model. Then HGAGRare used to calculate the expanded capacity in the upperlevel model. The statistics result of flow of each section V𝑎 ,section saturation V𝑎 /𝑐𝑎 , and network total travel time, underthe circumstance of equalization 𝑇all 𝑎 𝐴 𝑡𝑎 V𝑎 , are shownin Table 2.It shows that the capacity expansion is not significantcompared to the SN. The reasons are as follows. (1) The trafficdemand of former SN is small. In the state of equilibrium,the saturation of each section satisfies the network designlevel. The saturation of all sections are less than 1. (2) TheLagrangian multiplier 𝛾 is too large, which leads to the highcost of improving total travel time.(2) Influencing Factors Analysis. With the increase of trafficdemand, network capacity needs expanding [18]. To modelthe real network environment, this paper firstly increases thedemand of the SN by 𝑞14 120 and gets the new Suwansirikulnetwork with increased demand (SND). Then the expendedcapacity of the SND is reoptimized with 𝛾 0.03. Calculationresults of two scenarios are shown in Table 3. In the SND,the network capacity of each section has increased to meetthe need of travel demand, but the sections are still in a stateof saturation. As the difference of 𝛾 and the cost of capacityexpansion is too large, the cost of traffic congestion is higherthan the cost of increasing the capacity when the system isoptimal. As 𝛾 0.03, the cost of capacity expansion maybe reduced, and the saturation of each section will improve.With the limited budget and increased travel demand, thetraffic condition can be improved by expanding the networkcapacity. Supposing the capacity of each road is 20 pcu, onthe basis of the expanding capacity of sections 42 and 43, oneroad should be added between section 42 and 43, in order tokeep the whole network in high service level.(3) HGAGR Algorithm Performance. The convergence curvesof the HGAGR under three conditions are shown in Figure 4.The HGAGR converges quickly in first 10 iterations. Theobjective function value significantly reduces. Then the convergence speed is getting lower and there are few fluctuationsof the best fitness values after 50 iterations. During the processof the optimization, the average fitness of the population isfluctuating because of the golden ratio based local search ofthe HGAGR. The average computation time of the solutionalgorithm is 122 s, which satisfies the real-time demand ofroad network evaluation.6. ConclusionNetwork capacity represents the level of road network construction and reflects the level of service of the existing roadinfrastructures. Thus, it is an important decision variableto determine the saturation level, potential capacity, andbottlenecks of existing road network. Aiming at crucialissues of capacity expansion of road network, this paperemployed the bilevel mathematical programming modellingfor the capacity expansion in the continuous network designproblem. To improve the local search ability of simple geneticalgorithms, a golden ratio based hybrid genetic algorithm wasdeveloped to solve the upper-level model of expanded capacity, and the lower-level model was solved by the classic FrankWolfe algorithm. Three numerical analyses on Suwansirikulnetwork indicate the following.(i) For capacity expansion, urban road saturation (V/𝑐) isa key parameter to evaluate the level of road service.When the road saturation is over 0.9, these saturatedroads become bottleneck sections. To meet increasingtraffic demand, reconstruction of road facilities isnecessary; that is to say, for bottleneck sections,increasing link capacity with building new lane ornew link can balance traffic distribution in wholenetwork with better use of total network capacity.(ii) For the algorithm performance, the proposedHGAGR is more time-efficient because of less calculations and simpler convergence condition. Thegood performance of the proposed model alsoindicates that the HGAGR has the potential infinding reliable solutions with golden ratio basedlocal search around the excellent individuals, insteadof random search. Therefore, the design of theimprovement measures used to enhance the localsearch capacity of simple genetic algorithms will be acritical operational issue.NotationsList of Key Variables Used in the Network Capacity Models𝐴: Set of links in the network𝐴: Set of links with the expanded capacity inthe network 𝐴 : The total number of links with theexpanded capacity𝑊: Set of OD pairs. For each OD pairnumbered 𝑤, 𝑤 𝑊𝑅𝑤 : Set of routes between the OD pairnumbered 𝑤. For each route 𝑟, 𝑟 𝑅𝑤

Computational Intelligence and Neuroscience7Table 2: Capacity expansion of Suwansirikul road network (𝑞14 60, 𝛾 1.50).Section1 21 32 43 23 4𝑇all 𝑡𝑎 V𝑎𝑎 𝐴min𝑍 𝑇all 𝛾 𝑔𝑎 (𝑢𝑎 )𝑢𝑎 𝐴 NetworkSN ESN 16.965132.184332.1759𝑐𝑎3030 0.13885050 0.21183030 0.27942020 0.02204040 0.2333V𝑎 70.34790.80460.7997589.7041588.4805—589.0714SN: Suwansirikul network; ESN: expanded capacity based Suwansirikul network.Table 3: Capacity expansion of Suwansirikul network with increased demand (𝑞14 120).Section1 21 32 43 23 4𝑇all 𝑡𝑎 (V𝑎 , 𝑢𝑎 ) V𝑎𝑎 𝐴min𝑍 𝑇all 𝛾 𝑔𝑎 (𝑢𝑎 )𝑢𝑎 𝐴 ESND 𝛾 1.5𝛾 0.03𝛾 1.5𝛾 0.03𝛾 1.5𝛾 0.03𝛾 1.5𝛾 0.03𝛾 1.5𝛾 0.03𝛾 1.5𝛾 0.03𝛾 1.5𝛾 �𝑎 𝑢𝑎30 3.403030 24.191750 3.660750 25.054830 4.856330 27.246820 0.009920 1.046540 4.553840 25.68112108.81274.12316.71431.1ESND: expanded capacity based Suwansirikul network with increased demand.𝑓𝑟𝑤 :Flow volume of route 𝑟 between the ODpair numbered 𝑤f:Route flow volume vector𝑇f (. . . , 𝑓𝑟𝑤 , . . .) in the lower modelLink flow volume, 𝑎 𝐴V𝑎 :v:Link flow volume vector v (. . . , V𝑎 , . . . )𝑇in the lower modelTop decision variables of the expanded𝑢𝑎 :capacity of link 𝑎, 𝑎 𝐴The upper limit of the expanded capacity𝑢𝑎max :of link 𝑎, 𝑎 𝐴u:The expanded link capacity vector in thetop model (𝑢𝑎1 , 𝑢𝑎2 , . . . , 𝑢𝑎 𝐴 )𝑡𝑎 (V𝑎 , 𝑢𝑎 ): Travel time of link 𝑎 𝐴, which is anequation of link flow volume andexpanded link capacity𝑐𝑟𝑤 :Travel time of route 𝑟 between the OD pairnumbered 𝑤𝜋𝑤 :Minimum travel time between the ODpair numbered 𝑤Traffic demands between the OD pair𝑞𝑤 :numbered 𝑤q:Vector of demands between all OD pairs(𝑞1 , 𝑞2 , . . . , 𝑞𝑊)𝑔𝑎 (𝑢𝑎 ): Cost of the expanded link capacity, 𝑎 𝐴𝑤𝛿𝑎𝑟:𝐵:If link 𝑎 is included in route 𝑟 between theOD pair numbered 𝑤, it equals 1,otherwise it equals 0Fixed investment budget of networkcapacity expansion.V𝑎 10.55901.43020.9224

8Computational Intelligence and Neuroscience310020003000Fitness valueFitness 0405060Generation70809001001020(a) ESN with 𝛾 1.530405060Generation708090100(b) ESND with 𝛾 1.515601540Fitness 0GenerationBest fitnessAverage fitness(c) ESND with 𝛾 0.03Figure 4: Convergence curves of the HGAGR.Conflict of InterestsThe authors declare that there is no conflict of interestsregarding the publication of this paper.AcknowledgmentsThe work of this paper is supported by National ScienceFoundation of China (Project no. 50408034). The authors aregrateful to

the constraint condition of the capacity of road network. An advanced bilevel tra c assignment method was proposed, which considered not only the physical capacity of road network, but also the balance among tra c individuals [ ]. e study o ers a new method to calculate the road network capacity model. Despite the promising progress from .