Algorithms for Flows over Time with Scheduling Costs

Abstract

Flows over time have received substantial attention from both an optimization and (more recently) a game-theoretic perspective. In this model, each arc has an associated delay for traversing the arc, and a bound on the rate of flow entering the arc; flows are time-varying. We consider a setting which is very standard within the transportation economic literature, but has received little attention from an algorithmic perspective. The flow consists of users who are able to choose their route but also their departure time, and who desire to arrive at their destination at a particular time, incurring a scheduling cost if they arrive earlier or later. The total cost of a user is then a combination of the time they spend commuting, and the scheduling cost they incur. We present a combinatorial algorithm for the natural optimization problem, that of minimizing the average total cost of all users (i.e., maximizing the social welfare). Based on this, we also show how to set tolls so that this optimal flow is induced as an equilibrium of the underlying game.

Partially supported by NWO TOP grant 614.001.510 and NWO Vidi grant 016.Vidi.189.087. A version of this manuscript containing omitted proofs can be found on arXiv:1912.00082.

1 Introduction

The study of flows over time is a classical one in combinatorial optimization; it began already with the work of Ford and Fulkerson [9] in the 50s. It is a natural extension of static flows, which associates a single numerical value, representing a total quantity or rate of flow on the arc. In a flow over time, a second value associated with each arc represents the time it takes for flow to traverse it; the flow is then described by a function on each arc, representing the rate of flow entering the arc as a function of time.

Classical optimization problems involving static flows have natural analogs in the flow over time setting (see the surveys [17, 24]). For example (restricting the discussion to single commodity flows), the maximum flow over time problem asks to send as much flow as possible, departing from the source starting from time 0 and arriving to the sink by a given time horizon T; this can be solved in polynomial time [8,9,10]. A quickest flow asks, conversely, for the shortest time horizon necessary to send a given amount of flow. Of particular importance for us is the notion of an earliest arrival flow: this has the very strong property that simultaneously for all $T' \le T$, the amount of flow arriving by time $T'$ is as large as possible [12]. Such a flow can also be characterized as minimizing the average arrival time [15]. Earliest arrival flows can be “complicated”, in that they can require exponential space (in the input size) to describe [29], and determining the average arrival time of an earliest arrival flow is NP-hard [7]. But they can be constructed in time strongly polynomial in the sum of the input and output size [2].

Another important aspect of many settings where flow-over-time models are applicable—such as traffic—involves game theoretic considerations. In traffic settings, the flow is made up of a large number of individuals making their own routing choices, and aiming to maximize their own utility rather than the overall social welfare (e.g., average journey time). Dynamic equilibria, which is the flow over time equivalent of Wardrop equilibria for static flows, are key objects of study. Existence, uniqueness, structural and algorithmic issues, and much more have been receiving increasing recent interest from the optimization community [3,4,5,6, 16, 22, 23].

Traffic, being such a relevant and important topic, has received attention from many different communities, each with their own perspective. Within the transportation economic literature, modelling other aspects of user choice besides route choice has been considered particularly important. A very standard setting, motivated by morning rush-hour traffic, is the following [1, 26]. Users are able to choose not only their route, but also their departure time. They are then concerned not only with their journey time, but also their arrival time at the destination. This is captured in a scheduling cost function which we will denote by $\rho$: a user arriving at time $\theta$ will experience a scheduling cost of $\rho (\theta )$. The total disutility of a user is then the sum of their scheduling cost and their journey time (scaled by some factor $\alpha > 0$ representing their value for time spent commuting). A very standard choice of $\rho$ is

(1)

where $\beta< \alpha < \gamma$ (it is very bad to be late, but time spent in the office early is better than time spent in traffic). Our approach can handle essentially general scheduling cost functions, but we will restrict our discussion to strongly unimodal cost functions; these are the most relevant, and this avoids some distracting technical details.

Two very natural questions can be posed at this point. The first is a purely optimization question, with no attention paid to the decentralized nature of traffic.

Problem 1

How can one compute a flow over time minimizing the average total cost paid by users, i.e., maximizing the social welfare?

From now on, we will call a solution to this problem simply an optimal flow.

