# Model-Based Dynamic Toll Pricing: An Overview
## 2 Overview of Dynamic Toll Price Definition Methods
### Optimization-Based Algorithms  
While control-based dynamic toll pricing approaches described in Section 2.1 usually focus on keeping free-flow conditions, optimization-based algorithms are built around the maximization of some performance index of the system. Road managers may be interested in implementing strategies that, as they deal with congestion on the managed road, satisfy some objectives as maximization of revenue, social welfare, freeway throughput, or a combination of them [48]. A general formulation of the unconstrained optimization problem for the definition of such strategies is given by Equation (6):  
\[\pi(n)=\operatorname*{argmax}_{\pi(n)}\sum_{k=n}^{n+N}g(\pi(k)), \tag{6}\]  
where the toll price for tolling interval \(n+1\), \(\pi(n+1)\) is the one that maximizes the accumulation of a performance index \(g(\pi(k))\), chosen according to the strategy objectives, over a certain period of time, called _rolling horizon_, corresponding to the following \(N\) intervals. The complete formulation of the optimization problem is given by (6) with appropriate constraints. Manifold single-objective pricing strategies with similar formulations are presented in literature: revenue-maximizing problems are described in [28; 29; 30; 46], a throughput maximizing problem is formulated in [31], and an average-flow maximizing toll is presented in [8]. In [8; 30; 31], penalty methods are applied, replacing the constraints to ensure free-flow with penalty functions added to the objective function. As is intuitive, strategies obtained via the maximization of a performance indicator associated with a single objective may not satisfy other possible objectives: for example, total system travel time minimization and revenue maximization are found to conflict in [40]; multi-objective approaches in literature aim to design tolls from a compromise among multiple objectives, seeking Pareto optimum, a solution characterized by the fact that \"no other feasible solutions can improve at least one objective without deteriorating another\" [60]. A bi-objective optimization approach is proposed in [33], where the objective function \(\gamma\) is defined as the weighted sum of the system cost \(c\) (in monetary units) and time \(\tau\) (in time units) (7):  
\[\gamma=c+w\cdot\xi\cdot\tau, \tag{7}\]  
where \(\xi\) is the weighted average value of time (VOT), to convert time units in monetary units, and \(w\) is a non-negative weighting parameter, called _Pareto parameter_. The obtained toll expression reduces to a minimum cost scheme for \(w=0\) and to a minimum time scheme, in case of \(w\rightarrow\infty\). The authors of [60] propose a toll defined by a bi-objective program for a tollable vehicular network, seeking to minimize both total delays and emissions, formulating the problem as a mathematical programming with complementarity constraints (MPCC) and solving it with a quadratic penalty-based gradient projection algorithm. A Pareto-improving queue-eliminating dynamic toll is proposed in [34]. Dynamic toll pricing problems are generally particularly difficult because of their fundamental bi-level form, where the upper level is the one picking the optimal tolls, which are subject to route-choice constraints that constitute the lower-level dynamic traffic assignment [81]. The computational complexity of the toll design problem is known to be NP-hard [81; 82; 83], even when the formulation is not explicitly dynamic [37; 84; 85; 86; 87]. As a consequence, these problems are typically solved through heuristics or meta-heuristics [81]. In [35], a bi-level dynamic second-best toll pricing model is solved through a relaxation scheme consisting in the conversion of the bi-level formulation into a single level nonlinear programming problem, which is then solved iteratively. In [36], the genetic algorithm and the method of successive average are used to solve a two-layer network dynamic congestion pricing problem.