The road pricing problem: A two-level optimisation approach

Like in many countries congestion is also a big problem in the Netherlands. Congestion is damaging for the economy, the environment, and our own health. There is a big need for solving this problem. Possible solutions are: increasing road capacity, road pricing, fuel taxation, using other modes of transport, etc. Road pricing is seen as one of the best ways to decrease congestion. The traffic authorities want to influence travellers' behaviour with the help of road pricing causing them to change route, change departure time, change mode of travelling, etc., resulting in a more efficient use of transportation resources and relieving congestion on the roads. The road pricing problem can be seen as a situation where two decision makers have conflicting interests. The traffic authorities want to find an optimal toll pattern to achieve a situation in which the road system is in optimal form. I n other words, the traffic authorities want to minimise the total time travellers spend on the network. Travellers, on the other hand, want to minimise their own travel times. It is possible that there are travellers in the optimal network conditions, that can improve their own travel time. If they indeed choose another route for improving their travel time, network conditions deteriorate. The road pricing problem is restricted by some boundary conditions and basic assumptions of which 'the traffic assignment and the traffic flows will be static' is the most important. This research will focus on solving a mathematical representation of the road pricing problem using different methods taking into account the complexity and the properties of the road pricing model. Restrictions are made about the value of toll (lower and upper bound) and the number of roads that may be tolled (not all roads may/can be tolled). Therefore, the purpose of this thesis is not to toll every link, but to achieve a system state that is near the system optimum by charging toll on a subset of links and taking into account a lower and an upper bound for the tolls. This means that i t is a constrained optimisation problem and that some of the variables of the solution may be lying at the boundaries of their allowed ranges. The plan of approach for this research is to do first a literature study on bi-level optimisation and later on solution methods. The road pricing problem can be written mathematically as a two-level optimisation model (a special case of bi-level optimisation). The mathematical model consists of an upper and a lower level. The lower level is a representation of the behaviour of the travellers and in the upper level the traffic authorities are modelled. Both levels consist of an objective function and some constraints. The complexity and the convexity of the road pricing model are discussed. After that some solution methods and their convergence are discussed. Finally, these methods are tested on four networks and the results are reviewed. In complexity theory there are four classes of problems: P, NP, NP-complete, and NP-hard. Problems belonging to the class P are called (computationally) tractable. Problems that belong to the other three classes are called intractable problems. In the literature much is proved about the complexity of a bi-level problem. The conclusion is that the road pricing problem is NP-hard. This means that it is not likely to find an exact solution with a polynomial-time algorithm. Heuristics will therefore be used to solve the road pricing model. It is plausible that the road pricing model is a convex optimisation problem. In that case existing solution methods in order to find local optima can be used. Therefore, line search, first order gradient, direction set, and simplex methods are used to solve the road pricing model. These methods are implemented and eleven test cases are considered to assess and compare the methods. The seven best performing methods in the first four test cases are tested on the resulting test cases. These are the EDO/BS, the SD/BS, the Hestenes/Stiefel, the cyclic coordinate, the Rosenbrock, the Powell I I , and the complex method. They are compared per test case with respect to the value of the objective function (1), the number of the function evaluations (2), and the number of iterations (3). The methods are given notes from 1 t i l l 7 for these three criteria. The best performing method is given number 7 and the worst is given number 1. The average over all the test cases is shown in Table 6.1. Best performing means the smallest value of the objective function, the smallest number of function evaluations, or the smallest number of iterations. This is not the best way for comparing the methods, but it forms a notion of the performance of the methods compared with each other.Transport and PlanningCivil Engineering and Geoscience