Introduction

One of the challenges for transportation decision makers is to optimally allocate resources for capacity expansion projects in a constrained budget scenario to achieve a certain performance measure (e.g. congestion reduction), simultaneously considering route choice behavior of network users. Such type of decision making can be solved using bi-level optimization with two sets of players: decision maker, and road users. Both players have inherently different objectives. The road users to their advantage select routes such that individual travel costs are minimized while the decision maker seek to optimally select capacity expansion of network segments. It is well known in the literature that selecting capacity expansions based on only flow pattern without considering responses of user’s behavior may lead to situations of increased congestion [1]. Thus, the decision maker has to model the users’ collective response for capacity expansion of the existing network. Such type of modeling framework is extensively analyzed in the literature [2–10]. There is consensus among researchers that such bi-level optimization problems are non-linear in nature, and difficult to solve. The difficulty of exactly solving this problem is due to the fact that a user equilibrium or Nash equilibrium flow pattern has to be calculated at each step of the optimization search process. This is computationally demanding, and the algorithms proposed to date are applicable only to problems of modest size. Proposed solution algorithms are solved by exact and heuristic methods. Because of the complex nature of capacity expansion a variety of problem formulations are proposed in the literature.

The purpose of this paper is three-fold. First, to develop solution algorithm considering bi-level optimization model for capacity expansion in a network design problem context. Second, to assess the solution algorithm performance in comparison with existing literature. Third, to test the efficacy of the proposed algorithm in real world moderate to large scale transportation networks for robustness and flexibility. Remainder of the paper is organized as follows: first a review of pertinent literature on related works is presented; followed by a description of the model formulation and solutions approach. Results of the model application on two example problems and a large network is discussed next. Conclusions and recommendation for future research are presented in the final section.

Literature Review

Transportation agencies face the dilemma to select a limited number of road improvement projects for allocation of resources among thousands of prospective choices given a scarce budget. Finding optimum selection of projects from a larger pool falls in the category of mixed integer knapsack problem. Recent literature focused extensively on multilevel programming, a branch of mathematical programming that can be viewed as either a generalization of minimization–maximization problems or as a particular class of Stackelberg games. The network design problem with continuous decision variables, representing link capacities, can be cast into such a framework. Marcotte [11] gives a formal description of the problem and then develops various suboptimal procedures to solve it. Gradient based methods were used to solve a continuous network design problem in a transportation network where Wardrop’s first principle was used for traffic assignment [12]. Bi-level optimization is a useful approach for problems with conflicting objectives within a hierarchical structure. It originated from the fields of game theory and decision making and describes a number of problems in transportation planning and modeling.

The bi-level problem has hierarchal framework that involves two separate optimization problems at different levels. The first problem has a feasible solution set and is called the upper-level problem which is also known as the leader problem. The solution set is determined by the second optimization problem. The second problem is the lower-level problem or the follower problem. This concept can be extended in order to define multi-level programs with any number of levels [13]. The network design problems are formulated as bilevel programming problem that are non-convex and non-differentiable in nature. Hence, obtaining global optimum solution for these problems is extremely difficult [14]. These problems are considered as NP-hard which not only consume time and memory but also are extremely difficult to solve. In the field of transportation engineering, proposing an efficient algorithm as a solution approach for this problem is still regarded as a major contribution [15]. Several solution approaches have been proposed and developed over the past few decades. Some of the initial approaches had used heuristic algorithms, which gave near optimal or local optimum solutions [16, 17]. Moreover, there are methods such as equilibrium decomposed optimization (EDO) [6], which is computationally robust but results in suboptimal solutions. Gershwin and Tan [18] formulated the continuous network design problem (CNDP) as a constrained optimization problem in which the constrained set was expressed in terms of the path flows and performed their method on small networks. Marcotte [19] and Marcotte and Marquis [20] presented heuristics for CNDP using system optimal approach and obtained relatively better numerical results. However, these heuristics have not been extensively tested on large-scale networks. Regarding the sensitivity based approach applied to bi-level optimization problem, Falk and Liu [21] investigated theoretic analysis for general non-linear bi-level optimization problem and proposed a descent approach in terms of the bundle method to solve the non-linear bi-level problem where the gradient of the objective function can be obtained when the sub gradient information of the lower level are available. Chiou [22] explored a mixed search procedure to solve an area traffic control optimization problem confined to equilibrium network flows, where good local optima can be effectively found via the gradient projection method.

