Unformatted text preview:

Amount of travel on road or transit line iso a e1.204 Lecture 18 Continuous constrained nonlinear optimization:optimization: Convex combinations 1: Network equilibrium Transportation network flows • Amount of travel on any road or transit line isany result of many individuals’ decisions – These depend on price and quality of service – Congestion in urban areas is a significant factor • Analyzing passenger flows on networks relies on: – Graph data structures – Shortest path algorithms Net rk assignment lgorithms that assign tra lers to – Network assignment algorithms that assign travelers to a particular set of streets or transit lines, based on travel time, cost and other service measures – Demand models are also used • Based on discrete choice theory (take 1.202!) 1t t t t t tTransportation network equilibrium • Users make their own, ‘selfish’ decisions on the best path through a network – When congestion exists, traveler choices affect travel times, which in turn affect traveler choices, which… – Users switch routes (and modes and time of day and trip frequency and location) in response to changes in service quality – We model this as a market that reaches supply-demand equilibrium on every arc in a network Figures from Sheffi Definition of equilibrium • Links (including intersections) have a supply function: • Definition of equilibrium: – For each origin-destination pair: • Travel time for all used paths is equal, and is • LLess thhan ((or equall to)) thhe travell tiime on any unusedd pathh (Transit is messier, because it has a route structure as well as a network structure, but the same principles apply) 2 Q QuantityQ*P *P Price Supply functionDemand functionFigure by MIT OpenCourseWare.1325412345678910Figure by MIT OpenCourseWare.Link Travel Time [min]Link Flow [veh/hr]Free flow travel timeX3 CapacityωtFigure by MIT OpenCourseWare.3Network equilibrium problem formulationdtxzxaa)()(min∑∫=ωωksrfxsrkfsrpairsODqftosubjectrskarskrskpathsrskaarcs,,,,0,0∑∑∑∑∫∀=∀≥∀=storfrompathonaiffkkjia,,∑∑∑Network equilibrium problem example21211+=+=xtxt3:,)(:521212122===++=xinspectionbySolutionusedroutesbothttconditionsmEquilibriuxxxt5232121====ttxx2+x1= 1+2(5-x1)3x1= 11-2x1= 3Link Travel Time [min]Link Flow [veh/hr]Free flow travel timeX3 CapacityωtFigure by MIT OpenCourseWare.1 2 312345Travel Time [min]Flow [veh/min]t1(x1)t2(x2)x2 = 2x1 = 3txO DLink 2Link 1Figure by MIT OpenCourseWare.4Formulation example..)21()2()(min0021+++=∫∫tsddxzxxωωωω..)21()2()(min510,0550012212111+++=−=−≥≥=+∫∫−tsddxzxxsettingbyDtoConvertxxxxxxωωωω30)(3095.1)(:05,0..11112111=⇒=+−=≥−≥xdxxdzxxxzlyanalyticalIntegratexxtsz(x)= 2x1+ x12/2 +(5-x1) + (5-x1)2= 2x1+ 0.5x12+ 5-x1+ 25 - 10x1+ x12Formulation• The formulation has no economic or physical significancepy g– It happens to produce the desired first-order conditions for an optimum– They require that the time on all routes used between an origin and destination be equal– And the time on routes not used must be greater– We can view the objective function as a convergence criterion for the equilibrium solution• Nonetheless, equilibrium is a key conceptqyp– And it’s a nonlinear optimization problem, techniques for which we want to cover in this course– This is a constrained continuous nonlinear optimization problem5Solution method: convex combinations..)(minijiijjbxhtsxz∀≥∑||||/)(.),...,,(,),...,,(2121nnnnnInnnnInnnixyxyvectorunitisytoxfromDirectiondecreasemaximumgivesytoxfromdirectionsoyyyysolutionfeasibleauxiliaryfindtowishwedirectiondescentfindToxxxxissolutioncurrentAssume−−==))(,...,)(,)(()(||||)()()()()||(||||||)(21 jnnTnnnnxxzxxzxxzxzwherexyxyxzxyofdirectioninxzofSlopevvmeansvyyyf∂∂∂∂∂∂=∇−−⋅∇−=−⋅Solution method: convex combinations 2..)()()()(min:TnnnnLbyhtsxyxzxzyzionapproximatlinearasproblemoriginalRewrite≥−⋅∇+=∑)()()(min:,,)()(iiinTnnLnnnnijiijyxxzyxzyzleavingitdropcanwesoxxatconstantisxzAlsoxzdropcanwe:constantisfunctionobjectiveofvaluexxAtbyh⋅∂∂=⋅∇==∇=≥∑∑)(...nnijiijxydirectiondescentagivesItyissolutionwhoseprogramlinearaisThisbyhts−≥∑6Solution method: convex combinations 3tsxyxzdirectionthisingotofarhow determine Tonnn..)]([min:−+αxyxx:by generated point next found, is α Oncebisection using searchline a withsolvedα, in problem onminimizati D-1 a is Thisnnnn1n)(10−+=≤≤+ααguaranteed but slowis whiche,convergenc until Continueyandx of ncombinatio convex oraverage, weighteda is solutionnew Theynnn)(Convex combinations algorithm• Step 1: Direction finding. Find ynthat solves linear program.pg• Step 2: Step size determination, or line search. Find αnthat solves)]([minnnnxyxz−+α∑∑≥⋅∂∂=ijiijiiinnLbyhtsyxxzyz ..)()(min• Step 3: Move. Set• Step 4: Convergence test. If z(xn) - z(xn-1) < K, stop)]([yα)(nnnn1nxyxx −+=+α8Next time• We’ll apply the convex combinations method to the network equilibrium problempp y– Formulation– Algorithms• Direction finding – Shortest path algorithm solves the linear program– Compute y flow vector (auxiliary solution)• Line search – Bisection solves the line search problem– Must compute derivative of objective function– Must compute of objective function• Move– Update x flows on network as linear combination of x and y flows– Update arc travel times; both of these steps are just algebra• Convergence test– Compute change in flows as simplest measure– Java implementationderivativeMIT OpenCourseWarehttp://ocw.mit.edu 1.204 Computer Algorithms in Systems Engineering Spring 2010 For information about citing these materials or our Terms of Use, visit:


View Full Document

MIT 1 204 - Convex combinations 1- Network equilibrium

Download Convex combinations 1- Network equilibrium
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Convex combinations 1- Network equilibrium and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Convex combinations 1- Network equilibrium 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?