Continuous Network Design Using Partial Linearized Subgradient Methods

Abstract

Although demand management has shown to be a vital tool in managing congestion, many metropolitan planning organizations (MPOs) and departments of transportation (DOTs) still pursue network modification and capacity increase as a congestion relief and a mitigation measure. The network design problem (NDP) still has, therefore, an essential and significant role in shaping and sizing urban transportation networks. The literature has traditionally treated the NDP as a bi-level mathematical programming problem or a mathematical program with equilibrium constraints (MPEC). In the bi-level optimization setting, the problem is approached as a leader-follower problem in which the lower level is a user equilibrium (UE) assignment problem as the follower, and the upper level is the network sizing problem as the leader problem. NDP has long been known as a challenging problem, and many solution algorithms have been proposed to solve it. This study proposed an efficient solution algorithm for the continuous network design problem (CNDP). The solution algorithm has been shown empirically to solve the CNDP in a shorter time using partial linearized subgradient methods. The proposed method was applied to a small network that was traditionally used to evaluate the performance of solution algorithms versus Braess’s paradox. It was then applied to the Sioux Falls network as a well-known benchmark network to compare the results with previous studies. The proposed method has been shown to run much faster than all the previous studies reviewed in this paper with minimal degradation of accuracy (0.52% lower than the best solution).

Keywords

planning and analysis network assignment networks

Besides travel demand management (TDM) methods, supply-oriented network development is vital to mitigate traffic congestion, particularly in developing countries. Metropolitan planning organizations (MPOs) and departments of transportation (DOTs) spend large amounts of resources on transportation network improvement projects annually. Moreover, transportation challenges have become a primary concern of residents and authorities in large cities. That is why efficient decision making is essential for transportation network sizing, design, and development projects. This problem would become crucial for even developed countries, and in some studies, such as Zhao & Zhang ( 1 ), the transportation NDP has been transformed into a transportation system reconstruction problem.

Theoretically, transportation network design can be assumed to be among the most challenging and complicated transportation problems. It is a well-known complex mathematical problem. Although network design has been widely investigated in the literature, it is still not used, at least not widely, in practice. In addition to the problem’s theoretical complexity, the solutions’ run time is another critical issue. As a result, it is challenging to implement a network design problem (NDP) in large-scale realistic size networks. Therefore, it is essential to develop reasonable methods to solve the transportation NDP.

Macroeconomic decisions, traffic management, transportation infrastructure development, and decision making in large corporations are mostly multi-level decision-making problems ( 2 ). The NDP can be formulated as a bi-level mathematical/decision-making problem, in which network managers or planners are at the upper level as the leader of the decision, while users/drivers are at the lower level and make their decisions as followers in response to the decisions of the leader. This is often referred to as the leader-follower model structure. At the upper level, the decision maker tries to optimize criteria formulated as the objective function or sometimes functions (e.g., system optimization and environmental pollution optimization) using the decision variables they have in hand (roadway/link capacities). The NDP could be defined as the problem of determining network parameters (e.g., capacity enhancement) to optimize a given transportation network under budget constraints by considering the reaction of the users to those decisions. The NDP could be continuous (CNDP), where the decision on the amount of capacity on the links are continuous variables, or discrete (DNDP), where the decision maker decides to either perform or not perform a capacity enhancement in the network (value of 1 means to build and 0 will be not to build). The mix NDP is a mixture of both cases.

The network structure is usually not changed in the CNDP, and the link capacities are assumed to be the decision variables. On the other hand, in a discrete problem, one or more roads are to be constructed or modified, and the variables are typically binary ( 3 ). NDP seeks to make optimal use of network investment to optimize the objective function subject to budgetary constraints. Numerous studies emphasized that network design is a nonlinear, non-convex bi-level mathematical problem (NP-hard) ( 4 – 6 ). Therefore, network design faces many challenges and complexities, and solving the NDP cannot guarantee finding the optimal global solution. On the other hand, solving NDP is often time-consuming, and most solution algorithms are unable to solve NDP in a reasonable amount of time. The run time increases exponentially with the network size. As such, finding a solution algorithm that solves the NDP accurately enough and in a reasonable time is essential.

This research seeks to develop a methodology to solve the CNDP more efficiently by reducing the model run time while maintaining satisfactory accuracy. The remainder of the paper is organized as follows: the next section reviews the literature; we then formulate the problem and describe the suggested solution algorithm, before discussing the results and concluding.

Literature Review

The NDP has a long history in the literature. LeBlanc and Boyce’s ( 7 ) investigation is one of the first studies that tried to solve the continuous network design using the Hooke–Jeeves and Powell methods. Marcotte ( 8 ) demonstrated that the Hooke–Jeeves and Powell method used by LeBlanc and Boyce ( 7 ) would not necessarily converge to the Pareto optimal solution. Other researchers have also proposed different solution algorithms. For instance, Suwansirikul et al. ( 9 ) introduced the equilibrium decomposed optimization approach. Peterson ( 10 ) adopted a heuristic approach and employed the cut-flow constraint rather than the conservation of flow constraint in the assignment sub-problem. Ban et al. ( 11 ) modeled the NDP with equilibrium constraints in the form of a nonlinear complementary problem. Meng et al. ( 12 ) used an appropriate approximation for the equilibrium traffic assignment problem. Billheimer and Gray ( 13 ) used a heuristic method based on network link addition and removal. Haghani and Daskin ( 14 ) proposed network aggregation to reduce the size of the network and thereby reduce the model’s run time. Moreover, dual problems of network design were employed to solve CNDPs by Balakrishnan et al. ( 15 ) and LeBlanc and Abdulaal ( 16 ). Liang et al. ( 17 ) developed a primal-dual method and exploited the Lagrangian dual to solve the transit network design problem. The dual problem was used to solve the CNDP. Tong et al. ( 18 ) decompose the NDP using Lagrangian relaxation.

