Hide metadata

dc.date.accessioned2013-03-12T08:20:59Z
dc.date.available2013-03-12T08:20:59Z
dc.date.issued2008en_US
dc.date.submitted2008-11-17en_US
dc.identifier.citationVenstad, Jon Marius. System optimum vs. user equilibrium in static and dynamic traffic routing. Masteroppgave, University of Oslo, 2008en_US
dc.identifier.urihttp://hdl.handle.net/10852/10765
dc.description.abstractThis thesis treats traffic as flow in static and dynamic networks. This may be any kind of traffic; cars, information etc. Two flows are of particular interest: The system optimum, which minimizes total travel time for all traffic, and the user equilibrium, in which all traffic with common origin and destination experiences the same cost. The system optimality problem is given globally as a minimization problem, whereas the user equilibrium is given locally on the flow of each origin-destination pair. A network consists of a directed graph G = (V, A) where each arc has a transition time, or latency function, dependent on the amount of flow along it. In addition arcs may have flow capacities. Some of the vertices also have supplies or demands, and a flow needs to satisfy all constraints in the network. The static networks are allowed to have convex non-decreasing latency functions, which makes finding the system optimum or the user equilibrium for a given network a convex optimization problem in general. The thesis also treats some special cases. The main results in this area are : (1) A system optimality criterion given locally on the flow of each origin-destination pair, similar to the criterion for a user equilibrium. This makes checking for optimality simple, and can in some cases simplify finding the system optimum. (2) An algorithm for determining taxes on the arcs of a static network such that the system optimum when considering only latency costs and the user equilibrium when considering latencies and taxes coincide. This can for instance be used to determine taxes that will make vehicle traffic in cities distribute itself in a system optimum, minimizing the total amount of time spent in traffic by all vehicles. The dynamic networks are restricted to having only constant latency functions on the arcs. This allows discretizing the the network along the time axis, which again allows for a linear optimization formulation of the dynamic system optimality problem. The main result in this area is an algorithm for finding the dynamic system optimum without discretizing the network, and thus reducing the required computational time by a large amount. This algorithm is based on the Successive Shortest Path algorithm for finding minimum cost static flows, and has the same running time as this algorithm. The resulting dynamic flow is one that consists of different extreme static flows at different time intervals. Combining this result with (2) from the static flow work ultimately results in a method for computing a dynamic system optimal flow and turning this into a user equilibrium by adding time dependent taxes along the arcs of the network.eng
dc.language.isoengen_US
dc.subjecttrafikk-tilordning dynamisk nettverk-støm brukerlikevekt system-optimal bomplasseringen_US
dc.titleSystem optimum vs. user equilibrium in static and dynamic traffic routingen_US
dc.typeMaster thesisen_US
dc.date.updated2009-05-05en_US
dc.creator.authorVenstad, Jon Mariusen_US
dc.subject.nsiVDP::410en_US
dc.identifier.bibliographiccitationinfo:ofi/fmt:kev:mtx:ctx&ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:dissertation&rft.au=Venstad, Jon Marius&rft.title=System optimum vs. user equilibrium in static and dynamic traffic routing&rft.inst=University of Oslo&rft.date=2008&rft.degree=Masteroppgaveen_US
dc.identifier.urnURN:NBN:no-21228en_US
dc.type.documentMasteroppgaveen_US
dc.identifier.duo86991en_US
dc.contributor.supervisorGeir Dahlen_US
dc.identifier.bibsys092368204en_US
dc.identifier.fulltextFulltext https://www.duo.uio.no/bitstream/handle/10852/10765/3/VenstadMaster.pdf


Files in this item

Appears in the following Collection

Hide metadata