However, very little information is available in the literature about the complete solution approach of the bi-level model structure in NDP and its application on real world networks. Further, only theoretical approaches have been published without any significant applicability. In a recently published paper, Mishra et al. [23] provided a methodology for a decision making process tool for large-scale transportation infrastructure investment consisting of multiple entities. More recently, Jiang and Szeto [24] proposed a bi-level optimization framework for time-dependent discrete road network design that considers health impacts where modified Sioux Falls network is adopted to show the performance of the solution algorithm as well as the effectiveness of the proposed repairing procedure but does not provide any real world application.

Methodology

Bi-level Programming Problem (BLPP) Description

The NDP can be represented as a leader–follower game where the transport planner makes network planning decisions, which can influence, but cannot control the users’ route choice behavior. The users make their route choice decisions in a user optimal manner. This game can be formulated as a bi-level programming model, where the upper-level problem determines the optimal capacity improvement to each link in a given set of candidate links, minimizing the total system travel time (TSTT), subject to a given budget limit, and the lower-level problem represents a UE traffic assignment problem that describes users’ route choice behavior. The symbols used in the model are listed below:

Notation

Explanation

\( A \):

Set of arc \( a \)

\( I \):

Set of trip origins, \( i \in I \)

\( J \):

Set of trip destinations, \( j \in j \)

\( IJ \):

Set of origin–destination pairs on the network, \( \left( {i,j} \right) \in IJ \)

\( k \):

The complete set of available paths in the network

\( k^{ij} \):

The set of paths in the network between I–J pair \( \left( {i,j} \right),\forall \left( {i,j} \right) \in IJ \)

\( f_{k}^{ij} \):

Flow on path r, connecting each origin–destination (O–D) pair (i–j)

\( q_{ij} \):

Demand between each origin–destination (O–D) pair \( \forall \left( {i,j} \right) \in IJ \)

\( t_{a} \left( {x_{a} ,y_{a} } \right) \):

Travel cost on link a as a function of flow and capacity expansion

\( x_{a} \):

Flow for link \( a \)

\( \alpha_{a} \):

Constant, varying by facility type (BPR function)

\( \beta_{a} \):

Constant, varying by facility type (BPR function)

\( \delta_{a,ij}^{r} \):

Binary variable \( \left\{ {1, {\text{if link a }} \in {\text{A is on path k }} \in {\text{k}}^{\text{ij}} :0, {\text{otherwise}}} \right\} \)

\( d_{a} \):

Represents the monetary cost of capacity increments per unit of enhancement

\( \theta \):

Denotes a user defined factor converting investments costs to travel cost

\( g_{a} \left( {y_{a} } \right) \):

Improvement cost function for link ‘a’

\( y_{a} \):

Capacity expansion for link ‘a’ (nonnegative real value)

\( TSTT \):

Total system travel time

\( B \):

Budget (nonnegative real value)

The Upper-level Optimization Problem (ULP)

The planner aims to minimize the total system travel time in the NDP. Thus the upper-level problem can be formulated as

$$ Minimize TSTT = \mathop \sum \limits_{a \in A} (x_{a} t_{a} (x_{a} ,y_{a} )). $$
(1)

Subject to:

$$ \mathop \sum \limits_{a \in A} g_{a} \left( {y_{a} } \right) \le B, $$
(2)
$$ y_{a} \ge 0:\quad \forall_{a \in A} , $$
(3)

The objective function (1) represents the total system travel time where \( x_{a} \) is determined by the lower-level UE problem which will be presented in the next section. Constraint (2) guarantees that the total improvement cost does not exceed the total given budget. Constraint (3) ensures that the capacity improvement index \( y_{a} \) for each candidate links are positive.

The Lower-level User Equilibrium Traffic Assignment Problem (LLP)

The upper level shown in Eqs. (1–3) provide a capacity expansion vector \( y_{a} \) and is added to existing capacities thus forming new link capacities. Based on these updated capacity values of the links, the link flows can be computed by solving the following problem formulation:

$$ Minimize Z = \mathop \sum \limits_{a \in A} \mathop \int \limits_{0}^{{x_{a} }} t_{a} \left( {x_{a} ,y_{a} } \right)dx. $$
(4)

Subject to:

$$ q_{ij} = \mathop \sum \limits_{{k \in k^{ij} }} f_{k}^{ij} , \; \forall \left( {i,j} \right) \in IJ, $$
(5)
$$ x_{a} = \mathop \sum \limits_{{\left( {i,j} \right) \in IJ}} \mathop \sum \limits_{{k \in K^{ij} }} \delta_{ak}^{ij} f_{k}^{ij} , \; \forall_{a} \in A, $$
(6)
$$ f_{k}^{ij} \ge 0,\quad \forall_{k} \in k^{ij} , \; \forall \left( {i,j} \right) \in IJ, $$
(7)
$$ q_{ij} \ge 0, \; \forall \left( {i,j} \right) \in IJ. $$
(8)

Equation (4) represents the objective function of UE problem. Constraint (5) defines the demand conservation condition. Constraint (6) defines the relation between link flow and path flow. Constraints (7) and (8) requires non negativity path flow and travel demand, respectively. An important feature of this problem, and more generally of bi-level programs, is the hierarchical relationship between two autonomous, and possibly conflicting, decision makers. Mathematical program in Eqs. (1–3) and (4–8) are connected through the use of common variables, namely capacity improvement index \( y_{a} \) and flows \( x_{a} \). Also, the decision of the planner cannot be computed until flows are known. These flows are not in the direct control of the planner, but their decisions are reflected by the capacity improvement vector \( y_{a} \). Here it is imperative to mention two important limitations of this approach. First, it incorporates single objective at upper level (minimization of TSTT) but decision makers may have other objectives such as minimization of system level emissions. Second, this formulation does not consider multiyear budget scenario. Incorporation of these two factors can be interesting future extension of this study.

Solution Approach

Figure 1 shows the flowchart describing the solution approach. As evident from this figure the ULP and LLP are solved in feedback loop alternatively till convergence. The ULP was solved by PSWARM optimization algorithm in MATLAB to obtain a trial capacity expansion vector (\( y_{a} \)). Then this vector is added to existing capacity vector to form new network capacities. The new network properties are transferred to the lower level. The LLP is solved using slope-based path shift-propensity algorithm (SPSA) [25]. The SPSA yields a UE link flows with small solution noise. The convergence of SPSA search algorithm is guaranteed and it leads to efficient solution with moderate computational effort. The LLP provides new link flow (\( x_{a} \)) vector based on the capacity enhancement vector (\( y_{a} \)). This link flow vector is feed backed to the upper level. The upper level objective function is maximized to obtain the new trial capacity vector (\( y \)). This new trial capacity is transferred to the lower level again and this method is repeated until convergence.

Fig. 1
figure 1

Flowchart of the solution approach

Full size image

Implementation

This section presents the numerical experiments and discusses results to benchmark the proposed method covered in the previous section. Numerical analysis has been conducted in order to compare the results obtained with other methods suggested previously in literatures [6, 15, 26]. Two example networks were chosen from literature to perform the comparisons. Results are compared with multiple algorithms from the literature e.g. MINOS [6], Hooke–Jeeves [6] and EDO [6].

Test Network 1

As a simple example (see Fig. 2a), was used as a reference to compare the results to the similar network from the literature. The network data, link attributes, and demand are adopted from literature [6].

Fig. 2
figure 2

Test network topology. a Test network-1. b Test network-2

Full size image

Table 1 shows the results of current procedure after 20 iterations. The MINOS, Hooke–Jeeves and EDO algorithms came up with nearly identical solutions. The objective values of current solution shows better results. MINOS had the closest results to the current study. The expansion for the link 3 in optimal solution should be zero. However, the EDO and Mathew approach have some values, which can indicate the small gap to the convergence.

Table 1 Test network 1 after 20 iterations
Full size table

Test Network 2

