AbstractsComputer Science

An Investigation Into Braess' Paradox and Selfish Routing in Traffic Flow

by Anette Ostbø Sørensen

Institution: Norwegian University of Science and Technology
Year: 2014
Record ID: 1294745
Full text PDF: http://urn.kb.se/resolve?urn=urn:nbn:no:ntnu:diva-25619


The aim of this master thesis was to investigate Braess' Paradox in traffic flow and to look at the effect of selfish routing in optimization of flow distribution on traffic networks. Braess' Paradox is a well known phenomenon in traffic flow. It occurs when extention of a road network by one road leads to increased travel times for all travelers due to a redistribution of the traffic.Selfish routing is about how travelers choose their travel route selfishly. Compared to flow distribution at system optimal flow, selfish routing may result in increased travltime for some or all travelers.The optimal flow distribution was found by a non-linear program, and Nash equilibrium and system optimal flow are achieved with different objective functions. The non-linear program is solved as quadratic programming, since the travel time functions are linear. The method to solve the program was an interior-point method based on a predictor-corrector method. The results of occurences of Braess' paradox are compared to the results from a mathematical characterization of the paradox from the litterature.Four different traffic networks was investigated. The first network was the network model originally used by Braess with one origin and one destination. Furthermore, a network of one origin and two destinations was used, which contributed to two different networks when the direction of two roads were changed. Another network is of two origins and one destination, which also contributed to two networks. Lastly, a three times symmetric network was used, with three origin-destination pairs. Each of the networks were nvestigated to find occurences of Braess' paradox, and to investigate the effect of selfish routing. In the analyses the values of function parameters and demand between origin and destination was changed. In the work it was showed that Braess' paradox occures at some limited intervals of demand, which is dependent on the parameters in the travel time functions. It seems to exist an upper limit for the increase in travel time caused by the added road. The paradox occures when the path with the additional road is utilized together with and at the same time as one or several other paths. Selfish routing affects the travel time when demand is within a limited interval. The travel times at system optimal flow distribution is in some intervals most unfavorable for some of the travelers, compared to the travel time at user optimal flow.