It is well understood that users will typically not coordinate their actions to induce a flow that minimizes total disutility. There is a huge body of literature (particularly in the setting of static flows [20]) investigating this phenomenon. In the traffic setting, the relevance of an optimal flow represented by an answer to this question comes primarily via the possibility of pricing. By putting appropriate tolls on roads, we can influence the behaviour of users and the resulting dynamic equilibrium. Thus:

Problem 2

How can one set tolls (possibly time-varying) on the arcs of a given instance so that an optimal flow is obtained in dynamic equilibrium?

One subtlety is that since dynamic equilibria need not be precisely unique, there is a distinction between tolls that induce an optimal flow as an equilibrium, compared to tolls for which all dynamic equilibria are optimal. (This is called weak and strong enforcement by Harks [14] in a general pricing setting). We will return to this subtlety shortly.

Questions like these are of great interest to transportation economists. However, most work in that community has focused on obtaining a fine-grained understanding of very restricted topologies (such as a single link, or multiple parallel links); see [25] for a survey.

Both of these questions (for general network topologies) were considered by Yang and Meng [28] in a discrete time setting, by exploiting the notion of time-expanded graphs. This is a standard tool in the area of flows over time; discrete versions all of the optimization questions concerning flows over time mentioned earlier can (in a sense) be dealt with in this way. A node v in the graph is expanded to a collection (v, i) of nodes, for $i \in \mathbb {Z}$ in a suitable interval, and an arc vw of delay $\tau _{vw}$ becomes a collection of arcs $((v,i), (w,i+\tau _{vw}))$ (this assumes a scaling so that $\tau _{vw}$ is a length in multiples of the chosen discrete timesteps). Scheduling costs are encoded by appropriately setting arc costs from (t, i) to a supersink $t'$ for each i, and the problem can be solved by a minimum cost static flow computation. A primary disadvantage of this approach (and in the use of time-expanded graphs more generally) is that the running time of the algorithm depends polynomially on the number of time steps, which can be very large. Further, it cannot be used to exactly solve the continuous time version (our interest in this paper); by discretizing time, it can be used to approximate it, but the size of the time-expanded graph is inversely proportional to the step size of the discretization. In the same work [28], the authors also observe that in the discrete setting, an answer to the second question can be obtained from the time-expanded graph as well. Taking the LP describing the minimum cost flow problem on the time-expanded graph, the optimal dual solution to this LP provides the necessary tolls to enforce (weakly) an optimal flow. (This is no big surprise—dual variables can frequently be interpreted as prices.)

An Assumption on $\rho$. Suppose we consider $\rho$ in the standard form given in (1), but with $\beta > \alpha$. This means that commuting is considered to be less unpleasant than arriving early. A user arriving earlier than time 0 at the sink would be better off “waiting” at the sink before leaving, in order to pay a scheduling cost of 0. Whether waiting in this way is allowed or not depends on the precise way one specifies the model, but it is most natural (and convenient) to allow this. If we do so, then it is clear that a scheduling cost function $\rho$ can be replaced by

$$ \hat{\rho }(\theta ) := \min _{\xi \ge \theta } \rho (\xi ) + \alpha (\xi - \theta ) $$

without changing the optimal flow (except there is no longer any incentive to wait at the sink, and we need not even allow it). Then $\theta \rightarrow \hat{\rho }(\theta ) + \alpha \theta$ is nondecreasing. From now on, we always assume that $\rho$ satisfies this; we will call it the growth bound on $\rho$.

Our Results. We give a combinatorial algorithm to compute an optimal flow. Similarly to the case of earliest arrival flows, this flow can be necessarily complicated, and involves a description length that is exponential in the input size.

The algorithm is also similar to that for computing an earliest arrival flow. It is based on the (possibly exponentially sized) path decomposition of a minimum cost flow into successive shortest paths. In particular, suppose we choose the scheduling cost function to be as in (1), with $\beta =\alpha$ and $\gamma =\infty$. Then the disutility a user experiences is precisely described by how much before time 0 they depart; all users must arrive by time 0 to ensure finite cost. This is precisely the reversal (both in time and direction of all arcs) of an earliest arrival flow, from the sink to the source. Our algorithm will be the same as the earliest arrival flow in this case. This also shows that it may be the case that all optimal solutions to Problem 1 require exponential size (as a function of the input encoding length), since this is the case for earliest arrival flows.

