Dynamic Stackelberg equilibrium congestion pricing

Abstract

This paper considers the problem of dynamic congestion pricing that determines optimal time-varying tolls for a pre-specified subset of arcs with bottleneck on a congested general traffic network. A two-person nonzero-sum dynamic Stackelberg game model is formulated with the assumption that the underlying information structure is open loop. Characteristics of the Stackelberg equilibrium solution are analyzed. The Hooke–Jeeves algorithm that obviates an evaluation of the gradient vector of the objective function is presented with a numerical example. The paper concludes with its future extensions.

Introduction

In this paper we consider an application of the dynamic Stackelberg game theory to a particular situation where a public highway authority determines congestion toll schedules for a pre-specified subset of arcs with bottleneck (e.g., tunnels or bridges) on a congested traffic network and where automobile commuters choose departure time–route pairs with minimum costs between their relative origins and destinations. The goal of a government authority is to improve the network performance and maximize the net consumer surplus through its toll policy. Such an application also corresponds to a situation where a private firm seeks an optimal toll policy to maximize toll revenues generated from privately-funded express lanes while keeping toll levels sufficiently low enough to attract commuters from congested untolled lanes and simultaneously keeping toll levels high enough to guarantee free-flow travel conditions on tolled lanes as often required by a government in the franchise agreements. This paper, however, focuses on the former situation where the maximization of net consumer surplus is the public highway authority’s goal.

The Stackelberg equilibrium strategy appears to be suitable for the problem of dynamic congestion pricing in which the leader is a public highway authority, the follower is the group of automobile commuters and the network flow pattern is constrained to be in equilibrium. We assume that the leader announces arc-specific congestion toll schedules before commuters begin their trips and toll schedule information is available via the Internet, road signs, or other media channels. Each commuter is assumed to determine its optimal departure time and routing strategy through day-to-day explorations according to a dynamic version of Wardrop’s first principle of traffic equilibrium, while taking into consideration the pre-announced toll schedules. The leader, however, takes into consideration the global impact of dynamic congestion tolls on the departure time–route choice behavior of commuters when determining toll schedules.

The central part of the dynamic Stackelberg congestion pricing problem is to find optimal toll schedules that can shift a dynamic user equilibrium flow pattern toward a socially preferred flow pattern for the maximization of net consumer surplus. The lower-level dynamic network user equilibrium problem with elastic travel demands and schedule delays is formulated as a finite-dimensional arc-based nonlinear complementarity problem. The dynamic congestion pricing model presented in this paper is different from that considered in the work of Wie and Tobin (1998) where the theory of marginal cost pricing is applied to determine optimal time-varying tolls for every arc that are equal to the difference between marginal social costs and marginal private costs. By contrast, the dynamic congestion pricing model considered in this paper is to maximize the net consumer surplus when a public highway authority is constrained to impose congestion tolls only on a pre-selected subset of arcs. Certainly, a dynamic flow pattern induced by the imposition of congestion tolls only on a pre-selected subset of arcs may be less socially optimal with regards to the value of the net consumer surplus than one induced by the imposition of congestion tolls on every arc of the network based on the marginal cost pricing method. However, the application of the marginal-cost based congestion pricing model appears impractical particularly when a realistic size of any urban traffic network with thousands of arcs and nodes prohibits from charging tolls on every arc due to technical difficulties and high capital investment requirement in large-scale implementation of the automated electronic toll collection system.

A number of dynamic congestion pricing models have been reported in the literature. Henderson (1974) considered the importance of schedule delays and departure time decisions in the modeling of congestion pricing for a single bottleneck and showed that time-varying congestion tolls influence the commuter’s decision of departure time and give rise to an efficient reorganization of traffic flows as compared to a non-toll situation. Agnew (1977) applied the optimal control theory to determine an optimal toll to control congestion according to the criterion of maximizing the sum of producers’ and consumers’ surplus. Carey and Srinivasan (1993) derived marginal social costs, marginal private costs and congestion externality costs, obtained a system of optimal congestion tolls, and showed that the congestion externality costs depend not only on the level of congestion but also on the rate of increase or decrease of congestion. Huang and Yang (1996) formulated a time-varying congestion pricing model on a congested network of parallel routes with elastic travel demand using the optimal control theory.

The main contributions of this paper include (1) the formulation of a nonzero-sum open-loop Stackelberg game model, (2) the characterization of open-loop Stackelberg equilibrium strategies, and (3) the development and implementation of a heuristic iterative algorithm. The dynamic congestion pricing model presented in this paper is, however, limited in the following aspects. First, the imposition of congestion tolls affects only the commuter’s decision of departure time and route in the proposed model. In reality, commuters may respond to congestion tolls in several different ways by changing their destination, travel mode, or vehicle occupancy. Second, neither a closed-loop nor a feedback Stackelberg strategy is considered. It implies that the leader is unable to adjust toll schedules on the basis of current real-time traffic information particularly when non-recurrent congestion is created by traffic accident, bad weather, special event, or emergency road maintenance work. An open-loop strategy appears to work better when arc capacities and origin–destination travel demands are stable from day to day and commuters settle into a stationary equilibrium state after learning the best departure time and route choices over time through day-to-day explorations. Third, the existence and uniqueness of Stackelberg equilibrium toll schedules are not proved in the paper. But these solution properties have profound implications for a real-world application of the proposed dynamic congestion pricing model. Moreover, theoretical results are not established for the convergence of the proposed heuristic algorithm. Fourth, the proposed model is not capable of simultaneously choosing a subset of arcs for charging tolls and determining toll schedules for them so as to induce the most socially optimal flow pattern. Instead, a set of tolled arcs is assumed to be known in advance through an external selection process. Such a sequential procedure is, however, quite common in practice which determines the location of tolled expressways and then determines the toll schedules after the construction. Lastly, the shape and time interval of dynamic toll schedules are assumed to be known in advance. We consider only the triangular-shaped multiple step tolls with pre-determined starting and ending periods. Since the shape and time interval of dynamic tolls are pre-selected, it is necessary to determine only the value of the maximum toll for each tolled arc, and the rate of increase or decrease of toll is naturally determined by the value of the maximum toll.

Although the triangular-shaped multiple step tolls have been occasionally adopted in practice such as I-15 FasTrack and 91 Express Lanes in California, its generalization to different shapes such as nonlinear smooth bell-shaped tolls appears to be an interesting topic to investigate in future research. It also appears important to investigate how the shape of schedule delay cost functions would affect an optimum shape of dynamic toll schedules. In this paper, both toll schedules and schedule delay functions are assumed to be piecewise linear.

The paper is structured as follows. Section 2 presents an arc-based dynamic network user equilibrium model and its nonlinear complementarity formulation. This model formulation is similar to that in the work of Wie et al. (2002). A main difference can, however, be found in the definition of route–departure time decision variables. In Section 3, a two-person nonzero-sum dynamic Stackelberg game is formulated as a bilevel dynamic optimization problem. Open-loop Stackelberg equilibrium strategies of the leader and the follower are also defined. In Section 4, a heuristic algorithm is proposed to find Stackelberg equilibrium congestion toll schedules. The paper concludes with a discussion on its future extensions.