The second test network analyzed is Sioux Falls (see Fig. 2b). The network topology is adapted from the literature [6] which consists of 24 nodes, 76 links, and 576 O–D pairs. The links highlighted are considered to be eligible for capacity improvement. The purpose of selection of these links is to compare the results with past literature. Using the proposed methodology, the optimal capacity expansion for the links and the total system travel time or the system cost is calculated. These results were then compared with other algorithms in the past [5] as shown in Table 2. Table 2 displays the results of the link capacity expansion and the objective function values from the above past models as well as the current study methodology. From the table, it can be observed that the SA and GA produced relatively acceptable results. When compared across all the models, it can be concluded that the approach proposed in this study produced the best solution. It should be noted that regardless of the relative closeness of objective function values, there is inconsistency across the link capacity expansion values. This suggests that the problem has several optimal solutions. As mentioned by Szeto and Lo [7] multiple local optimums exist due to the non-convexity of CNDP and each method leads to a different solution.

Table 2 Comparison of results between test network 2 and previous literatures
Full size table

In order to compare the performance of the proposed solution approach with other models, sensitivity analysis is conducted. First, several demand levels are computed by multiplying the base demand with factors such as (0.8, 1.2, 1.4, 1.6). Then the network design is performed on these newly formed demand levels using the proposed method. Table 3 shows the total system cost and number of iterations conducted for these demand levels. Although the number of iterations by current study is much higher than the other algorithms (except IOA and GA), the solution provided by this algorithm yields the lowest objective function value.

Table 3 Comparison of results for different demand level: Sioux falls network
Full size table

In current study, the results are close to the ones from MINOS, H–J and EDO approach at bi-level iteration five. However, with more bi-level iterations, the results become more similar to numbers from the IOA study. The bi-level convergence criterion is based on the flows. After about thirty iterations for case one and twenty iterations for cases two and three, users (flow of lower level) stopped responding to improvements. It was concluded that the MINOS, H–J and EDO approaches probably stopped after about five iterations. In case one, link six had the highest need for improvements until iteration four. However, this trend changed when the flows converged and the entire budget gradually allocated to link 16. Again the results from MINOS, H–J and EDO have the budget allocated to link six. The current study and the three stated studies were similar until iteration four.

Large Scale Network

The Chicago sketch network consists of 933 nodes, 2950 links and 93,135 origin destination pairs. Various budget scenarios were analyzed to examine the robustness of the proposed solution approach. Figure 3 shows capacity expansion on scenarios ranging from budget of $300 to $600 million. The cost of link expansion is assumed to be $1 million per lane mile. In the optimization it was ensured that no link is eligible to receive capacity expansion of more than 100 %. As expected higher number of links are selected with increasing budget. Figure 4 shows system level performance measures for Chicago sketch network. The UL objective function (TSTT) as expected decreased with increased budget. However, after a certain budget the network performance has not changed showing law of diminishing return. Similarly, average speed is increased with increased spending, and congested lane miles have decreased. Average travel time per O–D pair have also decreased with increasing budget. In summary, results of the large network capacity expansion appears reasonable, and budget sensitivity analysis appears intuitive.

Fig. 3
figure 3

Suggested capacity expansion in Chicago sketch network

Full size image
Fig. 4
figure 4

Budget sensitivity and network measures

Full size image

Conclusion

Transportation agencies need a quantitative method for allocating scarce resources for capacity expansion or network improvements. In this paper a bi-level approach is used for the capacity expansion and a solution approach is proposed. The implementation of proposed approach is demonstrated using small to large scale networks. The novelty of the approach is that it uses kth best algorithm to solve bi-level network design problem where the upper level solution is provided using PSWARM optimization algorithm and the lower level solution is provided using an efficient traffic assignment algorithm SPSA. The methodology has been validated by comparing the results with methods previously suggested in literatures using three test networks. The proposed method provided a single optimal solution and after several iterations, the users in all test networks stopped responding to additional improvements defined in the upper level objective function. This means the flows, which are the convergence criteria within a bi-level optimization problem, achieved convergence. The insights from the numerical results suggest that method proposed in this study lead improved results from other studies. It was found that the bi-level method required more iterations than several of the previous studies. Sensitivity analysis is conducted by providing the networks with various demand levels and results showed that the current study provides better results compared to the other methods in literature at all demand levels. This also confirms the resilience of the solution method especially at high demand and congested network. The numerical results also indicate that proposed approach is suitable for a large network and can be used for practice. The possible extensions of the approach will be to incorporate capacity expansions with multi-objective formulation at upper level and in multi-year network design framework.