Despite the close relation to earliest arrival flows, the proof of optimality of our algorithm is rather different. A key reason for this is the following. As mentioned, earliest arrival flows have the strong property that the amount of flow arriving before a given deadline $T'$ is the maximum possible, simultaneously for all choices of $T'$ (up to some maximum depending on the total amount of flow being sent). This implies that an earliest arrival flow certainly minimizes the average arrival time amongst all possible flows [15], but is a substantially stronger property. A natural analog of this stronger property in our setting would be to ask for a flow for which, simultaneously for any given cost horizon $C' \le C$, the amount of flow consisting of agents experiencing disutility at most $C'$ is as large as possible. Unfortunately, in general no such flow exists. The example is too involved to discuss here, but it relates to some questions on the behaviour of dynamic equilibria in this model that are investigated in a parallel manuscript [11].

Since the proofs for earliest arrival flows [2, 12, 19, 27] show this stronger property which does not generalize, we take a different approach. Our proof is based on duality (of an infinite dimensional LP, though we do not require any technical results on such LPs). The main technical challenge in our work comes from determining the correct ansatz for the dual solution, as well as exploiting properties of the residual networks obtained from the successive shortest paths algorithm in precisely the right way to demonstrate certain complementary slackness conditions. As was the case with the time-expanded graph approach, the optimal dual solution immediately provides us with the tolls. However, we obtain an explicit formula for the optimal tolls, in terms of the successive shortest paths of the graph (see Sect. 3). This may be useful in obtaining a better structural understanding of optimal tolls, beyond just their computation. We also remark that a corollary of our result is that there is always an optimal solution without waiting (except at the source).

Consider for a moment the model where users cannot choose their departure time, but instead are released from the source at a fixed rate $u_0$, and simply wish to reach the destination as early as possible. This is the game-theoretic model that has received the most attention from the flow-over-time perspective [3, 5, 6, 16, 22]. Our construction of optimal tolls is applicable to this model as well. Reverse all arcs, as well as the role of the source and sink (thus making s the new sink), and also introduce a replacement sink $s'$ and arc $ss'$ of capacity $u_0$ in the original instance. Then by choosing $\rho$ as described in (1) with $\beta =\alpha$, $\gamma =\infty$, the optimal flow is an earliest arrival flow, and the tolls we construct will induce it in the original instance (after appropriate time reversal).

We now return to the subtlety alluded to earlier: the distinction between strongly enforcing an optimal flow, and only weakly enforcing it.

Consider the simple instance shown. Suppose that the outflow of arc e is larger than 1 for some period in the optimum flow, due to the choice of scheduling cost function. In this period, one unit of flow would take the bottom arc g, and the rest will be routed on f. Since the total cost (including tolls) of all users is the same in a tolled dynamic equilibrium, a toll of cost equivalent to a unit delay on arc g is needed in this period to induce the optimal flow. But then it will also be an equilibrium to send all flow in this period along f.

To strongly enforce an optimal flow, we need more flexible tolls. One way that we can do it is by “tolling lanes”. If we are allowed to dynamically divide up the capacity of an arc into “lanes” (say a “fast lane” and a “slow lane”), and then separately set time-varying tolls on each lane, then we can strongly enforce any optimal flow. We discuss this further in Sect. 5. We are not aware of settings where this phenomenon has been previously observed, and it would be interesting to explore this further in a more applied context.

Outline of the Paper. We introduce some basic notation and notions, as well as formally define our model, in Sect. 2. In Sect. 3, we describe our algorithm, and show that it returns a feasible flow over time; we restrict ourselves to the most relevant case of a strictly unimodal scheduling cost function. In Sect. 4 we show optimality of this algorithm, and in Sect. 5 we derive optimal tolls from this analysis.

2 Model and Preliminaries

The notation $(z)^+$ is used to denote the nonnegative part of z, i.e., $(z)^+ = \max \{z,0\}$. Given $v: X \rightarrow \mathbb {R}$ and $A \subseteq X$, we will use the shorthand notation $v(A) := \sum _{a \in A} v(a)$. We will not distinguish between a map $v: X \rightarrow \mathbb {R}$ and a vector in $\mathbb {R}^X$, and so the notation $v_a$ and v(a) is interchangeable. All graphs will be directed and (purely for notational convenience) simple and without digons.

