Pricing and revenue maximization over a multicommodity transportation network: the nonlinear demand case

Abstract

This paper is concerned with the design of efficient exact and heuristic algorithms for addressing a bilevel network pricing problem where demand is a nonlinear function of travel cost. The exact method is based on the piecewise linear approximation of the demand function, yielding mixed integer programming formulations, while heuristic procedures are developed within a bilevel trust region framework.

1 Introduction

In its simplest form (see Labbé et al. [10]), the network pricing problem consists in setting revenue maximizing tolls on a congestion-free, multi-commodity transportation network, under the assumption that flows are assigned to cheapest paths with respect to a generalized cost. Kuiteing et al. [8] considered an extension where demand decreases linearly with travel cost, and the goal of the present work is to address the case of nonlinear price-demand relationships, which is much more challenging from the computational point of view.

The key elements of the paper are: a formulation of the bilevel model; the development of a quasi-exact method based on approximation, discretization and linearization techniques; the design of two heuristics based on the trust region paradigm (see Conn et al. [4]); numerical experiments and sensitivity analysis with respect to demand elasticity.

2 Model formulation

Consider a network defined over the underlying graph $G = ({\mathcal {N}}, {\mathcal {A}})$, with node set ${\mathcal {N}}$ and arc set ${\mathcal {A}}=({\mathcal {A}}_1,{\mathcal {A}}_2)$. Each arc of ${\mathcal {A}}$ is endowed with a unit weight $c_a$, while a toll $t_a$, to be determined by the leader, is associated with arcs in the subset ${\mathcal {A}}_1\subseteq {\mathcal {A}}$. In this context, the generic term ‘weight’ may designate an out-of-pocket cost, a delay, or any attribute of disutility. We assume that weights and tolls are expressed in the same units, yielding the generalized cost $c_a+t_a$. Let ${{\mathcal {K}}}$ denote the set of origin-destination (OD) pairs or commodities. For each $k\in {{\mathcal {K}}}$ demand from the origin o(k) to its destination d(k) is provided by a function $n_k(u_k)$ of the minimal travel cost $u_k$ from o(k) to d(k).

For each $k\in {{\mathcal {K}}}$, let $h_p^k$ denote the proportion of demand assigned to path $p\in {\mathcal {P}}_k$, where ${\mathcal {P}}_k$ is the set of paths from o(k) to d(k). Since only cheapest paths with respect to t can carry positive flow (proportions), we have that, for all k in ${\mathcal {K}}$,