Since the variables are continuous in CNDP, the gradient data of the traffic assignment problem, which is the traffic assignment problem sensitivity analysis, could be used. These methods exploit the sensitivity analysis of the user equilibrium assignment problem to solve the main problem (upper level) in their subgradient calculation. Davis ( 19 ) solved the network design using stochastic user equilibrium assignment and used sensitivity analysis to find the subgradient. Gao et al. ( 20 ) also used sensitivity analysis to solve a CNDP. As another example, Yang ( 21 ) performed a sensitivity analysis to solve an NDP with variable demand. In fact, several mathematical programming approaches could be employed to solve network design problems using sensitivity analysis. This leads to a variety of solution techniques.

Furthermore, assignment linearization methods have also been used in network design. Linearization has typically been used in continuous network design ( 22 ). Previous studies used a linear reaction for network design ( 23 ). Some other studies, like Wang et al. ( 24 ), use the reformulation–linearization technique to solve NDP. Moreover, the LeBlanc–Boyce model exploits a linearization approach as another approximation of optimal assignment rather than user equilibrium. This, however, imposes an error as a result of the use of the Cournot–Nash game rather than the Stackelberg game.

Decomposition-based techniques have been employed for both continuous and discrete network design. Lin et al. ( 25 ) used Dantzig–Wolfe decomposition to solve an NDP under dynamic traffic assignment. Dynamic traffic assignment not only increases the problem’s complexity but also seems unnecessary as the network design is a long-term problem, and the short-term dynamism of the network may not be of interest. Several studies adopted the Benders decomposition algorithm ( 26 , 27 ).

More recently, metaheuristic algorithms have also been used to solve the NDP. Zhou et al. ( 28 ) used a non-dominated sorting genetic algorithm to elucidate a CNDP. Bin et al. ( 29 ) proposed a leaf photosynthate-based method. However, these methods were more likely to be trapped in local minima without significant improvement in run time.

The review of the literature shows that different researchers haves used a variety of techniques to solve the NDP, some of which are: alternative constraints, equilibrium constraints, problem approximation, transformation into a one-level problem, network downsizing, dual problems, subgradient, sensitivity analysis, linearization, decomposition, and metaheuristic methods. As an alternative approach, Zilioniene et al. ( 30 ) focused on accelerating the lower-level assignment problem to accelerate the NDP.

Although many solution algorithms have been devised to solve the NDP, the run time is still a major issue. This paper proposes a partial linearized subgradient method to solve the CNDP. As shown here, previous efforts on linearization focused on linearizing the cost function and turning the lower-level problem into a linear or piecewise linear problem. Subgradient methods such as the one proposed by Chiou ( 31 ) use the sensitivity analysis of the UE problem. In this method, as will be discussed in the next section, at each iteration, we find the gradient of the UE problem by solving only one iteration of the UE problem at a time and using the linearized gradient information of that single step for that iteration. In other words, as in each iteration of the lower-level UE traffic assignment problem, a partially linear version of the problem is solved (similar to the well-known Frank–Wolfe algorithm); we use the gradient of that partially linearized assignment problem as the subgradient for the upper-level problem at each iteration. As a result, the NDP and the UE assignment are solved simultaneously. This is the difference between our proposed method and the previous methods.

Proposed Algorithm

As mentioned previously, CNDP can be represented as a leader-follower game where the transportation planners are the leaders, and the users/passengers that could (mostly) freely choose their path based on the leader’s decision are followers ( 32 , 33 ). It is assumed that transportation planners can influence the route choice behavior of the users but cannot force them to choose a certain path. The users make decisions based on their utilities. Thus, network design models seek to optimize the planners’ decisions by considering the interaction of such network decisions on the network users. In Table 1, all used parameters are introduced.

Table 1.

Parameters Used in the Proposed Method

Notation	Description
$X^{*} :$	The optimal link flow.
$\hat{C}$ :	The capacity vector in the network.
$Θ :$	The feasible link capacity set.
$C_{a} :$	Capacity of link a, $a \in A_{p}$ .
$C_{\max} :$	Maximum permissible capacity of each link.
$C_{a}^{*} and C_{ab} :$	Initial and optimal capacities of link a, respectively, $a \in A_{p}$ .
$f_{prs} :$	Flow in the path between the origin and destination.
$W :$	Set of origin–destination (OD) pairs in the network.
$δ_{a, p}^{rs}$ :	A binary parameter that is 1 when link a is on the path p; otherwise, it is zero.
$P_{rs} :$	Set of paths between the OD pair.
$g :$	Relative weight of the second part of the problem (it is typically assumed to be equal to the travel time value).
$e_{a} :$	Cost of one unit rise in the capacity in link a.
$t_{a} :$	Travel time for link a.
$x_{a} :$	Flow of link a.
$\bar{x_{a}}$ :	Auxiliary flow in network links.
$g_{p}^{rs}$ :	Auxiliary flow in path p from origin r to destination s.
$γ$ :	The conversion factor from investment cost to travel times.
$\bar{C_{a}}$ :	Auxiliary capacity for link a.