Static Flows. Let $G=(V,E)$ be a directed graph, with source node $s \in V$ and sink node $t \in V$. Each arc $e \in E$ has a capacity $\nu _e$ and a delay $\tau _e$ (both nonnegative). We use $\delta ^+(v)$ to denote the set of arcs in E with tail v, and $\delta ^-(v)$ the set of arcs with head v.

Consider some $f: E \rightarrow \mathbb {R}_+$ (which we will equivalently view as a vector in $\mathbb {R}_+^E$). We use $\nabla f_v$ to denote the net flow into $v \in V$; a (static) s-t-flow satisfies the usual flow conservation conditions. Given an s-t-flow f, its residual network $G^f = (V, E^f)$ is defined by

$$\begin{aligned} E^f = \{ vw : vw \in E \text { and } f_{vw} < \nu _{vw}\} \cup \{ vw : wv \in E \text { and } f_{wv} > 0 \}. \end{aligned}$$

Call arcs in $E^f \cap E$ forward arcs and arcs in ${E^f}{\setminus }{ E}$ backwards arcs. The residual capacity $\nu ^f_e$ of an arc $e \in E^f$ is then $\nu ^f_{vw} = \nu _{vw} - f_{vw}$ for vw a forward arc, and $\nu ^f_{vw} = f_{wv}$ for vw a backwards arc. We also define $\tau _{vw} = -\tau _{wv}$ for all backwards arcs vw.

Given a subset $F \subseteq E$, we use $\chi (F)$ to denote the characteristic vector of F. We make the definitions and . Given $f,g \in \mathbb {R}_+^{E}$, we define $f+g$ in the obvious way, and also define , by interpreting a negative value on vw instead as a positive value on wv.

Flows over Time. Consider some $f: E \times \mathbb {R}\rightarrow \mathbb {R}_+$. We will generally write $f_e(\theta )$ rather than $f(e, \theta )$. Define the net flow into v at time $\theta$ by

$$\begin{aligned} \nabla f_v(\theta ) := \sum _{e \in \delta ^-(v)} f_e(\theta - \tau _e) - \sum _{e \in \delta ^+(v)} f_e(\theta ). \end{aligned}$$

Note that $f_e(\theta )$ represents the flow entering arc e at time $\theta$; this flow will exit the arc at time $\theta + \tau _e$ (explaining the asymmetry between the terms for flow entering and flow leaving in the above).

We say that f is a flow over time of value Q if the following hold.

• (i) For each $e \in E$, $f_e$ is integrable and has compact support.

• (ii) $\int _{-\infty }^\infty \nabla f_v(\theta )d\theta = Q(\mathbf {1}_{v = t} - \mathbf {1}_{v=s})$ for all $v \in V$.

• (iii) $\int _{-\infty }^\xi \nabla f_v(\theta )d\theta \ge 0$ for all $v \in {V}{\setminus }\{s\}$ and $\xi \in \mathbb {R}$.

• (iv) $f_e(\theta ) \le \nu _e$ for all $e \in E$ and $\theta \in \mathbb {R}$.

Note that this definition allows for flow to wait at a node; to disallow this and consider only flows over time without waiting, we would replace (iii) with the condition that $\nabla f_v(\theta ) = 0$ for all $v \in {V}{\setminus }\{s,t\}$ and $\theta \in \mathbb {R}$.

We also have a natural notion of a residual network in the flow over time setting. Define, for any flow over time f and $\theta \in \mathbb {R}$,

$$ E^f(\theta ) = \{ vw : vw \in E \text { and } f_{vw}(\theta ) < \nu _{vw}\} \cup \{ vw : wv \in E \text { and } f_{wv}(\theta - \tau _{wv}) > 0\}. $$

Minimizing Scheduling Cost. We are concerned with the following optimization problem. Given a scheduling cost function $\rho : \mathbb {R}\rightarrow \mathbb {R}_+$, as well as a value $\alpha > 0$, determine a flow over time f of value Q that minimizes the sum of the commute cost $\alpha \sum _{e \in E} \tau _e \cdot \int _{\mathbb {R}}f_e(\theta )d\theta$ and the scheduling cost $\int _{\mathbb {R}}\nabla f_t(\theta )\cdot \rho (\theta ) d\theta$. As already discussed, we assume that $\rho$ satisfies the growth bound, i.e., that $\theta \rightarrow \rho (\theta ) + \alpha \theta$ is nondecreasing. This ensures that waiting at t is not needed, which is in fact disallowed by our definition¹, and makes various arguments cleaner. We will also make the assumption that $\rho$ is strongly unimodal². We then assume w.l.o.g. that the minimizer of $\rho$ is at 0, and that $\rho (0) = 0$. For further technical convenience, by adjusting $\rho$ on a set of measure zero we take $\rho$ to be lower semi-continuous.