$$\begin{aligned} h^k\in \arg \min _{h^{'k}}&\sum _{p \in {\mathcal {P}}_k } \Bigl ( \sum _{a\in p} c_a +\sum _{a\in p\cap A_1} t_a \Bigr ) h_p^{'k}\\ \hbox {s.t.}&\sum _{p \in {\mathcal {P}}_k }h_p^{'k} = 1, \end{aligned}$$

and the cost of a cheapest path is denoted $u_k$, where

$$\begin{aligned} u_k=\sum _{p \in {\mathcal {P}}_k } \Bigl ( \sum _{a\in p} {c_a} +\sum _{a\in p\cap A_1} t_a \Bigr ) h_p^{k}. \end{aligned}$$

The validity of the latter expression rests on the fact that paths with positive flow proportions must bear the same cheapest cost, and the flow proportions must sum up to one. This yields the bilevel mathematical program

$$\begin{aligned}&\mathrm{P:}\quad \max _{t\ge 0,h , u} \ \sum _{k \in {\mathcal {K}}} \sum _{p \in {\mathcal {P}}_k } {\sum _{ a \in p\cap {{\mathcal {A}}}_1} } t_a n_k(u_k) h^{k}_{p} \\&\quad \text {s.t. } \quad \forall \ k\in {\mathcal {K}}{\left\{ \begin{array}{ll} u_k \ = \ \displaystyle \sum _{p \in {\mathcal {P}}_k} \Bigl (\sum _{a \in p}c_a + \sum _{a \in p\bigcap {\mathcal {A}}_1} t_a \Bigl ) {h^{k}_{p}}\\ h^{k} \in \displaystyle \arg \min _{h^{'k} } \sum _{p \in {\mathcal {P}}_k } \Bigl ( \sum _{a\in p} c_a + \sum _{a \in p\cap {\mathcal {A}}_1} t_a \Bigl ) h^{'k}_{p} \\ \quad \text {s.t. } \quad \displaystyle \sum _{p \in {\mathcal {P}}_k} h^{'k}_{p} \ = 1. \end{array}\right. } \end{aligned}$$

Two remarks are in order:

• The equation that defines $u_k$ is an upper level constraint that must be enforced by the leader. Its role is to ensure compatibility between the least costs and the corresponding cheapest path flows. This constraint does not bind the followers, i.e., the road users.

• In this ‘optimistic’ framework, the leader is allowed to select, among cheapest paths, the ones that yield maximum revenue. It follows that there exists an optimal solution where, for each origin-destination pair k, only one variable $h_k^p$ is positive and its value must equal 1. Without loss of generality, we henceforth assume that flow proportions are binary-valued.

A single-level nonlinear reformulation of the bilevel model is readily obtained by following the steps suggested in Didi-Biha et al. [6]: introduce variables $T^k$ equal to the revenue per flow unit (equivalently the toll on cheapest path) and express the lower-level optimality conditions as linear constraints involving big-M constants (see [8] for their estimates). This yields the formulation

$$\begin{aligned}&\overline{\mathrm{P}}:\quad \max _{t,h,T,u} \ \sum _{k \in {\mathcal {K}}} n_k(u_k) T^k \nonumber \\&\quad \text {s.t. } \displaystyle \sum _{a\in p}c_a + {\sum _{a \in p\cap {\mathcal {A}}_1}} t_a - M_p^{k} \ \left( 1-h^{k}_{p}\right) \ \le u_k&\forall \ p\in {\mathcal {P}}_k, \forall \ k \in {\mathcal {K}} \end{aligned}$$

(1)

$$\begin{aligned}&\qquad \displaystyle u_k \ \le \ \sum _{a\in p} c_a + \sum _{a \in p\bigcap {\mathcal {A}}_1} t_a&\forall \ p\in {\mathcal {P}}_k, \forall \ k\in {\mathcal {K}}\end{aligned}$$

(2)

$$\begin{aligned}&\qquad \displaystyle u_k \ = \ T^k + \sum _{p \in {\mathcal {P}}_k} h^{k}_{p}\ \sum _{a \in p}c_a&\forall \ k\in {\mathcal {K}} \end{aligned}$$

(3)

$$\begin{aligned}&\qquad \displaystyle \sum _{p \in {\mathcal {P}}_k} h^{k}_{p} \ = \ 1.&\forall \ k\in {\mathcal {K}}\end{aligned}$$

(4)

$$\begin{aligned}&\qquad \displaystyle h^k_p \in \{0,1\}&\forall p\in {\mathcal {P}}_k, \forall \ k\in {\mathcal {K}} \end{aligned}$$

(5)

where constraints (1) and (2) ensure that flow is assigned to cheapest paths, (3) establishes consistency between $T^k$ and $u_k$, and constraints (4) and (5) ensure that commodity flows are not split between paths. Based on Eq. (3), one can replace $T^k$ by $u_k - \sum _{p \in {\mathcal {P}}_k} h^{k}_{p}\ \sum _{a \in p}c_a$. This yields the nonlinear binary program

$$\begin{aligned}&\mathrm{P1:} \quad \max _{t,h,u} \sum _{k \in {\mathcal {K}}} n_k(u_k) \Bigl ( u_k - \sum _{p\in {\mathcal {P}}_k} h^k_p \sum _{a\in p} c_a \Bigr ) \\&\quad \text {s.t. } (1)-(2) \hbox { and } (4)-(5), \end{aligned}$$

which will be used from now on.

In this paper, travel demand either has a constant elasticity or decays exponentially, i.e., $n_k(u_k)=\alpha _k u_k^{-\beta _k}$ or $n_k(u_k)=\alpha _k \exp (-\beta _k u_k)$, where $\alpha _k\ge 0$ and $\beta _k>1$. Both are convex and widely used in economics. (See Moore [12].) In both cases, the resulting revenue function $n_k(u_k)u_k$ is either convex and decreasing, or pseudo-concave (increasing then decreasing) as depicted in Fig. 1.

Fig. 1

Graph of function $n_k(u_k)u_k$; ${{\underline{u}}}_k$ is a lower bound on the cost of any path

3 An exact method

In this section, we describe an exact method inspired by the classical cutting plane principle introduced by Kelley [9], and applied to the hypograph (respectively epigraph) of the first term (respectively second term) in the objective. More precisely, similar to Audet et al. [2] in the context of non-convex quadratic programming, we replace these functions by piecewise linear over-estimations (respectively under-estimations), and derive an MIP that provides an upper bound on the objective of P1.

3.1 Approximation of ${\mathbf {P1}}$

The toll revenue in the objective of P1 can be expressed as the difference between the total generalized cost and the total travel time, i.e.,

$$\begin{aligned} \sum _{k \in {\mathcal {K}}} n_k(u_k) u_k - \sum _{k \in {\mathcal {K}}} n_k(u_k)\Bigl ( \sum _{p\in {\mathcal {P}}_k} h^k_p \sum _{a\in p} c_a \Bigr ) \end{aligned}$$

(6)

Let us first focus on the second term of (6). Since both forms of the demand function $n_k(u_k)$ are convex, the latter can be underestimated by its first-order Taylor development

$$\begin{aligned} n_k(u_k^l)+\frac{dn_k(u_k^l)}{du_k}(u_k-u_k^l). \end{aligned}$$

Setting $b_k^l=\frac{dn_k(u_k^l)}{du_k}$ and $a_k^l=n_k(u_k^l)-u_k^l b_k^l$ and upon introduction of the variable $y_k$, we append to the model the constraints

$$\begin{aligned} y_k\ge a_k^l+b_k^l u_k. \end{aligned}$$

(7)

At optimality, $(u_k, y_k)$ must lie on a face of the polyhedron defined by constraints (7). The process is initiated with lower and upper bounds $\underline{u}_k$ and $\overline{u}_k$ determined a priori (see Fig. 2). For instance, ${{\underline{u}}}_k$ and ${{\bar{u}}}_k$ can be set to the cost of a cheapest path for OD pair k when, respectively, $t_a=0$ (no tolls) and $t_a=\infty$ (no toll arcs are allowed) for all $a\in {{{\mathcal {A}}}}_1$.

Fig. 2

Under-approximation of $n_k(u_k)$

Upon substituting $n_k(u_k)$ by $y_k$, the expression $\displaystyle n_k(u_k) \sum \nolimits _{p\in {\mathcal {P}}_k} h^k_p \sum \nolimits _{a\in p} c_a$ in the objective function becomes $\displaystyle y_k\sum \nolimits _{p\in {\mathcal {P}}_k} h^k_p \sum _{a\in p} c_a = \sum \nolimits _{p\in {\mathcal {P}}_k} y_k h^k_p \sum \nolimits _{a\in p} c_a$. The linearization of the bilinear term $y_k h^k_p$ is obtained by introducing a variable $y_k^p$ set to $y_k h^k_p$ and a big-M constant $M_k$ to force the equality $y^k_p = y_k h^k_p$:

$$\begin{aligned}&0 \ \le \ y_k^p \le M_k h^k_p&\forall p \in {\mathcal {P}}_k \end{aligned}$$

(8)

$$\begin{aligned}&y_k - \sum _{p\in {\mathcal {P}}_k} y_k^p = 0.&\end{aligned}$$

(9)

The parameter $M_k$ can be set to $n_k(\underline{u}_k)$. In [8], it has been shown that this linearization outperforms the one where (9) is substituted to $- M_k(1 - h^k_p)\ \le \ y_k - y_k^p \le M_k(1 - h^k_p)$.

Let us now consider the piecewise linear approximation of the pseudo-concave term $n_k(u_k)u_k$, which is assumed concave over the interval $[ \underline{u}_k, u_k^{I_k}]$, and convex over $[u_k^{I_k}, \overline{u}_k]$. Note that we can limit our attention to this case, since it subsumes the case when the function is convex.

Let $w_k$ denote an over-estimate of the generalized cost. For its concave portion, the over-estimate is obtained using the tangential or first-order approximation (see Fig. 3):

$$\begin{aligned}&w_k \le a_k^i + b_k^i u_k + M^i_k s_k&\forall \ i = 1,\ldots ,I_k \end{aligned}$$

(10)

$$\begin{aligned}&u_k \le {u_k^{I_k}} (1- s_k) + \overline{u}_k s_k&\nonumber \\&s_k \in \{ 0,1 \}&\end{aligned}$$

(11)

where $\displaystyle M^i_k = \max _{\xi _k \le u_k \le \overline{u}_k}\{ n_k(u_k)u_k\} + | \min \{0, a^i_k + b^i_k \overline{u}_k \} |$, $a_k^i$, $b_k^i$ are the coefficients of the tangent to $n_k(u_k)u_k$, and $s_k$ a binary variable equal to 0 if $u_k$ lies in the concave part of $n_k(u_k)u_k$ and 1 otherwise.

Fig. 3

Over-approximation of $n_k(u_k)u_k$

At optimality, the pair $(u_k, w_k)$ lies on a face of the polyhedron determined by the tangents to $n_k(u_k)u_k$.

The over-approximation of the convex part of $n_k(u_k)u_k$ is obtained by appending to P1 a set of piecewise linear constraints. The interval $[u^{I_k}_k, \overline{u}_k]$ is split into $J_k$ sub-intervals $[u^j_k, u^{j+1}_k]$ for $j=1,\ldots , J_k-1$. With each sub-interval $[u^j_k, u^{j+1}_k]$ is associated a binary variable $z^j_k$ that indicates whether $u_k$ belongs to it ($z^j_k = 1$) or not ($z^j_k = 0$). The linear constraint that defines the over-approximation of $n_k(u_k)u_k$ over the sub-interval $[u^j_k, u^{j+1}_k]$ corresponds to the segment joining the two points $\left( u_k^j, n_k(u_k^j)u_k^j\right)$ and $\left( u_k^{j+1}, n_k(u_k^{j+1}) u_k^{j+1} \right)$. Mathematically, these constraints are expressed in the following way:

$$\begin{aligned}&w_k \le a_k^j + b_k^j u_k + M^j_k (1 - z_k^j) + N_k (1 - s_k)&\forall \ j = 1,\ldots ,J_k-1 \end{aligned}$$

(12)

$$\begin{aligned}&u_k \ge u_k^{j} z_k^j&\forall \ j = 1,\ldots ,J_k-1 \end{aligned}$$

(13)

$$\begin{aligned}&u_k \le u_k^{j+1} z_k^j + \overline{u}_k (1 - z_k^j)&\forall \ j = 1,\ldots ,J_k-1 \end{aligned}$$

(14)

$$\begin{aligned}&z_k^j \ \in \ \{ 0, 1\}&\forall \ j = 1,\ldots ,J_k-1 \end{aligned}$$

(15)

$$\begin{aligned}&\sum _{j=1}^{J_k -1} z_k^j = s_k \end{aligned}$$

(16)

where

$$\begin{aligned} M^j_k&= \max _{\xi _k \le u_k \le \overline{u}_k}\{ n_k(u_k)u_k\} + | \min \{0, a^i_k + b^i_k \overline{u}_k \} | \\ N_k&= \max _{\underline{u}_k \le u_k \le \xi _k}\{ n_k(u_k)u_k\} - \max _{\xi _k \le u_k \le \overline{u}_k}\{ n_k(u_k)u_k\} \end{aligned}$$

and $a_k^j$, $b_k^j$ are parameters associated with the straight line going through $\big (u_k^j, n_k (u_k^j)$ $u_k^j\big )$ and $\left( u_k^{j+1}, n_k(u_k^{j+1}) u_k^{j+1} \right)$. At optimality, $(u_k, w_k)$ lies on a face of the polyhedron bordered by piecewise linear functions defined over each sub-interval as depicted in Fig. 3.

The approximation of $n_k(u_k)$ and $n_k(u_k)u_k$ yields the mathematical program

$$\begin{aligned}&\widetilde{\mathrm{P1}}: \quad \max _{t,h,T,u,w, y, z, s} \sum _{k \in {\mathcal {K}}} \left( w_k - \sum _{p\in {\mathcal {P}}_k} y_k^p \sum _{a\in p} c_a \right) \\&\;\; \text {s.t. } (1)-(5) \text { and } (7)-(16). \end{aligned}$$

which provides an upper bound on the leader’s revenue, as well as a lower bound obtained by solving the original lower level problem with respect to its toll solution.

3.2 Refining the functional approximations

When a refinement of the objective function is required, for instance if the gap between its actual value and the approximation is too wide at the current iterate $({\tilde{t}},{\tilde{h}},{\tilde{T}},{\tilde{u}},{\tilde{w}},{\tilde{y}},{\tilde{z}},{\tilde{s}})$, we proceed as follows.

For the under-estimate, if the difference between ${{\tilde{y}}}_k$ and $n_k({{\tilde{u}}}_k)$ is large, we improve the approximation by appending the following tangential cut (see Fig. 4) to $\widetilde{\mathrm{P1}}$:

$$\begin{aligned} y_k \ge a_k + b_k u_k \end{aligned}$$

(17)

Fig. 4

Refining the under-approximation of $n_k(u_k)$

Next, consider the over-approximation of $n_k(u_k)u_k$. If ${\widetilde{u}}_k$ lies in the concave part of $n_k(u_k)u_k$, the refinement is obtained by appending to $\widetilde{\mathrm{P1}}$ the tangential cut (see Fig. 5):

$$\begin{aligned} w_k \le a_k + b_k u_k + M_k s_k \end{aligned}$$

(18)

where $s_k$ is the binary variable that takes value 1 whenever $\tilde{u}_k$ lies in the concave part, and 0 otherwise.

Fig. 5

Refining the over-approximation of $n_k(u_k)u_k$ over the concave part

If $\tilde{u}_k$ belongs to the convex part of $n_k(u_k)u_k$, with ${\widetilde{u}}_k\in [u_k^j, u_k^{j+1}]$, we divide the interval $[u_k^j, u_k^{j+1}]$ into two sub-intervals $[u_k^j, {\widetilde{u}}_k]$ and $[{\widetilde{u}}_k, u_k^{j+1}]$ and replace the cut associated with $[u_k^j, u_k^{j+1}]$ by the piecewise linear cuts illustrated in Fig. 6.

Fig. 6

Refining the over-approximation of $n_k(u_k)u_k$ over the convex part

For the sake of consistency, the following constraints are also introduced in $\widetilde{\mathrm{P1}}$:

$$\begin{aligned}&w_k \le a_k^1 + b_k^1 u_k + M^1_k (1 - z_k^1) + N_k (1- s_k) \end{aligned}$$

(19)

$$\begin{aligned}&u_k \ge u_k^{j} z_k^1 \end{aligned}$$

(20)

$$\begin{aligned}&u_k \le \tilde{u}_k z_k^1 + M^1_k (1 - z_k^1) \end{aligned}$$

(21)

$$\begin{aligned}&w_k \le a_k^2 + b_k^2 u_k + M^2_k (1 - z_k^2) + N_k (1- s_k) \end{aligned}$$

(22)

$$\begin{aligned}&u_k \ge \tilde{u}_k z_k^2 \end{aligned}$$

(23)

$$\begin{aligned}&u_k \le u_k^{j+1} z_k^2 + M^2_k (1 - z_k^2) \end{aligned}$$

(24)

$$\begin{aligned}&z_k^1,z_k^2 \ \in \ \{ 0, 1\}. \end{aligned}$$

(25)

3.3 Lower bound and inverse optimization

Let $({\tilde{t}},{\tilde{h}},{\tilde{T}},{\tilde{u}},{\tilde{w}},{\tilde{y}},{\tilde{z}},{\tilde{s}})$ be a current solution to $\widetilde{\mathrm{P1}}$. Based on ${\widetilde{t}}$, we can solve the lower level problem and derive a lower bound on the leader’s revenue. However, ${\widetilde{t}}$ does not necessarily yield the maximum revenue with respect to the flow vector ${\widetilde{h}}$. Assuming that ${\widetilde{h}}$ is known a priori, one can determine the compatible tolls that should be imposed in order to maximize the leader’s revenue. This corresponds to solving an inverse optimization problem.

More precisely, let $\tilde{p}_k$ be the path used by commodity k, i.e., ${\widetilde{h}}^k_{{\widetilde{p}}_k} = 1$ and ${\widetilde{h}}^k_{p} = 0$ for all $p\in {\mathcal {P}}_k \backslash \{\tilde{p}_k\}$. We write

$$\begin{aligned} u_k&= T^k + \sum _{a\in \tilde{p}_k} c_a \\ n_k(u_k)&= n_k\left( T^k + \sum _{a\in \tilde{p}_k} c_a\right) T^k \end{aligned}$$

and consider the problem, for fixed vector flow ${\widetilde{h}}$, defined as

$$\begin{aligned}&\hbox {IOP}({\widetilde{h}}):\quad \max _{t,T,u} \sum _{k \in {\mathcal {K}}} n_k\left( \sum _{a\in \tilde{p}_k} c_a + T^k \right) T^k \nonumber \\&\quad {\text {s.t.}} \quad T^k \ = \ \sum _{a \in {\widetilde{p}}_k \cap {\mathcal {A}}_1} t_a&&\forall k \in {\mathcal {K}} \end{aligned}$$

(26)

$$\begin{aligned}&\quad u_k \ \le \ \sum _{a\in q} c_a + \sum _{a \in q\cap {\mathcal {A}}_1} t_a&\forall q\in {\mathcal {P}}_k : {{\tilde{h}}^k_q=0}&\ \forall k \in {\mathcal {K}} \end{aligned}$$

(27)

$$\begin{aligned}&\quad u_k \ = \ T^k + \sum _{a\in {\widetilde{p}}_k} c_a&&\forall k \in {\mathcal {K}} . \end{aligned}$$

(28)

In the above objective, each term

$$\begin{aligned} n_k\left( \sum _{a\in \tilde{p}_k} c_a + T^k\right) T^k \end{aligned}$$

inside the summation can be expressed as

$$\begin{aligned} n_k\left( \sum _{a\in \tilde{p}_k} c_a + T^k \right) \left( \sum _{a\in \tilde{p}_k} c_a + T^k \right) - n_k\left( \sum _{a\in \tilde{p}_k} c_a + T^k \right) \sum _{a\in \tilde{p}_k} c_a, \end{aligned}$$

whose first term is pseudo-concave and the second is convex. By using the technique described in Sect. 3.1, an over-approximation of IOP(${\widetilde{h}}$) can be formulated as an MIP.

Once IOP(${\widetilde{h}}$) is solved, assume that the optimal value of IOP$({\widetilde{h}})$ is less than the incumbent lower bound, i.e., the optimal solution of the original problem does not match the solution associated with the vector flow ${\widetilde{h}}$. In order to forbid ${\widetilde{h}}$, the following ‘flow cut’ is appended:

$$\begin{aligned} \sum _{k\in {\mathcal {K}}} h^k_{\tilde{p}_k} \le |{\mathcal {K}}| - 1. \end{aligned}$$

(29)

3.4 Upper bound

Let $p^k_0$ (respectively $p^k_{\infty }$) denote the cheapest path from o(k) to d(k) obtained by setting tolls to 0 (respectively $+\infty$) and let $\gamma ^k_0$ (respectively $\gamma ^k_{\infty }$) denote the corresponding travel cost, i.e.,

$$\begin{aligned} \gamma ^k_0&= \sum _{a\in p^k_0} c_a \\ \gamma ^k_{\infty }&= \sum _{a\in p^k_{\infty }} c_a. \end{aligned}$$

If there is a path from o(k) to d(k) in ${{{\mathcal {G}}}}({{{\mathcal {N}}}},{{{\mathcal {A}}}}_2)$, $\gamma _{\infty }^k$ equals the cost of the cheapest path on the subnetwork. Otherwise, all paths include at least one arc with infinite toll, and must therefore bear an infinite cost.

Proposition 1

Let

$$\begin{aligned} \overline{T}^k = {\left\{ \begin{array}{ll} \min \left\{ \gamma ^k_{\infty } - \gamma ^k_0,\ \displaystyle \frac{1}{\beta _k - 1} \sum _{a\in p^k_0}c_a \right\} &{} \text { if } n_k(u_k) = \alpha _k u_k^{-\beta _k} \\ \\ \min \left\{ \gamma ^k_{\infty } - \gamma ^k_0,\ \frac{1}{\beta _k} \right\} &{} \text { if } n_k(u_k)= \alpha _k \exp {(-\beta _k u_k)}. \end{array}\right. } \end{aligned}$$

An upper bound of the leader’s revenue is given by:

$$\begin{aligned} \text {UB} \ = \ \sum _{k \in {\mathcal {K}}} n_k \left( \sum _{a\in p^k_0} c_a + \overline{T}^k \right) \overline{T}^k \end{aligned}$$

Proof

The leader’s objective function for commodity k is $n_k(u_k)T^k$. Since path $p^k_0$ has the smallest travel fixed cost for commodity k and $n_k$ is strictly decreasing, then

$$\begin{aligned} n_k(u_k)T^k \ \le \ n_k\left( \sum _{a\in p^k_0} c_a + T^k \right) T^k. \end{aligned}$$

The function $n_k(\sum _{a\in p^k_0} c_a + T^k ) T^k$ is pseudo-concave (increasing then decreasing) and reaches its optimal value at $\pi ^k$, the zero of its derivative, which is equal to $(1/(\beta _k-1)) \sum _{a\in p^k_0}c_a$ (respectively $1 / \beta _k$) when $n_k(u_k) = \alpha _k (u_k)^{-\beta _k}$ (respectively $n_k(u_k)= \alpha _k \exp {(-\beta _k u_k)}$). Since $\gamma ^k_{\infty } - \gamma ^k_0$ is an upper bound on one unit of the leader’s revenue $T^k$ raised from commodity k, it follows that the maximum value of $T^k$ is $\min \{\gamma ^k_{\infty } - \gamma ^k_0, \pi ^k\}$. $\square$

As a corollary to the previous theorem, it follows that a valid upper bound on the leader’s objective is provided by the smaller value between UB and the objective value of $\widetilde{\mathrm{P1}}$ constitutes a valid upper bound.

3.5 Bounds on $u_k$

As mentioned by Al-Khayyal [1], the difficulty of obtaining tight bounds on $u_k$, with the aim of obtaining good approximations of the functions $n_k(u_k)$ and $n_k(u_k)u_k$, is related to the number of commodities.

Let $[\underline{u}_k, \overline{u}_k]$ be the range of admissible generalized cost values $u_k$, and let $N^k_{ij}$ be an upper bound on the toll on arc (i, j) with respect to commodity k. Let $c_i$ (respectively $c_j$) denote the cheapest path from o(k) to i (respectively from j to d(k)). In the fixed demand case, the upper bound

$$\begin{aligned} \overline{N}^k_{ij}=\gamma ^k_{\infty } - (c_i^-+c_{ij}+c_j^+) \end{aligned}$$

holds under the assumption that there exists a toll-free path from o(k) to d(k). If no such path exists, $\overline{N}^k_{ij}=\infty$ (see Dewez et al. [5]). However, when demand is elastic, an alternative bound can be derived, which holds even in the absence of toll-free paths.

Lemma 1

For $t=0$, let $c_{ki}^-$ and $c_{jk}^+$ be the cost of the cheapest path, respectively, from o(k) to i and from j to d(k), and define

$$\begin{aligned} \Omega ^k_{ij} = {\left\{ \begin{array}{ll} \frac{{c_{ki}^-} + c_{a} + {c_{jk}^+}}{\beta _k - 1} &{} \ \text {if} \ n_k(u_k) = \alpha _k u_k^{-\beta _k} \\ \\ \frac{1}{\beta _k} &{} \ \text {if}\ n_k(u_k)= \alpha _k \exp {(-\beta _k u_k)}. \end{array}\right. } \end{aligned}$$

If toll arc $a=(i,j)$ belongs to the path used by commodity k, then an upper bound on the corresponding toll is given by:

$$\begin{aligned} N^k_{ij} = \min \{\overline{N}^k_{ij}, \Omega ^k_{ij} \} \end{aligned}$$

Proof

If the path used by commodity k goes through arc $a=(i,j)$, then $u_k\ {=}\ {c_{ki}^-} + c_{a} + {c_{jk}^+} + T^k$. This implies that the leader’s revenue raised by commodity k satisfies $n_k(u_k)T^k \ = \ n_k\left( {c_{ki}^-} + c_{a} + {c_{jk}^+} + T^k \right) T^k$. Since the function on the right-hand side is pseudo-concave and reaches its maximum at $T^k = \Omega ^k_{ij}$, the result follows. $\square$

Proposition 2

Let ${\mathcal {A}}^k_1$ be the set of toll arcs that can be used by commodity k, and ${\mathcal {K}}^a$ the set of commodities that can use toll arc $a=(i,j)$. The following lower and upper bounds on the total cost of any path used by commodity k hold:

$$\begin{aligned} \underline{u}_k&= \ \sum _{a\in p^k_0} c_a \\ \overline{u}_k&= \ \min \left\{ {\gamma ^k_{\infty } - \gamma ^k_0+ \sum _{a\in p^k_0} c_a} , \max _{a\in {\mathcal {A}}^k_1} \left\{ {c_{ki}^-} + c_{a} + {c_{jk}^+} + \max _{k'\in {\mathcal {K}}^a } N^{k'}_{ij} \right\} \right\} . \end{aligned}$$

Proof

Since path $p^k_0$ has the smallest fixed travel cost among the paths of commodity k, we have that $\displaystyle u_k \ge \sum \nolimits _{a\in p^k_0} c_a$. Now, it follows from Lemma 1 that a toll arc $a=(i,j)$ will not carry any flow whenever its toll exceeds $\displaystyle \max _{k'\in {\mathcal {K}}^a } N^{k'}_{ij}$, which implies that $\displaystyle u_k \le \max _{a\in {\mathcal {A}}^k_1} \{ {c_{ki}^-} + c_{a} + {c_{jk}^+} + \max _{k'\in {\mathcal {K}}^a } N^{k'}_{ij} \}$. Since $\gamma ^k_{\infty } - \gamma ^k_0$ is an upper bound on one unit of the leader’s revenue, $T^k$, raised from commodity k, we have that $\displaystyle u_k \le \gamma ^k_{\infty } - \gamma ^k_0+ \sum \nolimits _{a\in p^k_0} c_a$. Combining both upper bounds yields the desired result. $\square$

3.6 The exact method and a variant thereof

The exact algorithm can be divided into two parts. The first consists in over-approximating the objective function after having computed bounds on variables $u_k$ and $T^k$. The second step iteratively solves the approximated problem and refines the over-approximation.

We now consider a variant of the exact method involving a more tractable objective. To this aim, we introduce the slack variable $\tau ^k$:

$$\begin{aligned} \tau ^k = u_k-\sum _{a\in p^k_0} c_a. \end{aligned}$$

(30)

By substituting $u_k$ for (30) in the objective function, we obtain

$$\begin{aligned}&n_k\left( u_k\right) u_k - n_k\left( u_k\right) \sum _{p \in {\mathcal {P}}_k} \sum _{a \in p} c_a h^k_p \nonumber \\&\quad = n_k\left( u_k\right) \left( \tau ^k + \sum _{a\in p^k_0} c_a \right) - n_k\left( u_k\right) \sum _{p \in {\mathcal {P}}_k} h^k_p \sum _{a \in p} c_a \nonumber \\&\quad = n_k\left( u_k\right) \tau ^k - n_k\left( u_k\right) \left( \sum _{p \in P_k} h^k_p \sum _{a \in p} c_a - \sum _{a\in p^k_0} c_a \right) \nonumber \\&\quad = n_k \left( \tau ^k + \sum _{a\in p^k_0} c_a \right) \tau ^k + n_k\left( u_k\right) \left( \sum _{p \in {\mathcal {P}}_k} h^k_p \sum _{a \in p} c_a - \sum _{p \in {\mathcal {P}}_k} h^k_p \sum _{a \in p^k_0} c_a \right) \nonumber \\&\quad = n_k \left( \tau ^k + \sum _{a\in p^k_0} c_a \right) \tau ^k - n_k\left( u_k\right) \sum _{p \in {\mathcal {P}}_k} h^k_p \left( \sum _{a \in p} c_a - \sum _{a\in p^k_0} c_a \right) . \end{aligned}$$

(31)

This yields the mathematical program obtained by replacing the objective of $\overline{\mathrm{P}}$ by (31) and appending constraints (30).

$$\begin{aligned}&\hbox {P2:}\quad \max _{t,h,T,u} \sum _{k \in {\mathcal {K}}} n_k \left( \tau ^k + \sum _{a\in p^k_0} c_a \right) \tau ^k - n_k\left( u_k\right) \sum _{p \in {\mathcal {P}}_k} h^k_p \left( \sum _{a \in p} c_a - \sum _{a\in p^k_0} c_a \right) \\&\quad \text {s.t. } \quad u_k = \tau ^k + \sum _{a\in p^k_0} c_a&\forall k \in {\mathcal {K}}\\&\quad \left( 1\right) -\left( 2\right) \hbox { and } \left( 4\right) -\left( 5\right) .&\end{aligned}$$

To solve P2, we adopt the strategy used for solving P1, and over-approximate $\displaystyle n_k( \tau ^k + \sum \nolimits _{a\in p^k_0} c_a ) \tau ^k$ in place of $n_k(u_k)u_k$. Note that the bounds on variables $T^k$ are valid for the variable $\tau ^k$.

We observe that P2 is likely to outperform P1 in terms of speed. Indeed, the convex part of the function $n_k(u_k)u_k$ is always larger than the one of $\displaystyle n_k ( \tau ^k + \sum \nolimits _{a\in p^k_0} c_a ) \tau ^k$, thus the over-approximation of $n_k(u_k)u_k$ involves a larger number of binary variables than the over-approximation of $\displaystyle n_k ( \tau ^k + \sum \nolimits _{a\in p^k_0} c_a ) \tau ^k$. This leads to a lesser quality of the upper bound of P1 compared to P2.

4 Two heuristic algorithms

In this section, we present two heuristics based on the trust region paradigm, following the framework proposed by Colson et al. [3] to solve general non-linear bilevel programs. At each iteration, the trust region ‘model’ corresponds to a bilevel program where all functions are linearized, with the exception of the lower-level objective, which is replaced by a second-order approximation. Upon replacing the quadratic lower-level program by its optimality conditions, the resulting quadratic MIP can be solved using a commercial software.

Two strategies have been considered. In the first, linearization of the demand function yields the network pricing problem studied in [8]. In the second, one replaces the lower-level by its optimality conditions in order to derive a single-level program P1 whose major difficulty rests in the nonlinearity of the objective function.

4.1 The first heuristic model

Let $({\widetilde{t}}, {\widetilde{h}}, {\widetilde{T}}, {\widetilde{u}})$ denote the incumbent solution of P. By linearizing the demand function $n_k(u_k)$ at ${\widetilde{u}}_k$ for each commodity, we have that $n_k(u_k)\approx a_k - b_k u_k$, where $a_k$ and $b_k$ are the coefficients of the tangent line to $n_k(u_k)$ at ${\widetilde{u}}_k$. For each commodity k, we substitute $n_k(u_k)$ for $a_k-b_ku_k$ in P and append the constraint ${\widetilde{t}} - \Delta t \le t \le {\widetilde{t}} + \Delta t$, where $\Delta t$ is the radius of the trust region:

$$\begin{aligned}&\mathrm{TR1:} \quad \max _{t\ge 0,\ h, u} \ \sum _{k \in {\mathcal {K}}} \sum _{p \in {\mathcal {P}}_k } (a_k - b_k u_k)\sum _{a \in p} t_a h^{k}_{p} \\&\quad \text {s.t.} \qquad {u_k \ = \ \displaystyle \sum _{p \in {\mathcal {P}}_k} \left( \sum _{a \in p}c_a + \sum _{a \in p\bigcap {\mathcal {A}}_1} t_a \right) h^{k}_{p}}\\&\quad \qquad \forall k\in {\mathcal {K}}{\left\{ \begin{array}{ll} h^{k} \in \displaystyle \arg \min _{h^{'k}} \sum _{p \in {\mathcal {P}}_k } \left( \sum _{a\in p} c_a + \sum _{a \in p\cap {\mathcal {A}}_1} t_a \right) h^{'k}_{p} &{} \\ \quad \text {s.t. } \quad \displaystyle \sum _{p \in {\mathcal {P}}_k} h^{'k}_{p} \ = 1 &{} \\ \qquad {h'}_p^k\in \{0,1\}. \end{array}\right. } \\&\quad \qquad {\widetilde{t}}_a - \Delta t_a \le t_a \le {\widetilde{t}}_a + \Delta t_a \quad \forall a \in {\mathcal {A}}_1. \end{aligned}$$

This problem, which corresponds to the linear demand case, is efficiently addressed by the algorithm proposed in [8].

4.2 The second heuristic model

Let $({\widetilde{t}}, {\widetilde{h}}, {\widetilde{T}}, \tilde{u})$ be the incumbent solution of $\overline{\mathrm{P}}$ and let $n_k$ be the variable associated with the function $n_k(u_k)$. The linearization of the revenue function of commodity k at $({\widetilde{T}}, {\widetilde{u}})$ is:

$$\begin{aligned} n_k(u_k)T^k\approx & {} n_k({\widetilde{u}}_k){\widetilde{T}}^k + n_k({\widetilde{u}}_k)(T^k - {\widetilde{T}}^k)+{\widetilde{T}}^k(n_k-n_k({\widetilde{u}}_k))\\= & {} n_k(\tilde{u}_k)T^k + {\widetilde{T}}^k n_k - n_k({\widetilde{u}}_k){\widetilde{T}}^k. \end{aligned}$$

For each commodity k, we substitute $n_k(u_k)T^k$ for $n_k({\widetilde{u}}_k)T^k + {\widetilde{T}}^k n_k - n_k({\widetilde{u}}_k){\widetilde{T}}^k$ in $\overline{P}$ and append the constraint ${\widetilde{t}} - \Delta t \le t \le {\widetilde{t}} + \Delta t$. Since the variable $n_k$ does not appear in $\overline{P}$, we impose the constraint $n_k \le a_k - b_k u_k$ where $a_k$, $b_k$ are the coefficients of tangents to $n_k(u_k)$ at the point ${\widetilde{u}}_k$. This latter constraint prevents $n_k$ from assuming an infinite value and enforces its proximity to the actual demand. This leads to the MIP

$$\begin{aligned}&\hbox {TR2:} \quad \max _{t,h,T,u} \sum _{k \in {\mathcal {K}}} ( n_k({\widetilde{u}}_k) T^k + {\widetilde{T}}^k n_k - n_k({\widetilde{u}}_k) {\widetilde{T}}_k ) \\&\quad \text {s.t. } \quad (1)-(2) \text { and } (4)-(5)&\\&\quad {\widetilde{t}}_a - \Delta t_a \le t_a \le {\widetilde{t}}_a + \Delta t_a&\forall a \in {\mathcal {A}}_1 \\&\quad n_k \le a_k - b_k u_k&\forall k \in {\mathcal {K}}. \end{aligned}$$

The single-level reformulation of TR1 involves $\sum _{k\in {\mathcal {K}}} |{\mathcal {P}}_k| - |{\mathcal {K}}|$ continuous variables and $\sum _{k\in {\mathcal {K}}} |{\mathcal {P}}_k|$ more constraints than TR2.

5 Numerical results

Numerical tests have been performed on randomly generated grid networks, a topology that has been shown to be challenging for network pricing problems. Grid Networks were designed as indicated in [8]. It has been observed in practice that exact solutions to TR1 and TR2 are not necessary to obtain good toll solutions.

The main parameters of the test problems are $|{\mathcal {N}}|$ (number of nodes), $|{\mathcal {A}}|$ (number of arcs), $\%t$ (the percentage of toll arcs), and $|{\mathcal {K}}|$ (number of commodities). We consider demand functions as described in Sect. 2, i.e, they either have a constant elasticity or decay exponentially. The parameters of the demand functions were chosen to make most commodities attractive. When the demand functions have a constant elasticity, we set

$$\begin{aligned} \alpha _k=\left\lceil \frac{\xi _k (1.5 {{\overline{C}}}_k)^{1.5}}{10^5}\right\rceil , \end{aligned}$$

where ${\overline{C}}_k$ is the average fixed cost of paths associated with OD pair k, and $\xi _k$ a random number drawn from the uniform distribution over the interval

$$\begin{aligned} \left[ \exp \left( 8\left\{ \frac{1}{2}+\frac{3}{2}\frac{\gamma _k^\infty }{{\overline{C}}_k}\right\} \right) \right] , \left[ \exp \left( 8.5\left\{ \frac{1}{2}+\frac{3}{2}\frac{\gamma _k^\infty }{{\overline{C}}_k}\right\} \right) \right] . \end{aligned}$$

For demand functions with exponential decay,

$$\begin{aligned} \alpha _k=\left\lceil \frac{\xi _k\exp (1.5{{\overline{C}}}_k)}{10^5}\right\rceil , \end{aligned}$$

with the aim of generating significant demand for all commodities.

Algorithms were coded in C++ and solved by the commercial MIP solver Cplex [7] under its default settings. The procedure ‘IloPiecewiseLinear’ of the ‘ILOG CPLEX Callable Library’ allowed the introduction of the piecewise linear cuts. The algorithms were run on an Intel Core 2 Duo (2.13GHz) processor PC, under the GNU/Linux openSUSE operating system.

The major issue concerning the exact algorithm is the solution $\widetilde{\mathrm{P1}}$, which takes $99\%$ of the CPU time. In order to take advantage of the information provided by the Branch-and Bound (BB) procedure, inverse optimization was implemented with respect to the flow vectors, at every 1000th iteration. Whenever the inverse optimization yielded an objective value inferior to the incumbent lower bound, a flow cut (29) was appended to the model. Otherwise, the incumbent lower bound was updated. At each iteration of the exact algorithm, an initial solution to $\widetilde{\mathrm{P1}}$ provides a lower bound, used to prune nodes in the BB tree. At each iteration, initial flows are assigned to the cheapest paths according to the travel costs obtained at the previous iteration.

Figures 7 and 8 illustrate the respective performance of formulations P1 and P2, when demand elasticity is constant. The time limit is set to 1000 s, the stopping criterion to $\epsilon =.001$, and the number of discretization points to 20.

Fig. 7

Comparison between P1 and P2 on instances of 5 commodities. Constant elasticity set to 2. Average taken over 10 random instances. ‘Best gap P1’ is the absolute difference between the best solution achieved by P1 and the upper bound provided by P2

Fig. 8

Comparison between P1 and P2 on instances of 5 commodities. Constant elasticity set to 6. Average taken over 10 random instances

We observe that the best solution found by both methods are almost identical, but that the upper bound associated with P1 decreases very slowly compared to the upper bound provided by P2. Indeed, the over-approximation of $n_k(u_k)u_k$ in the objective of P1 requires several additional cuts (extra binary variables) before reaching an acceptable solution, in contrast with $\displaystyle n_k (\sum \nolimits _{p\in p^k_0} c_a + \tau ^k )\tau ^k$ in the objective of $\widetilde{\mathrm{P2}}$. Moreover, whenever elasticity increases, the difficulty of solving P1 (respectively P2) increases (respectively decreases). This is mainly due to the convex part of $n_k(u_k)u_k$ becoming wider and the curvature of $n_k(u_k)u_k$ higher as the elasticity increases, while the convex part of $\displaystyle n_k (\sum \nolimits _{p\in p^k_0} c_a + \tau ^k )\tau ^k$ shrinks. Since these observations hold for all demand functions, we will only consider formulation P2 from now on.

From a computational point of view, a trade-off must be achieved between computational tractability and accuracy. We observe that it is worth increasing the number of discretization points, since the combinatorics of the problem comes more from the number of paths involved in the model than the number of linear pieces in the approximations of the functions. Of course, beyond a certain threshold, additional pieces are simply useless. Following experiments with 5, 10, 20 or 30 discretization points, it was observed that the number 20 represented a suitable compromise. For instance, see Fig. 9 for a comparison between 5 versus 20 discretization points.

Fig. 9

Comparison between 5 and 20 discretization points. Average taken over 10 generated problems for 10 commodities. Constant elasticity set to 2

Figure 10 highlights the performance of the exact method when flow cuts are appended to the original formulation. These allow to avoid paths with estimated high revenue, but actual revenue less than the incumbent lower bound. This resulted in an upper bound that decreases very fast, as well as a lower bound that increases in a stepwise manner (this behaviour can be observed on Fig. 11). We notice the good performance of the exact method when flow cuts are introduced during the process.

Fig. 10

Impact of flow cuts in formulation P2. Averages taken over 10 instances of 30 commodities

Fig. 11

Evolution of lower and upper bounds on instances of 40 commodities with 50% tolls arcs

Table 1 TR2: elasticity set to 2

Table 2 TR2: elasticity set to 6

Table 3 Parameters for the exact method and column headers for tables

Fig. 12

Cpu times with respect to elasticity (left) and percentage of toll arcs (right). Average taken over 10 generated problems for 5–10 commodities

Fig. 13

Gap between upper bound provided by exact method and solution found when selected paths are the shortest ones with respect to the fixed travel cost. Average taken over 10 generated problems for 10, 20, 30 and 40 commodities

To assess the potential of the exact method on P2, we applied it to instances ranging from 10 to 40 commodities. The results of our computational experiments are presented in Tables 1 and 2 , each table summarizing an average taken over 10 randomly generated problems. The values of parameters and column headers for the tables are displayed in Table 3.

Formulation P2 allows to solve small to medium scale problems (up to 10,000 paths) at quasi optimality in < 1,h of CPU time. On the larger instances, the running time increases very fast due to the number of binary variables that grows exponentially with network size. It is interesting to note (see Fig. 12) that running time decreases as elasticity increases. Intuitively, large elasticities imply a fast decrease of demand, which makes the path with smallest fixed travel cost all the more attractive for the leader. This reasoning is supported by the results displayed in Fig. 13, where the gap between the upper bound provided by $\widetilde{\mathrm{P2}}$ and an inverse optimization performed on flows assigned to cheapest paths (with respect to fixed costs) decreases as elasticities increase. On the other hand, no clear conclusion can be drawn concerning the sensitivity with respect to the percentage of toll arcs. Notwithstanding, the solution obtained by selecting the paths with smallest fixed travel cost provides a good lower bound, although exact methods fail to provide a small gap, due to the bad quality of the upper bound. Note that, as a general rule, it is easier to solve instances where all arcs can be tolled.

We finally assessed the efficiency of the two heuristics, setting the parameters to those recommended in [3], with the exception of the number of iterations $k_{\text {max}}$ and the maximum number of unsuccessful iterations mxnuns. These values are reported in Table 4 where nbpoint (respectively ptuns) denotes the number of starting points (respectively the number of consecutive points where the best solution is not improved).

While the models arising in the trust region algorithm are simpler than the original bilevel program, they are yet strongly NP-hard. For this reason, we decided to set the time limit to 1000 s and to allow more time for diversification. Alternatively, one can avoid generating already encountered flows through the introduction of the flow cut (29). In both cases, inverse optimization can be used to optimize revenues with respect to current feasible flow patterns. Table 5 illustrates the efficiency of the heuristic algorithms when elasticity is set to 2, comparing with P2 for various problem sizes.

We observe that the quality of solutions provided by the exact and heuristic method are similar when the number of commodities is small. This can also be observed on Figs. 14, 15 and 16. Heuristic algorithms always find quickly the best solution compared to the exact method (see column cpu*). Table 6 summarizes the ratio of running time over the three methods when they find the best solution.

Table 4 Parameters for the heuristic algorithms

Table 5 Comparison between exact method and heuristics; $\beta _k = 2$, 20, 30, 40 and 50 commodities

Whenever the number of commodities exceeds 30, the ratio P1/TR2 increases and reaches 2.27, while no firm conclusion can be drawn concerning the ratio P2/TR1. As can be observed in column $\#$fcuts, the number of flow cuts is highest with TR2, followed by TR1 and the exact method, which might explain why TR2 finds good solutions quickly. Due to the difficulty of solving sub-problems involving a large number of commodities, $\#$fcuts decreases as the number of commodities increases. Figure 17 shows that $\#$fcuts is concave (increasing then decreasing) with respect to the percentage of toll arcs, and reaches its maximum (respectively minimum) value between 40 and 50% (respectively when all arcs are tolled). In summary, the heuristics provide a good compromise between computational time and solution quality whenever the number of commodities exceeds 30 and elasticities are small. When elasticities are high, the exact method is to be preferred.

6 Conclusion

In this paper, we have considered efficient formulations and algorithms for addressing a network pricing problem involving nonlinear demand functions. We proposed for its solution an asymptotically exact method, as well as powerful heuristic procedures based on a bilevel approximation of the original problem, cast within the framework of trust region methods. The numerical tests illustrate the good behavior of our methods and the robustness of the associated code. From a qualitative point of view, it was observed that the instances involving high elasticities were easier to solve, due to a decrease in the combinatorial complexity of the problem.

Fig. 14

Comparison between exact method and heuristics. Average taken over 10 generated problems for 40 commodities. Elasticity set to 2

Fig. 15

Comparison between exact method and heuristics. Average taken over 10 generated problems for 50 commodities. Elasticity set to 2

Fig. 16

TR2: Comparison between exact method and heuristics. Average taken over 10 generated problems for 60 commodities. Elasticity set to 2

Table 6 Running time ratio between exact method and heuristic algorithms; $\beta _k = 2$

Fig. 17

Number of flow cuts (29) added during execution of heuristics with respect to the percentage of toll arcs. Average taken over 10 generated problems for 10, 20, 30, 40 and 50 commodities

Although the introduction of variable and nonlinear demand is an important step forward, yet it does not account for situations where commodity flows are not assigned to the same path. For instance, dispersion of traffic along the paths of the network could result from congestion, or from the presence of rigid link capacities. In both cases, the structure of the lower-level problem is significantly modified, and the resulting model calls for a different algorithmic approach. Another key assumption of our model is that the value-of-time parameter is uniform throughout the user population, i.e., given the choice between two paths of equal costs, users always select the one with highest toll. This drawback could be eliminated by introducing a range of value-of-time parameters across users. If this range is continuous, the lower level problem becomes an infinite-dimensional linear problem. As indicated by Marcotte and Zhu [11], an efficient solution to this lower level problem can be obtained by solving a parametric cheapest path problem. These extensions of the model are left to future studies.