Trafikktilordning og Optimering.

Abstract

The abstract is in English, however the master thesis itself is written in Norwegian. The thesis consists of four main parts. Firstly we introduce the concepts of general mathematical optimization and convex optimization. The second part starts by giving some background history to the traffic assignment problem, and then states the problem as a convex optimization problem. The third part explains how the Frank-Wolfe algorithm works, and then presents an alteration which has been made to the algorithm. The alteration makes the algorithm solve the version of the traffic assignment problem faster. The last section of part three tests the Frank-Wolfe algorithm with and without the alteration on different examples and reports the results. The last part of the thesis looks at the network design problem, where it first states the problem, and then introduces a heuristic for slowing it. Finally, the algorithm is used on some interesting examples and the results are presented.

The thesis uses a network which is a simplification of the roads in Oslo and the area surrounding the city. An assumption is that all the travelers in the traffic assignment problem are using cars. The problem consists of assigning the travelers from different origins to their given destinations, by using the roads in the network. For an optimal solution to the problem, each path (which is a combination of roads) has exactly the same travel time. On the Oslo network, we compare numbers of iterations for the Frank-Wolfe algorithm, with and without the alteration presented earlier. The results indicate that the alteration made to the algorithm has a vast improvement in the number of iterations, thus also in the running time on a computer. The traffic assignment problem studied in this thesis has travelers situated between most of the points (places) in the network. Therefore there exist many different origin/destination-pairs. In the light of this we would expect the same improvement as seen in this thesis for similar problems consisting of many origin/destination-pairs.

Given the alterations that can be made to the network, the network design problem is aiming to determine the best possible alteration. That is, an alteration of the network that gives the lowest total traveling time for the travelers. The heuristic for solving the network design problem finds an optimal solution in the tests made in this thesis. We can t expect that this always will be the case, but hopefully satisfying solutions could be found.