The unimodal assumption is not necessary; the algorithm and analysis can be extended to essentially general $\rho$, under some very weak technical conditions. We postpone discussion to the full version of the paper; no major new technical ideas are needed.

We also assume that we are able to query $\rho ^{-1}(y)$ for a given rational $y > 0$, obtaining a pair of solutions (one positive, one negative) of moderate bit complexity.

3 A Combinatorial Algorithm

In this section we present an algorithm that computes an optimal flow over time, assuming that $\rho$ is strongly unimodal. The proof of optimality is discussed in Sect. 4.

We begin by recalling the successive shortest paths (SSP) algorithm for computing a minimum cost static flow. It is not a polynomial time algorithm, so it is deficient as an algorithm for static flows, but it provides a structure that is relevant for flows over time. This is of course well known from its role in constructing earliest arrival flows, which we will briefly detail.

The SSP algorithm construct a sequence of paths $(P_1, P_2, \ldots )$ and associated amounts $(x_1, x_2, \ldots )$ inductively as follows. Suppose $P_1, \ldots , P_j$ and $x_1, \ldots , x_j$ have been defined. Let $f^{(j)} = \sum _{i=1}^j x_i \chi (P_i)$, and let $G_j$ denote the residual graph of $f^{(j)}$ ($G_0$ being the original network). Also let $d_j(v,w)$ denote the length (w.r.t. arc delays $\tau$ in $G_j$) of a shortest path from v to w in $G_j$ (this may be infinite). By construction, $G_j$ will contain no negative cost cycles, so that $d_j$ is computable. If ${d_{j}}(s,t) = \infty$, we are done; set $m := j$. Otherwise, define $P_{j+1}$ to be any shortest s-t-path in $G_j$, and $x_{j+1}$ the minimum capacity in $G_j$ of an arc in $P_{j+1}$. It can be shown that $\sum _{j=1}^r \tilde{x}_j \chi (P_j)$, with r and $\tilde{x}$ defined such that $\tilde{x}_j = x_j$ for $j < r$, $0 \le \tilde{x}_r \le x_r$ and $\sum _{j=1}^r \tilde{x}_j = M$, is a minimum cost flow of value M, as long as M is not larger than the value of a maximum flow.

To construct an earliest arrival flow of value Q and time horizon T, we (informally) send flow at rate $x_j$ along path $P_j$ for the time interval $[0, T - \tau (P_j)]$, for each $j \in [m]$ (if $\tau (P_j) > T$, we send no flow along the path). By this, we mean that for each $e=vw \in P_j$, we increase by $x_j$ the value of $f_e(\theta )$ for $\theta \in [d_{j-1}(s,v), T - d_{j-1}(v,t)]$ (or if e is a backwards arc, we instead decrease $f_{wv}(\theta -\tau _{wv})$). An argument is needed to show that this defines a valid flow, since we must not violate the capacity constraints, and moreover, $P_j$ may contain reverse arcs not present in G.

We are now ready to describe our algorithm for minimizing the disutility, which is a natural variation on the earliest arrival flow algorithm. It is also constructed from the successive shortest paths, but using a cost horizon rather than a time horizon. For now, consider C to be a given value (it will be the “cost horizon”). For each $j \in [m]$ with $\alpha d_{j-1}(s,t) \le C$, we send flow at rate $x_j$ along path $P_j$ for the time interval $[a_j, b_j]$ chosen maximally so that $\rho (\xi + d_{j-1}(s,t)) \le C - \alpha d_{j-1}(s,t)$ for all $\xi \in [a_j, b_j]$. (If $\rho$ is continuous, then of course $\rho (a_j + d_{j-1}(s,t)) = \rho (b_j + d_{j-1}(s,t)) = C - \alpha d_{j-1}(s,t)$). Note that a user leaving at time $a_j$ or $b_j$ and using path $P_j$, without waiting at any moment, incurs disutility C; whereas a user leaving at some time $\theta \in (a_j, b_j)$ and using path $P_j$ will incur a strictly smaller total cost.