Let $G = (N, A)$ be a directed graph in which $A$ is the set of links, and $N$ is the set of nodes. Then, $A$ can be divided into two subsets, namely, (1) $A_{b}$ are the links of the base network, and (2) $A_{p}$ are the candidates for capacity enhancement. Furthermore, the demand can be represented as a triple $(r, s, q^{rs})$ , in which $r$ is the origin node, $s$ is the destination node, and $q^{rs}$ is the demand from origin $r$ to destination $s$ . Let $C$ be a set of link capacities and $X$ be a set of link flows. Then, the NDP can be formulated as:

\hat{C} = ar g_{c} minF (C, x^{*} (C))

(1)

\begin{matrix} s . t : \\ C \in Θ \end{matrix}

(2)

The formulation shown in Equations 1 and 2 is a mathematical problem with equilibrium constraints (MPEC). A symmetric MPEC can be rewritten as a bi-level mathematical programming problem as follows:

\begin{matrix} Z_{U} = mi n_{c} \sum_{a \in A} x_{a}^{*} * t_{a} (C_{a}, x_{a}^{*}) \\ + \sum_{a \in A_{p}} γ * e_{a} * (C_{a} - C_{a}^{b})^{2} \end{matrix}

(3)

\begin{matrix} s . t : \\ C_{a}^{b} \leq C_{a} \leq C_{a}^{\max} \forall a \in A \end{matrix}

(4)

Z_{L} = mi n_{x} \sum_{a \in A} \int_{0}^{x_{a}} t_{a} (C_{a}^{*}, w) dw

(5)

\begin{matrix} s . t : \\ \sum_{p \in p^{rs}} f_{p}^{rs} = q^{rs}, \forall rs \in W \end{matrix}

(6)

x_{a} = \sum_{rs \in w} \sum_{p \in p^{rs}} f_{p}^{rs} {* δ}_{a, p}^{rs}, \forall a \in A

(7)

The formulation in Equations 3 to 7 has been used in much previous research. It simultaneously optimizes the network’s construction cost and total travel time. As mentioned previously, in this paper, we proposed a partial linearized subgradient method to solve the CNDP. The nonlinear bi-level NDP is converted into a linear bi-level problem using the subgradient of the lower-level problem at each iteration of the solution. In the linearized form, both the upper and lower-level problems have the same objective function. Thus, the problem can be solved efficiently using the subgradient as a single objective problem.

In other words, $Φ = \sum_{a \in A} \int_{0}^{x_{a}} t_{a} (c_{a}, w) dw$ (i.e., the objective function of user equilibrium assignment). Using the first-order Taylor series expansion, $at each$ iteration k, $Φ$ is written as:

Φ^{k} = Φ^{k - 1} + \nabla Φ^{k - 1} \times (x^{k - 1} - x^{k})

(8)

Therefore, the minimization problem at the lower level can be written as:

mi n_{x} Φ^{k} = mi n_{x} [Φ^{k - 1} + \nabla Φ^{k - 1} \times (x^{k - 1} - x^{k})]

(9)

where x is the link flow in the network. By eliminating the constant terms from the problem above we get:

mi n_{x} Φ^{k} = mi n_{x} \nabla Φ^{k - 1} \times x^{k}

(10)

As $\nabla Φ^{k - 1} = t_{a}^{k - 1}$ then:

mi n_{x} Φ^{k} = mi n_{x} \sum_{a} x_{a}^{k} \times t_{a}^{k - 1}

(11)

As can be seen, Equation 11 is similar to the upper-level objective function at each iteration. Let $ψ$ denote the upper-level objective function. By assuming constant travel time at each iteration (as in the solution procedures for solving the UE problem), the upper-level function can be written as:

mi n_{c} ψ^{k} = mi n_{c} mi n_{x} Φ^{k}

(12)

It can be concluded that:

\frac{\partial ψ}{\partial C_{a}} = \frac{\partial mi n_{x} Φ^{k}}{\partial C_{a}}

(13)

The right side of Equation 13 is the gradient of the lower-level problem concerning capacity. This derivative can be easily calculated by analyzing the sensitivity of the now linear lower-level problem (at that iteration) to the capacity. Thus, the assumption of a constant travel time for each link gives:

\frac{\partial ψ^{k}}{\partial C_{a}} = \frac{\partial \sum_{a \in A} x_{a}^{k} \times t_{a}^{k - 1} (C_{a})}{\partial C_{a}}

(14)

It should be noted that $mi n_{x} Φ^{k}$ is generally non-differentiable. Thus, the derivative obtained at each point through the sensitivity analysis of the linearized problem is only one of the possible and potential gradients of the corresponding function. Particularly when the solution to the assignment problem is not degenerate, in this case, since we are considering only one of the potential gradients (based on the shortest paths in that iteration), it would seem reasonable to assume that the shortest paths used in the traffic assignment will remain unchanged. This assumption only holds when the solution is not degenerate. This is used as an approximation in the present study, which has been numerically shown to be reasonable. When the assignment results degenerate, reducing the travel time of one link (not on the shortest path) could cause the shortest path to change. However, it should be noted that we are proposing to solve the sensitivity analysis of the partially linearized assignment problem at each iteration. As such, the changes in the shortest path information are expected to be taken care of in the next iteration of the algorithm.

