Optimal Toll Design Problem in Dynamic Traffic Networks
D Joksimovic, M C J Bliemer, P H L. Bovy, Delft University of Technology, NL
The optimal toll design problem is a part of a project ?A Multi-Disciplinary study of Pricing Policies in Transport - A Traffic Engineering Perspective? with focus on the optimal toll design and dynamic traffic assignment modelling part of it. This project is being carried out to provide theoretical and practical evaluation of effects of different road transport pricing policies on behavioural responses and their consequences. It is part of a larger multi-disciplinary research program established as a co-operation between four Dutch universities. More about problem definition and theoretical framework can be find in Joksimovic (2002). The problem of congestion pricing has been studied in the literature from different modelling perspectives and under various assumptions. Classification can be made depending on different criteria: pricing theory (marginal cost pricing vs. second best pricing), objectives to be reached (minimising total travel time or maximising net social welfare), type of analysis (static or dynamic pricing), pricing strategy (link-based, path-based or zone-based pricing) and type of OD-table taken in the analysis (static or dynamic OD table). The classical two-route congestion problem in static networks has been studied in Vickrey (1969), Dafermos and Sparrow (1971), Clegg et al (2001), Patriksson and Rockafellar (2002), Verhoef (2002).
Nevertheless, the nature of dynamic pricing in combination with dynamic traffic assignment leads to a very complicated formulation and especially difficult solution procedure of the problem. The researchers try to develop efficient algorithms in order to solve the dynamic pricing problem applied on dynamic, real-size traffic networks (Arnott et al. (1990), Huang and Yang (1996), Wie and Tobin (1998), Viti et al. (2003)). Dynamic congestion pricing methods with time-varying tolls over the day (but constant from day-to day) based on a bi-level programming formulation are proposed in this paper. The pricing methods take users? reaction (lower level) into account to compute the prices (upper level). A second-best link-based approach (where only a subset of links on the network is tolled) is used that sets upper bounds on the link prices.
The contributions of the paper can be listed as follows:
1) the dynamic congestion problem subject to the user equilibrium level is formulated as a bi-level programming problem, using the Mathematical Programming with Equilibrium Constraints (MPEC) method; the pricing is link-based and the second- best pricing is applied;
2) not only the route choice but also the departure time choice is modelled showing that the user?s tend to adapt their departure time choice in order to pay less for the travelling;
3) the whole problem is solved using the iterative gradient-based solution procedure;
4) the proposed model and solution algorithm are applied to a small hypothetical dynamic network;
Formulation of the optimal toll design problem
From the game theory point of view the optimal toll design problem can be represented as a leader-follower game, or Stackleberg game, where the system manager is the leader, and the network users are the followers (see more about pricing and game theory approach in Joksimovic et al. (2003)).
Considering the optimal toll problem, our aim is to optimize system performance (to minimise the total travel cost) by choosing the optimal tolls for a subset of links and within realistic constraints. First, the system manager selects feasible values for tolls, in order to optimize his own objective function. After that, network users use his decision and make route choice and departure time choice in order to satisfy their objective function, resulting in changing of flow pattern and departure time pattern. Travelers react on different travel costs, changing their travel behavior (route and departure time). This minimization problem can be converted into an equivalent variational inequality (VI) problem (Bliemer (2002)). Mathematical program with equilibrium constraints (MPEC) is an extension of a bi-level program applied for problems where the upper level is an optimisation problem and the lower level is an equilibrium problem (Luo et al. (1996)).
Solution of the problem
The link cost function used in this work consists of the following parts: 1) flow dependent travel time, 2) penalties for early departure at the origin, 3) penalties for late arrival at the destination 4) link toll. We assume that every driver has a perfect knowledge about route costs and route alternatives.
A gradient expression for the change in total travel time as a function of the change in prices, is derived and utilized in a decent gradient-based solution algorithm, which aims at determining a solution with lower total travel time from one iteration to another (Yang (1997), Abou-Zeid and Chabini (2003)). In every iteration the algorithm finds a user equilibrium solution and computes the gradients to find new prices that will potentially decrease the total travel time. The pricing methods have been applied to a small network example. It is shown that pricing leads to savings in total travel time compared to the no-toll situation.
This paper is organized as follows: First, the congestion pricing problem is mathematically formulated and some analytical properties of the problem are described. After that an iterative solution algorithm is presented. Then the congestion pricing methods are evaluated on a small hypothetical network. Finally, the conclusions are given as well as limitations and possible extensions.
Association for European Transport