As we will shortly argue, this results in a feasible flow over time f. Given this, its value will be $\sum _{j=1}^m x_j(b_j - a_j)$. It is easy to see that this value changes continuously and monotonically with C (here we use the strong unimodality). Thus a bisection search can be used to determine the correct choice of C for a given value Q. Alternatively, bisection search can be avoided by using Megiddo’s parametric search technique [18]; this will ensure a strongly polynomial running time, if queries to $\rho ^{-1}$ are considered to be of unit cost.

Feasibility. Given a vertex $v\in V$, a time $\theta \in \mathbb {R}$ and $j\in [m]$, let

$$ c_j(v,\theta )=\alpha d_{j-1}(s,t) + \rho (\theta + d_{j-1}(v,t)). $$

If $v\in P_j$ then $c_j(v,\theta )$ is the travel cost of a user that utilizes path $P_j$ and passes through node v at time $\theta$; there does not seem to be a simple interpretation if $v \notin P_j$ however. Now define

$$\begin{aligned} J(v,\theta ) = \max \{ j \in [m] : c_j(v,\theta ) \le C \}, \end{aligned}$$

(2)

with the convention that the maximum over the empty set is 0. The motivation for this definition comes from the following theorem, which completely characterizes f.

Theorem 1

$f_{vw}(\theta ) = f_{vw}^{(J(v,\theta ))}$ for any $vw \in E$ and $\theta \in \mathbb {R}$.

Since f has value Q and satisfies flow conservation by construction, the feasibility of f is an immediate corollary of this theorem. We sketch the proof in the appendix.

4 Optimality

Duality-Based Certificates of Optimality. We can write the problem we are interested in as a (doubly) infinite linear program as follows:

(3)

Here, $z_v(\theta )$ represents the amount of flow waiting at node v at time $\theta$ (which must always be nonnegative). The travel cost is captured on a per-arc basis, including waiting time as well.

The following theorem provides a certificate of optimality of a feasible solution to (3).

Theorem 2

Let f be a flow over time with value Q, and suppose that $\pi : V \times \mathbb {R}\rightarrow \mathbb {R}$ satisfies the following, for some choice of C:

• (i) $\theta \rightarrow \pi _v(\theta ) - \alpha \theta$ is nonincreasing.

• (ii) $\pi _w(\theta + \tau _{vw}) \le \pi _v(\theta ) + \alpha \tau _{vw}$ for all $\theta \in \mathbb {R}, vw \in E^f(\theta )$.

• (iii) $\pi _s(\theta ) = 0$ for all $\theta \in \mathbb {R}$.

• (iv) $\pi _t(\theta ) = (C - \rho (\theta ))^+$ for all $\theta \in \mathbb {R}$, and $\nabla f_t(\theta ) = 0$ whenever $\rho (\theta ) > C$.

Then f is an optimal solution.

Essentially, $\pi _v(\theta )$ are dual variables, and the assumptions of the theorem are that f and $\pi$ satisfy the complementary slackness conditions. There are many extensions of LP duality theory to infinite dimensional settings, e.g., [13, 21]; however the situation is subtle, since strong duality and even weak duality can fail [21]. We prefer to avoid technicalities and derive it directly (the proof is given in the full version).

The Dual Prescription. We now give a certificate of optimality $\pi : V \times \mathbb {R}\rightarrow \mathbb {R}$ for (3) that satisfies the conditions of the above LP. Given a vertex $v\in V$ and a time $\theta \in \mathbb {R}$ let