However, more accurate traffic assignment sensitivity analysis methods can be employed if deemed necessary (e.g., Tobin and Friesz [ 34 ] and Patriksson [ 35 ]), which will increase the run. The numerical investigation performed below will empirically show that the assumption made here is reasonable and that the additional complexity is unnecessary. The proposed algorithm to solve the CNDP is described below:

Step 0: Initialization: Select the convergence parameter ε and set the iteration counter to 0 ( $k = 0$ ). Set the travel time equal to the free flow travel time.

Step 1: All-or-nothing assignment: Increment the iteration counter by 1 ( $k : = k + 1$ ) and perform an all-or-nothing assignment using the travel time in the previous step to obtain the auxiliary flow. In this step, the following problem is solved:

\min \sum_{a \in A} \bar{x_{a}} \times t_{a} (C_{a}^{k - 1}, x_{a}^{k - 1})

(15)

$s . t :$

\sum_{p \in P^{rs}} g_{p}^{rs} = q^{rs} \forall rs \in w

(16)

\bar{x_{a}} = \sum_{rs \in w} \sum_{p \in P^{rs}} g_{p}^{rs} \times δ_{p}^{rs} \forall a \in A

(17)

Step 2: Calculation of the approximate derivative of the upper-level objective function: Estimate the auxiliary capacity by solving the following problem (it is easily solved using the gradient of the travel time function):

m i n_{Y . C .} \sum_{a \in A} (x_{a}^{k - 1} \times \frac{\partial t_{a}}{\partial c_{a}} (C_{a}^{k - 1}, x_{a}^{k - 1}) \times \bar{C_{a}}) + \sum_{a \in A_{p}} (2 γ \times e_{a} \times {(C_{a}^{k - 1} - C_{a}^{b})}^{2} \times \bar{C_{a}})

(18)

$s . t :$

C_{a}^{b} \leq \bar{C_{a}} \leq C_{a}^{\max} \forall a \in A_{p}

(19)

Step 3: Line search for the traffic assignment problem: Solve the line search for the equilibrium traffic assignment problem as in the Frank–Wolfe algorithm:

mi n_{α} \sum_{a \in A} \int_{0}^{x_{a}^{k - 1} + α \times (\bar{x_{a}^{k}} - x_{a}^{k - 1})} t_{a} (C_{a}^{k - 1}, w) dw

(20)

$s . t :$

0 \leq α \leq 1

(21)

Set $x_{a}^{k} : = x_{a}^{k - 1} + α \times ({\bar{x}}_{a}^{k} - x_{a}^{k - 1})$ and go to Step 4.

Step 4: Line search for the NDP: Solve the following line search problem for the upper-level problem:

\begin{matrix} mi n_{Y . C .} \sum_{a \in A} x_{a}^{k} \times (x_{a}^{k}, β) \\ + \sum_{a \in A_{p}} (γ \times e_{a} \times ((C_{a}^{k - 1} + β \times (\bar{C_{a}^{k}} - C_{a}^{k - 1})) - C_{a}^{b})^{2} \end{matrix}

(22)

$s . t :$

0 \leq β \leq 1

(23)

Set $C_{a}^{k} = C_{a}^{k - 1} + β_{a} \times ({\bar{C}}_{a}^{k} - C_{a}^{k - 1})$ and go to Step 5.

Step 5: Convergence control: Check whether the convergence criterion has been met. If yes, discontinue the process; if no, go to Step 1.

As shown in Figure 1, the simultaneous solution of the NDP and assignment is a characteristic of the proposed algorithm. Most previous research uses the so-called iterative assignment and design procedure, which solves the network assignment at each iteration. Instead of solving the assignment algorithm fully at each iteration of the upper level (as done in previous research), we solve one iteration of the assignment and one of the upper level at a time. This decreases the computational overhead of the CNDP. The proposed methodology uses two line search problems: one for the assignment problem and one for the NDP (based on the result of the assignment). This procedure will reduce the likelihood of falling into Braess’s paradox ( 36 ) trap by maintaining the correct structure of the leader-follower game in the NDP (the leader and follower each optimize their own objective function eventually). More specifically, the NDP is a Stackelberg game ( 37 ). Such games have a leader-follower structure, and one should solve the NDP based on the assumption that the decision maker is the leader while the users are followers and each is optimizing their own objectives without cooperation. If the NDP is structured as a Cournot–Nash game, the cooperation between the leader and follower will increase the probability of falling into the trap of Braess’s paradox. This is more likely to happen if both the leader and follower use the same objective function.

Figure 1.

Flowchart of the continuous network design algorithm.

Results

In this section, we apply the proposed algorithm to two well-known case studies to evaluate its appropriateness and efficiency compared with previous studies. The first network is a small one in which Braess’s paradox is possible. In the second case study, the model will be applied to the Sioux Falls network for comparison.

Small Sized Network

In this small network, previously used in the research, we investigate the likelihood of Braess’s paradox, as shown in Figure 2. The objective function is as in Equation 24.

\begin{matrix} Ψ = \sum_{a \in A} x_{a} \times t_{a} (C_{a}, x_{a}) \\ + \sum_{a \in A_{p}} 1.5 \times e_{a} \times (C_{a} - C_{a}^{b})^{2} \end{matrix}

(24)

The data are adapted from the Suwansirikul et al. ( 9 ) implementation. Table 2 describes the network and the parameters of the volume delay function. The functional form of the volume delay function is as $t_{a} = A_{a} + B_{a} \times (\frac{x_{a}}{C_{a}})^{4}$ for each link $a$ .

Figure 2.

Small size network.

Table 2.

First Network Parameters

Link	Parameters
Link	$d_{a}$	C	B	A
(1, 2)	2	40	0.6	4
(1, 3)	2	40	0.9	6
(2, 3)	1	60	0.3	2
(2, 4)	2	40	0.75	5
(4, 3)	2	40	0.45	3

A total of four scenarios were implemented: (I) Scenario 1, with 100 units of demand from node 1 to node 4, with a maximum capacity budget of four units; (II) Scenario 2, with 150 units of demand from node 1 to node 4, with a maximum capacity budget of eight units; (III) Scenario 3 with 200 units of demand from node 1 to node 4, with a maximum capacity budget of 16 units; and (IV) Scenario 4 with 300 units of demand from node 1 to node 4, with a maximum budget of 45 units. The proposed algorithm was applied to all four scenarios, and the results were compared with other similar studies. The results for the first scenario and the results obtained from previous studies are given in Table 3.

Table 3.

Comparison of the Proposed Algorithm and Some Previous Studies on Scenario 1

Link	Models
Link	Proposed algorithm	Equilibrium decomposed optimization	Hooke–Jeeves	MINOS	Full enumeration
(1, 2)	1.33	1.31	1.25	1.34	1.35
(1, 3)	1.12	1.19	1.2	1.21	1.2
(2, 3)	0	0.06	0	0	0
(2, 4)	0.97	0.94	0.95	0.97	0.95
(4, 3)	1.09	1.06	1.1	1.1	1.1
Objective function	1,200.58	1,200.64	1,200.61	1,200.58	1,200.58

Note: MINOS = Mixed-Integer Nonlinear Optimization System.

As seen in Table 3, the results obtained by our proposed algorithm are similar to the ones obtained by the full enumeration of the solutions (global optimum solution). Therefore, the proposed algorithm is efficient in this small case study and will likely avoid Braess’s paradox trap. Table 4 reports the solutions obtained under all scenarios.

Table 4.

Comparison of the Proposed Algorithm and Some Previous Studies on all Scenarios

Models
Scenarios	Proposed algorithm	Equilibrium decomposed optimization	Hooke–Jeeves	MINOS
1	1,200.58	1,200.64	1,200.61	1,200.58
2	3,156.22	3,156.24	3,156.38	3,156.21
3	7,086.17	7,086.45	7,086.21	7,086.12
4	21,210.11	21,210.54	21,209.91	21,209.9

Note: MINOS = Mixed-Integer Nonlinear Optimization System.

According to Table 4, the proposed algorithm is comparable to previous studies. It should be noted that the MINOS method is the most accurate yet the most time-consuming technique to solve the CNDP. As can be seen, the results of the proposed method are in good agreement with the MINOS method. The results of the proposed method were obtained in a maximum of 10 iterations; the computational overhead of 10 iterations is equal to performing 10 shortest paths searches, not 10 full assignments. As mentioned, the assignment and CNDP are solved simultaneously, and each iteration of our proposed algorithm does not fully solve the equilibrium assignment problem until convergence. As such, the computational overhead of 10 iterations of our algorithm is roughly equal to one iteration of other algorithms that require the traffic assignment to be fully solved.

Medium Size Network

The well-known Sioux Falls network is used as the second numerical case study. The Sioux Falls network has been used in many CNDP studies, such as ( 38 – 43 ). It has 24 OD pairs and 76 links. Different variants of the Sioux Falls network are available. The present study adopted the variant reported by Suwansirikul et al. ( 9 ). The Sioux Falls network and candidate links are shown in Figure 3. Also, a map of Sioux Falls is shown in Figure 4. Table 5 shows the candidate projects and the capacity increase cost per unit.

Figure 3.

Sioux Falls network and candidate links.

Figure 4.

Sioux Falls map.

Table 5.

Candidate Projects and the Capacity Increase Cost per Unit

Number	Link	Cost in thousands of dollars
1	(19, 16)	26
2	(20, 17)	40
3	(26, 25)	25
4	(48, 29)	48
5	(74, 39)	34

The Sioux Falls case study also has the same objective function as the first one, except for $γ$ . Thus, the objective function is:

\begin{matrix} Ψ = \sum_{a \in A} x_{a} \times t_{a} (C_{a}, x_{a}) \\ + \sum_{a \in A_{p}} 0.001 \times e_{a} \times (C_{a} - C_{a}^{b})^{2} \end{matrix}

(25)

Previous studies show that the maximum capacity budget is approximately 25 units.

As seen in Table 6, the proposed algorithm has been shown to be significantly faster than all previous methods while still getting a pretty accurate result (only 0.5% different from the best solution while being more than 1,000 times faster). Our proposed algorithm converged after 44 shortest path calculations, which is roughly equal to three fully converged iterations in other algorithms (we expect the assignment to assemble in 10–20 iterations). Figure 5 shows the convergence of the proposed method. The closest model for speed to our algorithm was Conjugate Gradient (CG) ( 41 ). While still being faster, our proposed algorithm converged to a better solution than CG.

Table 6.

Comparison of the Proposed Method and Some Previous Methods in the Sioux Falls Network

Link	The rate of capacity increase
Link	IOA ( 44 )	LeBlanc and Abdulaal ( 16 )	Suwansirikul et al. ( 9 )	MINOS ( 9 )	Friesz et al. ( 45 )	Meng et al. ( 12 )
(6, 8)	4.69	3.8	4.59	4.8	5.38	5.57
(7, 8)	3.9	3.6	1.52	1.2	2.26	1.64
(8, 6)	1.27	3.8	5.45	4.8	5.5	5.62
(8, 7)	1.66	2.4	2.33	0.8	2.01	1.64
(9, 10)	2.33	2.8	1.27	2	2.64	3.14
(10, 9)	2.34	1.4	2.33	2.6	2.47	3.28
(10, 16)	5.57	3.2	0.41	4.8	4.54	7.65
(13, 24)	4.69	4	4.59	4.4	4.45	3.80
(16, 10)	5.47	4	2.71	4.8	4.21	7.38
(24, 13)	6.25	4	2.71	4.4	4.67	3.69
Objective function	87.34	81.77	83.47	81.25	80.87	81.75
Number of assignments	31	108	12	58	3,900	2,700
Link	CG ( 41 )	PT ( 41 )	GA ( 46 )	CS ( 47 )	EDEMIS ( 48 )	Proposed algorithm
(6, 8)	4.77	5.03	5.17	5.1	5.54	5.38
(7, 8)	4.86	5.22	2.94	1.35	1.92	2.49
(8, 6)	3.07	1.83	4.72	6.49	5.24	5.16
(8, 7)	2.68	1.57	1.76	2.3	1.8	2.49
(9, 10)	2.84	2.79	2.39	2.91	2.9	2.86
(10, 9)	2.97	2.66	2.91	2.05	2.84	2.90
(10, 16)	5.68	6.19	2.92	3.67	3.59	4.85
(13, 24)	4.27	4.96	5.99	5.22	3.91	4.52
(16, 10)	4.4	4.067	3.63	3.42	3.58	4.85
(24, 13)	5.52	3.92	4.43	4.88	4.98	4.30
Objective function	82.53	82.53	81.74	81.51	81.6	81.29
Number of assignments	6	7	77	36	18	3

Note: MINOS = Mixed-Integer Nonlinear Optimization System; CG = Conjugate Gradient; IOA = Iterative optimization and assignment; GA = Genetic Algorithm; CS = Cuckoo Search; EDEMIS = Enhanced Differential Evolution algorithm based on Multiple Improvement Strategies.

Figure 5.

Convergence of the proposed algorithm for Sioux Falls network.

Discussion

Network improvement is an important tool in mitigating congestion in transportation networks. Although numerous studies have discussed the NDP in the past several years, NDP still poses a challenging problem. This study proposes a partial linearized subgradient method to solve the CNDP. The proposed algorithm is numerically shown to reduce the model’s computational overhead while converging to a satisfying solution.

The proposed algorithm was applied to two case studies: a small network where there is a possibility of the Braess’s paradox arising, and the Sioux Falls network. As the results were shown to be promising on the small network, the algorithm was also applied to the Sioux Falls network to compare with previous studies. Our proposed algorithm solved the CNDP and converged to a reasonable solution after only 30 shortest path calculations (with an accuracy of only 0.5% less than the best solution). Assuming that 10 to 20 shortest path calculations are required to solve the traffic assignment problem on the Sioux Falls network, the proposed algorithm was able to converge to a reasonable solution with a computational overhead of roughly three fully converged traffic assignment problems. Figure 6 compares the results obtained on the Sioux Falls network. The horizontal axis shows the algorithms. The vertical axis on the right side shows the required number of assignments for the algorithm to converge, and the vertical axis on the left shows the objective function’s value. It can be seen that the proposed algorithm had the highest speed, with only 0.52% lower accuracy than that proposed by Friesz et al. ( 45 ) and 0.05% lower accuracy than Suwansirikul et al. ( 9 ). The model introduced by Friesz had the highest accuracy. However, it required many assignment iterations (i.e., 3,900 assignments). Although the proposed algorithm is an approximate method, it uses partial linearization of the lower-level problem and ignores the potential degenerate solutions; the numerical results indicated that the solutions had satisfactory performance. In addition, a review of previous studies indicates that previous methods, particularly metaheuristic algorithms, were mostly approximate and stochastic. Since the NDP is non-convex, the global optimal solution cannot be ensured. However, the proposed algorithm deterministically converges to an efficient solution in a short time.

Figure 6.

Comparison of second network results.

Footnotes

Author Contributions

The authors confirm contribution to the paper as follows: study conception and design: Navid Kalantari, Hamid Mirzahossein, Travis Waller; data collection: Navid Kalantari, Hamid Mirzahossein, Pooyan Najafi; analysis and interpretation of results: Navid Kalantari, Pooyan Najafi, Travis Waller; draft manuscript preparation: Navid Kalantari, Hamid Mirzahossein, Pooyan Najafi, Travis Waller, Xiang Zhang. All authors reviewed the results and approved the final version of the manuscript.

Declaration of Conflicting Interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) received no financial support for the research, authorship, and/or publication of this article.

