Constrained Newton Methods for Transport Network Equilibrium Analysis

TSINGHUA SCIENCE AND TECHNOLOGYISSN 1007-0214 14/16 pp765-775Volume 14, Number 6, December 2009Constrained Newton Methods forTransport Network Equilibrium Analysis'CHENG Lin (程琳)", xU Xiangdong (许项东), QIU Songlin (邱松林)School of Transportation, Southeast University, Nanjing 210096, ChinaAbstract: A set of constrained Newton methods were developed for static tafflcf assignment problems. TheNewton formula uses the gradient of the objective function to determine an improved feasible directionscaled by the second-order derivatives of the objective function. The column generation produces the activepaths necessary for each origin-destination pair. These methods then select an optimal step size or make anorthogonal projection to achieve fast, accurate convergence. These Newton methods based on the con-strained Newton formula utilize path information to explicitly implement Wardrop's principle in the transportnetwork modelling and complement the traffc assignment algorithms. Numerical examples are presented tocompare the perfomance with all possible Newton methods. The computational results show that the opti-mal-step Newton methods have much better convergence than the fxed-step ones, while the Newtonmethod with the unit step size is not always eficient for trffic assignment problems. Furthermore, the opti-mal-step Newton methods are relatively robust for all three of the tested benchmark networks of traffic as-signment problems.Key words: taffic assignment; network flow; Newton method; column generation; line searchdestination. This rule implies that at equilibrium theIntroductionpath flow patterns are such that the travel times on allthe used paths connecting any given OD pair will beTraffic assignment models deal with the problem ofequal and that the travel times on all the used pathsassigning vehicular trips to a transport network, givenwill be less than or equal to the travel times of any un-an origin-destination (OD) trip matrix and the networkused paths. The network is then in user equilibriumcharacteristics. The transport network is represented by(UE) with no user able to reduce their travel time bya directed graph where each link is associated withunilaterally changing pathsl'.a link performance function, typically the travel time.The state of the art in taffic assigoment solutionsThe traffic assignment model is based on thebehavioural assumption that each user travels onhas evolved around two major directions,“link-based"and“patb-based" methods. With the link-based meth-the path that minimizes the travel time from origin toods, the paths are not conserved at each iteration, suchReceived: 2008-10-20; revised: 2009-06-09as in the Frank-Wolfe algorithm4 and restricted sim-* Supported by the National Naural Science Foundation of Chinaplicial decomposition5. The path-based methods are(No. 50678037), the National Key Basic Research and Developmnentpath-enumeration algorithms where all the used paths(973) Progam of China No. 206C70550), and the Nationalare sto中国煤化Tiectont, disag'High-Tech Research and Develpment (863) Program of Chinagregatoand gap func-(No. 20A112052)5** To whom correspondence should be adressed.YHcNMHGebetwentheseE-mail: GlSt@secu.edu.cn; Tel: 86 25- 83795649two kinds of methods is that the optimization in the766Tsinghua Science and Technology, December 2009, 14(6): 76-775link-based methods is performned in the link-flow do-has a given tafic demand qw The user equilibriummain, while that of the path-based methods is per-assignment problem is stated as follows.formed in the path-flow domain.min z(x)=Zj。 t。(s)ds(1a)The by-product of path-based methods is the abun-dant information on the path flow patterns at user equi-s.t.2 f"=q, Vw∈W(1b)librium. As is well known, the path flow pattern is notunique at user equilibrium'", but it is used in variousx=E 2 f".8, VaEA(1c)applications. For example, a path flow solution istypically used for real-time assignments, which is notf"≥0,Vk∈Kw, w∈W(1d)possible with the link-based Frank-Wolfe algorithm, inwhere xa is the link flow. ta is the travel time on link a.advanced traveller information systems or advancedδ%=| if link a belongs to path k; otherwise, 8k =0.traffic management systemslto. Sensitivity analysesl"f" is the flow on path k within OD pair w. Kw is the setrequire a set of reference path flows, from which a par-of paths within OD pair w. qw is the origin-destinationticular path flow patterm can be extracted. The Newtondemand between pair w.methods can be used to provide reference path sets forThe user equilibrium assignment problem is path-such flow sensitivity analyses. The path solution isformulated due to the constraints of Eqs. (lb)-(1d).related to a class of bilevel problemstas which uses theAltermatively, the same problem can be formulatedsensitivity of the link flow to the OD demand. Whenusing link variables indexed by origin or destination'!.path travel costs are nonadditive or nonlinear's, linkThis paper focuses on the formulation using path vari-flows can not be used alone to formulate and solve theables. Consistent with the necessary and sufficienttraffic assignment. Thus all of these types of problemsconditions of optimality, the equilibrium condition forneed a method to explicitly formulate and solve theeach OD pair is stated asproblem in the path flow domain.Zo.8x=i; if">0)This paper presents constrained Newton methods forVk, wsolving path-formulated static traffic assignment prob-Zt&≥i if" =0|lems. Column generation, orthogonal projectiont orine searchl4 can be incorporated into the solutionwhere r = min{t.δ%x} is the shortest path travelprocedure. With column generation, the active pathstime within OD pair w, equal to the Lagrange multi-joining each OD pair are generated only when needed.plier at this point of Eq. (lb) at the optimal point.The line search or orthogonal projection methods areThe solution of the UE assignment model can beused to avoid infeasible flows on the used paths and tocharacterized by Wardrop's principle. Specifically, forequilibrate the demand among the active paths as wella given path k connecting origin-destination pair w, theas the newly found shortest path for each OD pair.condition holds two possible combinations of pathThese methods are called constrained Newton methodsflow and travel time. Either the flow on the k-th path isbecause they extend the Newton formula over the re-zero, where the travel time on the path, 2。t.8x ,striction condition of the origin-destination demandconservation. The methods are fast and accurate bumust be greater than or equal to the OD pair specificneed to save and utilize the path information.Lagrange multiplier, w or the flow on the k-th path ispositive, where E。.8 =t. In any event, the La-1 Path-Formulated User Equilibriumgrange multiplier of a given OD pair in Eq. (lb) is lessAssignmentthan or equal to the travel time on all paths connectingGiven a transport network G(A, N) where A is the setthis pair; hence Tw equals the minimum path travel timeof links and N is the set of nodes, each directed linkwithin OD pair w.aeA is associated with a positive travel time t(xa)中国煤化工lethodswhich is an increasing function of the link flowxa. WY片CNMHGis the set of origin destination pairs and each pair w∈W In unconstamnea mumizaon, une optimization canCHENG Lin (程琳) et al: Constrained Newton Methods for Transport Network Equilibrium Anabysis767reach the bottom of the objective function where theFor path flows, the objective function, z(x), in Eq.gradient vector has all zero components. In a constrained(1a) is approximated by the following second-orderminimization problem such as traffic assignments,Taylor series:however, all of the gradient components do not vanishz(f)≌z(f")+(f-. f{")"'t(f"')+at the minimum. Figure 1 shows a traffic assignment(f-f0)"+'(f").(f-f")objective function defined over a feasible region in thepath flow domain. The shadow area in Fig. 1 denoteswhere r(f(") denotes the vector of path costs andthe feasible region. When the minimum is on ther'(f{") denotes their deriatives, which are the firstboundary of the feasible region, the gradient is eitherand second order derivatives of the objective functionequal to or greater than a constant for each OD pait,with respect to the path flows. f(") is the vector ofcompatible with Wardrop's principle. Since the gradi-current path flow solutions. The minimization is thenent of the objective represents the vector of path travelperformed on an approximate function. The frst de-times in the path flow domain, then this constant forrivative of the approximate function iseach 0D pair is probably equivalent to the shortestt()=(f")+(f- f{)y".r(f")=path time within the pair. The non-uniqueness of thepath flows make the feasible region changeable withr(f")+ Af".r'(f")(5)respect to the path flow vector. However, the unique-The improved increment along the path flow domainness of the path time vector could be used to find ais then:descent direction in path-based methods, therefore,Af(") ={r(f")- <()}[(f{")J'6)improving the solution eficiency through utilization ofFor convenience of expression, the active paths aresecond-order information in the objective function.partitioned into the shortest path, k"， and thenon-shortest paths, k∈Kw, for any pair w∈W. Near theoptimum, the flows on all the non-shortest paths willdecrease according to the direction expressed by Eq.(6). The decreased flows on the non-shortest pathswithin each OD pair will then shift to the correspond-ing sbortest path. The shortest path, k~, if not in-cluded in the current path set, will join the path setK{") at the next iteration, ie, K(* = K(") uk".Fig. 1 Optimum of capacitated UE assigomeatSince the flow must be conserved for every OD pair,the sum of the reduced flows will be equal to the in-The current method relies on only the used elementscreased flow on the shortest path or will be equal to thewith path flow vector with an iterative solution to thepath flow on the shortest path if the shortest path hadproblem in Eq. (1) to move from one feasible point tono flow since it was just found. The flow change in Eq.an improved feasible point. Given a feasible point,(6) in the used paths can also be expressed bypath flow vector f("), a moving flow 4f() and a4f(")=H(f{")-tUfg)-J]-[t'(f")~' (7a)step size h are determined such that the following twowhere I is a vector having the appropriate dimensionproperties are true:with the elements all being unity and t(f") repre-●f(")+.4f'") is feasible.●The value of the objective function afsenting the cost of the shortest path k for pair w.f'() +a.0f() is better than thatat f'").The flow or flow change on the shortest path can thenbe calculated byThis leads to a new point,中国煤化工Vw∈W (7b)fin = f0 +不.4f)(3)The process is repeated until the objective functionftl.MYH.CNMHGetweenpatsbecannot be further improved.longing to a currently used path set, the flows on some768Tsinghua Science and Technology, December 2009, 14(6): 765-775paths may become negative, which is not allowed inshortest paths with its diagonal elements beingtraffc assignment problems. The first feasibility in02z(f)2'8-8)， Vk*k,Vw (8)Eq, (3) for a new point can be satisfed in two ways as(0f")follows.where r denotes the derivative of the travel time(1) If the fixed step strategy results in infeasible pathfunction for link a.flows, an orthogonal projection is made on the con-The path flows on the non-shortest paths will alwaysstraint boundaries of Eq. (1d) by setting the negativedecrease as the flow decreases on the non-shortestpath flow to zero. This fixed-step strategy is also re-paths in each OD pair shifting to the correspondingferred to as the gradient projection (GP) method4.sshortest path. However, the amount of flow for eachwhen the step size A equals one.path has to be controlled to avoid negative path flows.(2) In contrast to the fixed step strategy, the currentIn the path flow domain, if the flow movement stepstrategy employs an optimized step size, subject tosize is predetermined, a simple scheme is to set nega-various constraints. For example, the step could betive path flows to zero whenever the movement resultslimited by the non-negativity of the link or path flowsin an infeasible solution. This operation is usuallyor the optimal link flows.called an orthogonal projection expressed asBoth strategies can be viewed as constrained New-*(t)=U5“("*+f"}'，Vk∈Km, k≠k° (9)ton methods because both use the extended Newtonformula in Eq. (6), where the feasible decent directionwhere [] is the orthogonal projection operator andis not only modified by information for the latestn is the number of iterations.shortest path but also scaled by second- order informa-The occurrence of orthogonal projection is deter-tion in the objective function (called the scaling ma-mined by the size of the predetermined step. Previoustrix). Both make successive moves towards the mini-algorithmss,151 used a similar method but with a step ofmum of the quadratic approximation of the objectiveunity, called the GP algorithm. The GP algorithm is afunction by shifting flows from the used paths on thespecial case of the Newton methods with fixed steps.particular OD pair to its shortest path. The flow incre-Their experience showed that a step size,的equal to 1ment guarantees that the second property that the ob-achieved a very good convergence rate when the flowjective function at f(on) +小△f(n) is better than that atupdate equations used automatic scaling based on thesecond derivative informnation. The effectiveness of theGP algorithm excellence is atributed to the manipula-The movement direction expressed by the first termtion of the orthogonal projection as examined in manyin the right hand side (RHS) of Eq. (6) is determinednumerical tests',16,1]according to Eq. (7), the critical steps become how toThe GP algorithm has many advantages over othercalculate the scaling matrix expressed by the secondalgorithms[16.17]due to the projection procedure. How-term in the RHS of Eq. (6) and how to decide the stepever, the orthogonal projection is not always guaran-size expressed in Eq. (3).teed by the constant step size of unity. An example2.1 Newton methods with fixed stepsgiven later shows that the Newton method with a stepsize of unity yields poor convergence if no projectionThe directional step provided by the gradient in Eq. (7a)occurs. Thus the constant step size has to be carefullyhas to be scaled to coordinate the directions of the pathselected to guarantee the occurence of the orthogonalflows within the OD pair, as well as the directionsprojection.among different OD pairs expressed by the secondterm on the RHS of Eq. (7a). The scaling is determined2.2 Newton methods with optimal stepsby the derivative of the path costs, which is the diago-The weakness of Newton methods with fixed steps cannal Hessian matrix of the objective function in Eq. (1a)e ovenirad If an optimal stepdue to the assumption that the path selection for dif-size is中国煤化工lods, the elementsferent OD pairs is not related. The Hessian is definedof theYHCN M H G to be calculatedin the domain of the used paths not including theprecisely as in Eq. (8). The diagonal elements of theCHENG Lin (程琳) et al: Constrained Newton Methods for Transport Network Equilibrium Analysis769Hessian matrix can be approximated by the OD de-mand or path flow to reduce the overhead associatedwith calculating the second derivatives of the objective(12b)function. The approximate diagonals of the HessianThe optimal step size for link flows may be calcu-matrix can be expressed aslated by solving the equationz'(x)=0. The step sizes(g.)"， Vk, Vw, if approximnatedfor each link flow must be coordinated and not larger2z(0)一by the OD demand;than Ahpatb. Therefore, the feasible link flow step should(0f")(")", Vk, Vw， ifapproximnated bysatisfythe path flowx≌min(12c)(10)Either a fixed or optimal step can be applied if the.3 Discussion of Newton methodsflow update equations use automatic scaling based onthe second derivative information. However, if theTwo strategies with fixed or optimal steps are pre-Hessian matrix is approximated, a step size of unitysented for Newton methods in Eqs. (3) and (7). Themight not be appropriate, but should be modified basedfirst strategy uses a fixed step and requires the calcula-on decision variables not being negative or on a linetion of the Hessian matrix. When the move towards thesearch.minimum in the negative gradient direction results inThe non-negativity of the path flows requiresan infeasible solution, the direction has to be projectedf"+h.4f,"≥0, Vk∈K, w∈W (11a)onto the feasible region. The proection operation maywhich is rewritten asresult in rapid changes to the demand conservation≤-Vk∈K, w∈W(11b)conditions and allow moves towards the minimumAf"’along the face of the feasible region of the path flowThe step sizes for the flows on every path must be COo-variables. However, although experiences16.17 hasordinated so the optimal step size for all paths mustshown that a step size of unity works very well, thepredetermination of the proper step size is not easy forsatisfy the following relationship.all types of the networks. Traffic practitioners some-_L=min|Af"|45"<0(1| (1l)times have to try various steps to realize an acceptableconvergence ratio. Also there is no theoretical assur-Then, the step size required by the link flows can beance that projection always occurs with a unit step size,determined using mathematical programming. Thesince moves towards the minimum may not result insecond-order approximation of the objective functionthe infeasible solutions so projection will not occurcan be expressed aswhich will hurt the convergent ratio.z(x)≈z(x0)+ A.QxT●z(x")+To overcome the weakness of the Newton methodsx2.OxT o2(x)-.x')(12a)with fixed steps, the second strategy introduces an op-timal step size with the requirement of non-negativitywhere h is a feasible step size, Ox is the vector of theof the decision variables or line search. The optimalincreased link flows, and z' and z" are the first andstep size gives fast convergence as the gradient projec-second order derivatives of the objective function (5a).tion method'. In most situations, traffic practitionersSubstitutingare accustomed to calculating the gradient Vz(f) butAx(0) =A.Of(n(Incidence relationship for movingnot the Hessian V2z(f) of the objective function.flows between a link and a path)However, the Hessian can usually be approximatedandusing. the origin-destination demand or path flowz"(x)=t'(Second derivatives of thewitho中国煤化工terations. The ap-function)proxiM.C N M H G then compensatesinto Eq. (12a) givesfor the expense oI calcuaung une optimal step.The approximate Hessian is not appropriate for770Tsinghua Science and Technology, December 2009, 14(6): 765-775Newton methods with fixed steps, but either a precisemethods. The actual nature of the objective functionsor approximate Hessian can be used in the optimal-stepand the constraints in the network assignment can bestrategy. The combination of a scaling matrix and aquite different.variable step size gives constrained Newton methodsfor taffic assignment problems for a systematicframework as ilustrated in Fig 2. Additioally, unlikethe Frank-Wolfe methodl2l or the simplicial decompo-sition method!', the Newton methods take advantageof the availability of information in the second-order(a) Newton method(b) Newton methodwith a fixed stepderivative of the objective function and column gen-with projctionwith no projectioneration! to achieve superior convergence and accu-racy. The following shows the superiority of the gra-dient projection (or the Newton method with a stepsize of unity)0D demand(C) Newton methodwith an optimal stepPath flowOptimalFig.3 Grapbical image of the Newton methods'convergenceThe second-orderFixedderivative3 Solution ProceduresScaling matixStep sizeFig. 2 Framework for Newton methods with a nega-Various Newton methods have been developed to solvetive gradient directionthe user equilibrium taffic assignment. The NewtonThe differences between the various Newton meth-algorithms generally consist of initialization, columnods can be ilustrated by the qualitative graphicalgeneration, equilibration, and convergence procedures.comparison in Fig. 3. If the predetermined step is ap-Column generation includes finding the shortest pathspropriate, orthogonal projection will occur and theand augmenting the path set, while equilibration in-Newton methods will move toward the minimum alongcludes implementation of the constrained Newtonthe face of the path-flow region. Computational ex-formula to update the traffic flows. The differencesperience indicates that the Newton method with a unitybetween various Newton methods lie only in thestep size outperforms other types of algorithms when-equilibration with strategies using fixed or optimal stepever projection occurs once or twice. However, if thesizes combined with the actual Hessian matrix orprojection does not occur, the fixed-step Newtonan approximate matrix. The algorithm steps are asmethods move in directions that are almost orthogonalfollows.to the negative gradient direction. In such cases, theInitializationiteration always moves to the optimum along the inside●Set iteration counter n=0.region in a zigzag patterm, similar to the successive●Solve the shortest path problem and create an ini-iterations of the Frank Wolfe methodl2. In contrast totial pathset K(0)， Vwe W.the fixed-step Newton methods, the optimal-step●Perform All-or-Nothing assignment and obtain theNewton methods optimize the step size in the descentinitial path and link flow.direction when they are close to the optimum. TheColumn generationperformance of the optimal-step ones is competitive, Increment the iteration counter: n: an+1.with the GP algorithm as the optimal-step Newton中国煤化工the shortest pathmethods move along the scaled descent directionwithin the inside region. This example ilustrates theMYHCNMH Ghs Kor and aug-qualitative reasons behind the performance of Newtonment the path set.CHENGLin (程琳) et al: Constrained Newton Methods for Transport Network Equilibrium Analysis771Set K{")=K{1uk{)", if k(m K(~n); other-find the total flow on each link, calculating the first-wise,set K() = K(m-).order derivatives for all the patbs between each ODpair, finding the second-order derivatives for each pair,Equilibration●Calculate the move direction for the path flowand finding the optimal step size for both path and linkflow movement for each iteration. With the opti-vector.●Update the used path flows using the Newtonmal-step Newton methods, the second-order deriva-tives can be readily approximated by the ori-methods with fixed or optimal step sizes.●If f"=0, drop path k: K{("=K({"\k. Heregin-destination demand or path flow, so the computa-tional intensity of the Hessian matrix is reduced to aK{m)\k denotes that path k is excluded fromsimple line search in the negative gradient direction.path set K(")5 Numerical Results●Update the path and link flow patterns.ConvergenceTwo numerical examples are presented to ilustrate thef"(n)performance of the Newton methods for traffic as-If max29r(1)≤ε, terminate; oth-signment problems. The first example ilustrates thedifferences between the various Newton methodserwise, go to Column generation.summarized in Fig. 3, while the second example com-4 Computational Considerationspares the performance of Newton methods with fixedσr optimal step sizes and the Frank-Wolfe algorithmAn important issue in path-based Newton methods isfor various networks. The assignments used a Bureau ofhow to store the paths to limit memory usage due toPublic Roads link-cost function, t=t[1+0.15(x/c)*],the large networks used in the Newton methods. Onewhere 1 is the link travel time, to is the freeflow cost, xshortest-path tree is built at each iteration from eachis the flow, and c is the link capacity. The convergenceorigin and ceach path is part of the shortest-path treestolerance was set as 8=1x10~ for all the assignmentfrom the corresponding origin node. The shortest pathcases.tree should not be stored as a node list to avoid re-peated storage of the common portions of differentExample 1paths from the sarme origin. If one node oumber isConsider a small network consisting of 4 links and 3stored for each node, each tree in a network of N nodesrequires N storage locations which results in NxNnodes as shown in Fig. 4. The origin-destination de-storage locations for each iteration, where No is themand and link performances are listed in Table 1.number of origins. Thus, the main memory require-ment for the Newton methods becomes NoxNxN;,where N; is the number of iterations to reach conver-gence. Note that N。and N are fixed by the networkFig.4 Networktopology, while N; depends on the convergence of theTable1 Input data for Example 1methods. Thus, the methods must converge well to beof practical use.Linbr°_C9_Careful implementation is absolutely essential for106009012)-600Newton methods to perform well. Almost all of the217500oou,3)-400time in the Frank-Wolfe algorithm is spent in the8009o02,3)-600shortest-path routine for larger networks. Apart from50400the computational intensity associated with the short-are afcted by the .est-path routine, Newton methods also have other pro-magni中国煤化工ar progammingcedures that consume excessive computational time.experiYHCNMHGsizeof1usuallyThe four key operations that must be carefully imple-works well with Newton methods. However, this ex-mented are the assigning of path flows to each link toample provides quite different insight into choosing the772Tsinghua Science and Technology, December 2009, 14(6): 765-775step size. Table 2 lists sequences of the objective func-of all the step sizes. The convergence with a step sizetion obtained for different step sizes (h=02, 0.4, 0.5,of unity is quite slow in this case because orthogonal0.6, 0.8, 0.9, 1.0). The bold numbers represent whereprojection does not occur in this case. Even with anthe objective function has reached the minimum butadaptive step size that is larger but avoids any negativethe calculation continues for more iterations whilepath flows, i.e, avoids orthogonal projection; thereaching the accuracy level of E= 1x10~. The resultsadaptive step size is always unity and the computa-in iterations after the bold number have the same val-tional result is the same as for a step size of unity. Thus,ues as the iterations of the Newton methods equilibratethe adaptive step size calculation verifies that projec-the flows among the existing paths to satisfy the con-tion never occurs in this example with a unit step size.vergence tolerance. For a step size of h= 1.0, the con-Therefore, projection would also not occur with anyvergence requires at least 1767 iterations, the sloweststep sizes less than 1.Table2_ Computational results for Newton methods with various step sizesObjective function valueIterationA=0.21三0.42=0.5A=0.6三0.8A=0.9=1.0021 97421 82821 74621 72721 72121 77521 81521 76421 73421 77921 90021 7382172121 72421 74321 79821 7221 72221 74021 85921 72321 73021 78621 72821 83421 72521 77810218161121 77221 80321 76721 7931521 76321 7851767However, step sizes less than 1 seem to work quitethree schemes converge to an accuracy level ofwell even when projection does not occur, especiallyE=1x10~ within five iterations, but with different stepfor h=0.4, 0.5, 0.6. Thus, h close to 1 is not alwayssizes. The optimal-step Newton methods have robustthe best choice for network problems, with other con-convergence without the instabilities of the fixed-stepstant step sizes yielding very rapid convergence evenNewton methods, regardless of the combination of thewithout orthogonal projection. Further work is neededscaling matrix, and step size. Comparison of Tables 2to clarify why the step size h=0.6 is better thanand 3 shows that the Newton method scaled by theh= 0.5, since h= 0.5, is equivalent to the optimal stepHessian matrix with the optimal step has the same re-size, as described in the following.sult as that of the Newton method of a fixed step sizeTable 3 shows sequences of the step sizes and theof h≈0.5. The same result occurs because the twoobjective function obtained with optimal step sizesmethods have the same direction, scaling matrix, andwhich depend on the feasibility of the flows and the中国煤化工scaling matrix isoptimality condition. The scaling matrices werestronEmal-step Newtonthe exact Hessian matrix or the Hessian matrixmethMYHC N M H Gocialed with comapproximated by the OD demand or the path flow. Allputing the Hessian matrix.CHENG Lin (程琳) et al: Constrained Newton Methods for Transport Network Equilibrium AnalysisTable3 Computational results for Newton methods with optimal step sizesScaled by Hessian matrixScaled by OD demand matrixScaled by path flow matrixIterationStep sizeObijectiveObijctiveStep size .Objective00.21 9740.021 6021 970.521 727217270.032 6021 7210.031 150.035 290.031 21217210.035 38As shown in Fig. 5, the optimal-step Newton meth-600rods are superior to the fixed-step Newton method withPath flow in Link 1unit step size4.s), because the latter does not experiencean orthogonal projection with zigzagging of the result.550The phenomenon is also shown by the path flow varia-tions shown in Fig. 6. The optimal step Newton meth-00ods have much better convergence in this case showingthat the Newton method with the unit step size is not100always efficient for taffic assignment problems.Path flow in Link 22.2050-12.19-Newton method with unit step size-1020304050602.18|Iterations(a) In OD(1,2)Newton method with optimal step400r2.17Path flow in Links 1 and 3Fig. 5 Comparison of Newton methods' convergence350for Example 15.2 Example 2In the second example, Newton methods are used tosolve various traffic assignment problems to test theirPath flow in Links 2 and 3robustness. The three traffic networks are described inTable 4, with the computational results in Table 5. For5(the frst two networks, the Newton method with stepsize h=1 (GP) exhibits more rapid convergence thanthe optimal-step Newton methods, but the fixed-step102030.Newton method does not converge as well for the third(b) In 0D(1, 3)case. Since projection does not occur the solution zig-Fig.6 Path flows for Erample 1zags for the Sioux Falls network as in Example 1. Theoptimal-step Newton methods are relatively robust andand Lee et alLlh indicate that the GP algorthm (a spe-convergent for all types of problems.:ial case. of the Newtnn methndel is typically aboutThe link-based Frank-Wolfe algorithm is not com-twice a中国煤化工ife agorithmn, inpared with the Newton methods here. However, pub-terms (THC N M H Gnding solutions.lished results in Jayakrishnan et al's, Chen and Leel6,Tsinghua Science and Technologr, December 2009, 14(6): 765-75Table 4 Three trfle networks for Example 2NetworksNo. of nodesNo. oflinksNo. ofOD pairsReferencesNguyen13l9Nguyen and Dupuis!9yInoue82412Inoue20OD demand: LeBlanc et al4;Sioux Falls76528Link capacit:; Yang and Meng2"___Table 5 Computational results with the Newton methods for the three traffc networksOptimal step sizeFixed step size徊1scaled by Hessianscaled by OD demandscaled by path flowNo. oflter.__ ObiectiveNo.oflter. Objective_ No. oflter.Objctiv No. ofter. bjective67 249910292 46911Sioux Falls'15281024902422*Accuracy level of 0.001 was not used due to the measurement unit problem.4] Bertsekas D P. On the Goldstein-Levin-Poljak gradient6 Conclusionsprojection method IEEE Transactins on Automatic Com-trol, 1976, 21: 174-183.This paper presents a general framework for con-[5] Jayakrishnan R, Tsai W K, PrashkerJN, et al. A fasterstrained Newton methods for taffic assignments. Thepath-based algorithm for taffc asignment. Transporationtechniques of column generation, orthogonal projec-Research Record, 1994, 1443: 75-83.tion, and line search can be incorporated into the solu-6] Larsson T, Prtisson M. Simpicial decompsition withtion procedures. The column generation allows thedisaggregated representation for the trafic assignmentactive paths joining each OD pair to be generated in-problem. Transporation Science, 1992, 26: 4-17.temally only when needed. The discussion shows that[7] Parikssn M. The Trafie Assignment Problem: Modelsthere are several schemes for the Newton methods. Theand Methods Urecht, The Netheriands: VSP BV, 1994.methodology highlights the importance of determining[8] Hearm D W, Lawphongpanich s. A dual algorithm for traf-the optimal step size to accelerate convergence of thefec asignment problems. Transporation Research, 1990,Newton methods for taffic assignment, with the opti-24: 423-430.mal-step Newton methods being robust for all the[9] Lo H K, Chen A. Traffice equilirium problem withvarious networks analyzed. The conventional gradientroute- secifc costs: Formulation and algorithms. Trans-projection algorithm is then a special case of the New-poration Research, 2000, 34B: 493-513.ton methods. The performance of the altemative New-[10] Kaysi I, Ben-Akiva M, Koutsopoulos H. An integratedton methods is improved by the combination of theapproach to vehicle routing and congestion prediction fordescent direction calculation, scaling matrix, the 0C-real-tine driver guidance. Transportation Research Record,curence of orthogonal projection, and the seletion of1993, 1408: 66-74.the optimal step size.[1] Tobin R L, Fricsz T L. Sensitivity analysis for equilibriumnetwork flow. Transporation Science, 1988, 22: 242-249.[12] Bell MG H, lida Y. Transportation Network Analysis. New[1] Shefh Y. Urban Transportation Networks. EnglewoodYork: John Wiley & Sons, 197: 14148Cifs, New Jersey: Prentic Hall, 1985.[13] Gabriel s, Berstein D. The trflce equlibrimn problem[2] LeBlanc L I, Morlok E K, Perskalla W P An eficicantwih naditive path costs. Transporation Science, 1997,approach to solving equilibrum taffic asignment problem.31: 337-348.Transporation Research, 1975, 9: 309-318.[141中国煤化Imative qusiNewton[3] Heam D w, Lawphongpanich s, Vebtura J A. RestrcedfHCNMHGiment. Transporlationsimplicial decomposition: Computation and extensions., =w 01 1-1l6.Mathematical Programming Study, 1987,31: 9-118.[15] Bertsekas D P, Gllager. Data Networks. Englewood Ciffs,CHENG Lin (程琳) et al: Constrained Newton Methods for Transport Network Equilibrium Analysis775New Jersey: Prentice Hall, 1987: 365-478.tion Science, 1973, 7: 168-176.[16] Chen A, Lee D H. Path-based algorithms for large -scale[19] Nguyen s, Dupuis C. An eficieaet method for computingtraffic equilibrium problerms: A comparison between DSDtraffic equilibria in networks with asymmetric transporta-and GP. In: Proceedings of the Transportation Researchtion costs. Transporation Science, 1984, 18: 185-202.Board Annual Meeting. Washington D. C, 1998.[20] Inoue H. Traffc equilibriuim and its solution in congested[17] Lee D H, Yu N, Chen A, et al. Link and path based trfficroad networks. In: Proceedings of IFAC Symposium onassignment algorihms: A computational and statisticalControl in Transportation Systems. Vienna, Austria: Per-tudy. In: Proceedings of the Transportation Researchgarmon, 1986: 267-272.Board Annual Meeting. Washington D. C., 2002.[21] Yang H, Meng Q. An integrated network equilibrium[18] Leventhal T, Nemhauster G Trotter L. A column genera-model of urban location and travel choices. Jourmal of Re-tion algorithm for optimal taffc assignment. Transporta-gional Science, 1998, 38(4): 575-598.Former Harvard Business School Senior Associate Dean F. Warren McFarlanAppointed Co-Director of Tsinghua School of Economics and Management ChinaBusiness Case CenterTsinghua University's School of Economics and Management (SEM) announced the appointment on August 18,2009 of former Senior Associate Dean of the Harvard Business School Professor F. Warren McFarlan asCo-Director of SEM's China Business Case Center for the next three years.During his tenure, Professor McFarlan will design a Harvard Business School case study based teaching platformfor SEM adapted to the current business environment in China. Professor McFarlan will also select a company asthe basis for case study and research on the problems the company encounters in its growth process. He may alsoopen further case development and teaching seminars in the future.SEM's Dean Qian Yingyi, Associate Dean Yang Bin, and Associate Dean Xia Donglin, who is also Director ofSEM's China Business Case Center, as well as the Director of Tsinghua's SEM EDP Center Xue Lei and Directorof the School's Office for Communication Zheng Yuhuang attended the ceremony at which Professor McFarlan'sappointment was announced.Professor McFarlan earmed his AB from Harvard University in 1959, and his MBA and DBA from the HarvardBusiness School in 1961 and 1965 respectively. He has played a significant role in introducing materials on Man-agement Information Systems to all major programs at the Harvard Business School since the first course on thesubject was offered in 1962. He has been a long time teacher in the Advanced Management Program, the Intema-tional Senior Managers Program, the Delivering Information Services Program, and several of the Social Sectorprograms. He currently teaches the MBA first year Financial Reporting and Control course and the second yearDoing Business in China in the Early 21st Century course. He also teaches in several Executive Education pro-grams.中国煤化工) 2009-08-21)"THCNMHG