$$\begin{aligned} \pi _v(\theta )&=\max \{\pi '_v(\theta ), \bar{\pi }_v(\theta ), 0\}&\\[0.3em] \text {where} \qquad \qquad \pi '_v(\theta )&= - \alpha d_{J(v,\theta )}(v,s),\\ \bar{\pi }_v(\theta )&=C-\alpha d_{J(v,\theta )}(v,t) - \rho (\theta +d_{J(v,\theta )}(v,t)). \end{aligned}$$

Notice that $\pi _s(\theta )=0$ and $\pi _t(\theta )=\max \{C-\rho (\theta ),0\}$ for all $\theta \in \mathbb {R}$ and thus conditions (iii) and (iv) of Theorem 2 hold. The bulk of the technical work is in showing the remaining conditions; we sketch some part of the proof in the appendix.

5 Optimal Tolls

Tolls $\mu : E \times \mathbb {R}\rightarrow \mathbb {R}_+$ are per-arc, time-varying and nonnegative. The value $\mu _e(\xi )$ represents the toll a user is charged upon entering the link at time $\xi$.

We have the following theorem.

Theorem 3

Let $(f,\pi )$ be an optimal primal-dual solution to (3) (as constructed in Sects. 3 and 4) and define, for each $vw \in E$,

$$ \mu _{vw}(\theta ) = (\pi _w(\theta + \tau _{vw}) - \pi _v(\theta ) - \alpha \tau _{vw})^+. $$

Then f is a dynamic equilibrium under tolls $\mu$.

Of course, to make sense of this theorem we must know what is meant by a dynamic equilibrium under tolls. A precise definition requires introducing the full game-theoretic fluid queueing model (also known as the Vickrey bottleneck model) [16, 26]. Tolls and departure time choice can be introduced into the definition of a dynamic equilibrium discussed in these works. Rather than going this route, we will show that the tolls satisfy a strong property that very clearly ensures the equilibrium property.

We show (in the full version—it is straightforward) that the following holds. A user starting from some $v \in V$ at some time $\theta \in \mathbb {R}$ cannot incur a total cost (including scheduling cost, and tolls and commuting cost from this point forward) less than $C - \pi _v(\theta )$. This is even allowing the user to take any link at any time, as if no other users were present in the network. Since the flow represents a solution where all users incur a total cost of precisely C, this must certainly be an equilibrium.

As already discussed, we cannot in general strongly enforce an optimal flow. The following shows that the “lane tolling” approach suffices to do this.

Theorem 4

Let $f, \pi$ and $\mu$ be as in the previous theorem, and suppose g is any dynamic equilibrium satisfying $g_e(\theta ) \le f_e(\theta )$ for all $e \in E$, $\theta \in \mathbb {R}$. Then $g=f$.

Essentially, being able to dynamically split and separately toll the capacity of a link allows us to easily rule out all other potential equilibria just by using tolls to artificially constrict the capacities (in addition to choosing tolls that weakly enforce the desired flow, which is still needed). Tolling in this way seems quite distant from what could be imaginable in realistic traffic scenarios. But it does raise the interesting question of whether there is a tolling scheme which can strongly enforce an optimum flow, but which is more restricted (and more plausible) than fully dynamic lane tolling. Another natural question would be to determine if an optimum flow can be strongly enforced using lane tolling only on certain specified edges. We leave these as open questions.

A Some Omitted Proofs

Proof

(Theorem 1). The key ingredient is the following observation.

Lemma 1

$c_j(v,\theta )$ is nondecreasing with j for any $\theta \in \mathbb {R}$.

Proof

Consider any $j \in [m-1]$; we show that $c_{j+1}(v,\theta ) \ge c_j(v,\theta )$. Suppose Q is a shortest v-t-path in $G_{j-1}$, so $\tau (Q) = d_{j-1}(v,t)$. Consider the unit v-t flow $g = \chi (P_{j+1}) - \chi (P_j) + \chi (Q)$ in . Now observe that the support of g is contained in $G_{j}$: $P_{j+1}$ and are certainly contained in $G_j$; and if $e \in Q \cap (E_{j-1}{\setminus }{E_j)}$, then $e \in P_j$. Since $G_j$ contains no negative cost cycles, the cost of g is at least that of a shortest v-t-path in $G_j$, and so $d_{j}(v,t) \le \tau (P_{j+1})- \tau (P_{j}) +\tau (Q)$. Finally, we can conclude

$$\begin{aligned} c_j(v, \theta )&= \alpha d_{j}(s,t) +\rho (\theta +d_{j-1}(v,t)) - \rho (\theta +d_{j-1}(v,t))+\rho (\theta +d_{j}(v,t))\\&\ge \alpha d_{j}(s,t) +\rho (\theta +d_{j-1}(v,t)) - \alpha (d_{j}(v,t)-d_{j-1}(v,t))\\&\ge \alpha d_{j-1}(s,t) +\rho (\theta +d_{j-1}(v,t)), \end{aligned}$$

where the first inequality follows from the growth assumption, using $d_{j}(v,t)\ge d_{j-1}(v,t)$.    $\square$

Fix some $vw \in E$ and $\theta \in \mathbb {R}$. Consider now any $P_j$ (with $\alpha \tau (P_j) \le C$, so that it is used for a nontrivial interval), with $vw \in P_j$. Since $P_j$ is a shortest path in $G_{j-1}$, if we send flow along this path starting from some time $\xi$, it will arrive at v at time $\xi + d_{j-1}(s,v)$. Considering the definition of the interval $[a_j, b_j]$, we see that $P_j$ contributes flow to vw at time $\theta$ if $c_j(v,\theta ) \le C$. By Lemma 1, this occurs precisely if $j \le J(v,\theta )$. Considering in similar fashion paths $P_j$ with $wv \in P_j$ (and noting that $J(w,\theta + \tau _{vw}) = J(v,\theta )$), the claim follows.    $\square$

Optimality. We give the proof that $\pi$ satisfies property (ii) in Theorem 2. The proof of property (i), while differing in the details, has a very similar flavour.

We first state a technical lemma involving distances in the residual graphs $G_j$; we omit the proof.

Lemma 2

 

• (a) For all $v \in V$, $d_j(v,s)$ is nonincreasing with j.

• (b) For all $v \in V$ and $j \in [m]$, $d_{j-1}(v,t)-d_{j-1}(s,t)=d_{j}(v,s)$.

Lemma 3

If $vw \in E^f(\theta )$, then $\pi _w(\theta + \tau _{vw}) \le \pi _v(\theta ) + \alpha \tau _{vw}$.

Proof

Let $j := J(v,\theta )$ and $\ell := J(w,\theta + \tau _{vw})$. Note that since $vw \in E^f(\theta )$, Theorem 1 implies that $vw \in E_j$.

• Case 1: $\pi _w(\theta +\tau _{vw}) = - \alpha d_{\ell }(w,s)$.

  If $\ell \le j$, then

  

  So suppose $\ell >j$. By the definition of $J(w,\theta + \tau _{vw})$ we know that

  $$\begin{aligned} \alpha d_{\ell -1}(s,t) + \rho (\theta +\tau _{vw}+ d_{\ell -1}(w,t))\le C. \end{aligned}$$

  (4)

  Since $vw \in E_j$ and $d_{j}(w,t)\le d_{\ell -1}(w,t)$, we also have

  $$\begin{aligned} \theta +d_{j}(v,t)\le \theta +\tau _{vw}+d_{\ell -1}(w,t). \end{aligned}$$

  (5)

  Thus

  

  where the second inequality follows from the growth assumption and (5).

• Case 2: $\pi _w(\theta +\tau _{vw}) = C-\alpha d_{\ell }(w,t) - \rho (\theta +\tau _{vw}+d_{\ell }(w,t))$.

  If $\ell \ge j$, since $vw \in E_j$ and $d_{j}(w,t)\le d_{\ell }(w,t)$, we have that

  $$\begin{aligned} \theta +d_{j}(v,t)\le \theta +\tau _{vw}+d_{\ell }(w,t). \end{aligned}$$

  (6)

  As a consequence, exploiting also the growth assumption, we have

  $$\begin{aligned} \pi _v(\theta )&\ge C-\alpha d_{j}(v,t) - \rho (\theta +d_{j}(v,t))\\&\ge C-\alpha d_{j}(v,t) - \rho (\theta +\tau _{vw}+d_{\ell }(w,t)) - \alpha \left( \tau _{vw}+d_{\ell }(w,t)-d_{j}(v,t)\right) \\&= C- \rho (\theta +\tau _{vw}+d_{\ell }(w,t)) - \alpha \tau _{vw} -\alpha d_{\ell }(w,t)\\&= \pi _w(\theta +\tau _{vw})-\alpha \tau _{vw}. \end{aligned}$$

  If $\ell <j$, by definition of $J(w,\theta +\tau _{vw})$ we have that

  $$\begin{aligned} \alpha d_{\ell }(s,t) + \rho (\theta +\tau _{vw}+ d_{\ell }(w,t))>C. \end{aligned}$$

  (7)

  Thus

  

   $\square$