ORCID iDs

Hamid Mirzahossein

Travis Waller

Data Accessibility Statement

Some or all data, models, or code that support the findings of this study are available from the corresponding author on reasonable request.

References

Zhao

Zhang

Transportation Infrastructure Restoration Optimization Considering Mobility and Accessibility in Resilience Measures. Transportation Research Part C: Emerging Technologies, Vol. 117, 2020, p. 102700.

Farvaresh

Sepehri

M. M.

A Branch and Bound Algorithm for Bi-level Discrete Network Design Problem. Networks and Spatial Economics, Vol. 13, No. 1, 2013, pp. 67–106.

Poorzahedy

Turnquist

M. A.

Approximate Algorithms for the Discrete Network Design Problem. Transportation Research Part B: Methodological, Vol. 16, No. 1, 1982, pp. 45–55.

Megiddo

On the Complexity of the One-Terminal Network Design Problem. Operations Research Letters, Vol. 1, No. 3, 1982, pp. 105–107.

Ketabi

Salzborn

F. J.

A Concavity Result for Network Design Problems. Journal of Global Optimization, Vol. 24, No. 1, 2002, pp. 79–88.

Johnson

D. S.

Lenstra

J. K.

Kan

A. R.

The Complexity of the Network Design Problem. Networks, Vol. 8, No. 4, 1978, pp. 279–285.

LeBlanc

L. J.

Boyce

D. E.

A Bilevel Programming Algorithm for Exact Solution of the Network Design Problem with User-Optimal Flows. Transportation Research Part B: Methodological, Vol. 20, No. 3, 1986, pp. 259–265.

Marcotte

A Note on a Bilevel Programming Algorithm by LeBlanc and Boyce. Transportation Research Part B: Methodological, Vol. 22, No. 3, 1988, pp. 233–236.

Suwansirikul

Friesz

T. L.

Tobin

R. L.

Equilibrium Decomposed Optimization: A Heuristic for the Continuous Equilibrium Network Design Problem. Transportation Science, Vol. 21, No. 4, 1987, pp. 254–263.

10.

Peterson

B. E.

A Cut-Flow Procedure for Transportation Network Optimization. Networks, Vol. 10, No. 1, 1980, pp. 33–43.

11.

Ban

J. X.

Liu

H. X.

Ferris

M. C.

Ran

A General MPCC Model and Its Solution Algorithm for Continuous Network Design Problem. Mathematical and Computer Modelling, Vol. 43, No. 5–6, 2006, pp. 493–505.

12.

Meng

Yang

Bell

M. G. H.

An Equivalent Continuously Differentiable Model and a Locally Convergent Algorithm for the Continuous Network Design Problem. Transportation Research Part B: Methodological, Vol. 35, No. 1, 2001, pp. 83–105.

13.

Billheimer

J. W.

Gray

Network Design with Fixed and Variable Cost Elements. Transportation Science, Vol. 7, No. 1, 1973, pp. 49–74.

14.

Haghani

A. E.

Daskin

M. S.

Aggregation Effects on the Network Design Problem. Journal of Advanced Transportation, Vol. 20, No. 3, 1986, pp. 239–258.

15.

Balakrishnan

Magnanti

T. L.

Wong

R. T.

A Dual-Ascent Procedure for Large-Scale Uncapacitated Network Design. Operations Research, Vol. 37, No. 5, 1989, pp. 716–740.

16.

LeBlanc

L. J.

Abdulaal

An Efficient Dual Approach to the Urban Road Network Design Problem. Computers & Mathematics with Applications, Vol. 5, No. 1, 1979, pp. 11–19.

17.

Liang

Gao

Sun

Yang

H. K.

Bus Transit Network Design with Uncertainties on the Basis of a Metro Network: A Two-Step Model Framework. Transportation Research Part B: Methodological, Vol. 126, 2019, pp. 115–138.

18.

Tong

Zhou

Miller

H. J.

Transportation Network Design for Maximizing Space–Time Accessibility. Transportation Research Part B: Methodological, Vol. 81, 2015, pp. 555–576.

19.

Davis

G.A.

Exact Local Solution of the Continuous Network Design Problem via Stochastic User Equilibrium Assignment. Transportation Research Part B: Methodological, Vol. 28, No. 1, 1994, pp. 61–75.

20.

Gao

Sun

Zhang

A Globally Convergent Algorithm for Transportation Continuous Network Design Problem. Optimization and Engineering, Vol. 8, No. 3, 2007, pp. 241–257.

21.

Yang

Sensitivity Analysis for the Elastic-Demand Network Equilibrium Problem with Applications. Transportation Research Part B: Methodological, Vol. 31, No. 1, 1997, pp. 55–70.

22.

Wang

D. Z. W.

H. K.

Global Optimum of the Linearized Network Design Problem with Equilibrium Flows. Transportation Research Part B: Methodological, Vol. 44, No. 4, 2010, pp. 482–492.

23.

Cho

H.-J.

S.-C.

Solving Bilevel Network Design Problem Using a Linear Reaction Function Without Nondegeneracy Assumption. Transportation Research Record: Journal of the Transportation Research Board, 1999. 1667(1): 96–106.

24.

Wang

D. Z. W.

Liu

Szeto

W. Y.

A Novel Discrete Network Design Problem Formulation and Its Global Optimization Solution Algorithm. Transportation Research Part E: Logistics and Transportation Review, Vol. 79, 2015, pp. 213–230.

25.

Lin

D.-Y.

Karoonsoontawong

Waller

S. T.

A Dantzig-Wolfe Decomposition Based Heuristic Scheme for Bi-level Dynamic Network Design Problem. Networks and Spatial Economics, Vol. 11, No. 1, 2011, pp. 101–126.

26.

Bagloee

S. A.

Sarvi

Rajabifard

Thompson

R. G.

System Optimal Relaxation and Benders Decomposition Algorithm for the Large-Sized Road Network Design Problem. International Journal of Logistics Systems and Management, Vol. 34, No. 4, 2019, pp. 486–509.

27.

Zetina

C. A.

Contreras

Cordeau

J.-F.

Exact Algorithms Based on Benders Decomposition for Multicommodity Uncapacitated Fixed-Charge Network Design. Computers & Operations Research, Vol. 111, 2019, pp. 311–324.

28.

Zhou

Yang

Sun

Wang

A Continuous Transportation Network Design Problem with the Consideration of Road Congestion Charging. Sustainability, Vol. 13, No. 13, 2021, p. 7008.

29.

Bin

Wenxuan

Zhen

Yunpeng

A Heuristic Algorithm Based on Leaf Photosynthate Transport. Simulation, Vol. 94, No. 7, 2017, pp. 593–607.

30.

Žilionienė

D’Acierno

Botte

Gallo

A General Methodology for Reducing Computing Times of Road Network Design Algorithms. International Journal of Supply and Operations Management, Vol. 6, No. 2, 2019, pp. 126–141.

31.

Chiou

S.-W.

A Subgradient Optimization Model for Continuous Road Network Design Problem. Applied Mathematical Modelling, Vol. 33, No. 3, 2009, pp. 1386–1396.

32.

Boyce

D. E.

Urban Transportation Network-Equilibrium and Design Models: Recent Achievements and Future Prospects. Environment and Planning A: Economy and Space, Vol. 16, No. 11, 1984, pp. 1445–1474.

33.

Yang

Bell

M. G. H.

Models and Algorithms for Road Network Design: A Review and Some New Developments. Transport Reviews, Vol. 18, No. 3, 1998, pp. 257–278.

34.

Tobin

R. L.

Friesz

T. L.

Sensitivity Analysis for Equilibrium Network Flow. Transportation Science, Vol. 22, No. 4, 1988, pp. 242–250.

35.

Patriksson

Sensitivity Analysis of Traffic Equilibria. Transportation Science, Vol. 38, No. 3, 2004, pp. 258–281.

36.

Sheffi

Urban Transportation Networks: Equilibrium Analysis with Mathematical Programming Methods. Prentice-Hall, Inc., Englewood Cliffs, NJ, 1985.

37.

Sherali

H. D.

Soyster

A. L.

Murphy

F. H.

Stackelberg-Nash-Cournot Equilibria: Characterizations and Computations. Operations Research, Vol. 31, No. 2, 1983, pp. 253–276.

38.

Luathep

Sumalee

Lam

W. H. K.

Z.-C.

H. K.

Global Optimization Method for Mixed Transportation Network Design Problem: A Mixed-Integer Linear Programming Approach. Transportation Research Part B: Methodological, Vol. 45, No. 5, 2011, pp. 808–827.

39.

LeBlanc

L. J.

An Algorithm for the Discrete Network Design problem. Transportation Science, Vol. 9, No. 3, 1975, pp. 183–199.

40.

Josefsson

Patriksson

Sensitivity Analysis of Separable Traffic Equilibrium Equilibria with Application to Bilevel Optimization in Network Design. Transportation Research Part B: Methodological, Vol. 41, No. 1, 2007, pp. 4–31.

41.

Chiou

S.-W.

Bilevel Programming for the Continuous Transport Network Design Problem. Transportation Research Part B: Methodological, Vol. 39, No. 4, 2005, pp. 361–383.

42.

Bar-Gera

Hellman

Patriksson

Computational Precision of Traffic Equilibria Sensitivities in Automatic Network Design and Road Pricing. Procedia - Social and Behavioral Sciences, Vol. 80, 2013, pp. 41–60.

43.

Abdulaal

LeBlanc

L. J.

Continuous Equilibrium Network Design Models. Transportation Research Part B: Methodological, Vol. 13, No. 1, 1979, pp. 19–32.

44.

Allsop

R. E.

Some Possibilities for Using Traffic Control to Influence Trip Distribution and Route Choice. Transportation and Traffic Theory, Proceedings, Sydney, NSW, Australia, 1974.

45.

Friesz

T. L.

Anandalingam

Mehta

N. J.

Nam

Shah

S. J.

Tobin

R. L.

The Multiobjective Equilibrium Network Design Problem Revisited: A Simulated Annealing Approach. European Journal of Operational Research, Vol. 65, No. 1, 1993, pp. 44–57.

46.

Mathew

T. V.

Sharma

Capacity Expansion Problem for Large Urban Transportation Networks. Journal of Transportation Engineering, Vol. 135, No. 7, 2009, pp. 406–415.

47.

Baskan

Determining Optimal Link Capacity Expansions in Road Networks Using Cuckoo Search Algorithm with Lévy Flights. Journal of Applied Mathematics, Vol. 2013, 2013, p. 718015.

48.

Baskan

Ozan

Dell’Orco

Marinelli

Improving the Performance of the Bilevel Solution for the Continuous Network Design Problem. Promet-Traffic & Transportation, Vol. 30, No. 6, 2018, pp. 709–720.