# Time-Dependent Transportation Network Design considering Construction Impact

Authors: Yi He; Ziqi Song; Lihui Zhang
Journal: Journal of Advanced Transportation
 (2018)

---

## Abstract

A traditional discrete network design problem (DNDP) always assumes transportation infrastructure projects to be one-time events and ignores travelers’ delays caused by construction work. In fact, infrastructure construction usually lasts for a long time, and the impact on traffic can be substantial. In this paper, we introduce time dimension into the traditional DNDP to explicitly consider the impact of road construction and adopt an overtime policy to add flexibility to construction duration. We address the problem of selecting road-widening projects in an urban network, determining the optimal link capacity, and designing the schedule of the selected projects simultaneously. A time-dependent DNDP (T-DNDP) model is developed with the objective of minimizing total weighted net user cost during the entire planning horizon. An active-set algorithm is applied to solve the model. A simple example network is first utilized to demonstrate the necessity of considering the construction process in T-DNDP and to illustrate the trade-off between the construction impact and the benefit realized through capacity extension. We also solve the T-DNDP model with data from the Sioux Falls network, which contains 24 nodes, 76 links, and 528 origin-destination (O-D) pairs. Computational results for the problem are also presented.


---

## Body

## 1. Introduction

Transportation plays an essential role in economic development and in the overall improvement of people’s living standard. Unfortunately, rapid population growth and the accompanying accelerated economic development in urban areas are usually accompanied by sharp increases in traffic demand, which may induce all sorts of traffic-related issues, such as congestion, air pollution, and noise pollution. Among these issues, traffic congestion is particularly a prominent problem, especially in large cities. According to the 2015 Urban Mobility Scorecard, the cumulative travel delay caused by congestion was about 7 billion hours and the wasted fuel totaled almost 3 billion gallons in 2014 alone in the United States [1]. To maintain a reasonable level of service and alleviate current and future traffic congestion, transportation agencies are often faced with the need to expand the existing road network. However, generally they must work with a limited amount of resources. Therefore, given all of the potential candidate road-widening projects, selecting appropriate projects becomes a crucial decision in maximizing the benefit of expansion projects. This kind of problem is usually referred to in the literature as the network design problem (NDP).Over the past few decades, NDP has been widely studied. Most of the literature related to NDP has focused on either modeling or new algorithms for network design models. However, these early studies regarded road construction work as a one-time event and did not consider the gradual improvement of the network until researchers introduced the time dimension to the traditional NDP (see [2–4]). Lo and Szeto [4] claimed that the road network is improved year by year before the completion of the improvement project, which makes the NDP model more realistic. Nevertheless, even though they considered network improvement to be gradual in their model, they still assumed the construction process to be a one-off procedure. Actually, capacity expansion work usually involves work zones and lane closures, which may reduce the current link capacity during construction and result in congestion and delays for road users. Furthermore, road infrastructure construction generally lasts for months or even years, and the impact of construction may greatly affect planners’ decisions. For example, when multiple projects are simultaneously underway, planners may choose to adjust the schedule of some projects to avoid excessive delays in a region. Therefore, the impact of construction work should not simply be ignored.This study explicitly considers construction impact in conjunction with the benefits brought about by capacity expansion as the two primary factors that govern the network design problem. Furthermore, in light of the fact that the construction process may have a tremendous impact on the road network, shortening the construction period represents a possible method for mitigating the impact. Thus, the proposed model also allows the construction period to be flexible, which means the planners can choose to speed up construction to shorten its duration by paying overtime to construction personnel.Compared with existing NDP models, the proposed model has the following advantages:(1)
The construction impact is clearly evaluated so that the selection and schedule of road infrastructure projects will be optimized.(2)
This model adopts an overtime policy in the candidate projects, which allows planners to choose whether or not to accelerate a project by paying overtime. Thus, the construction durations of the candidate projects are flexible.(3)
This model is able to address the problem of selecting road-widening projects from several candidate projects, simultaneously determining the optimal amount of increased capacity and designing the optimal schedule for the chosen projects.


## 2. Background

### 2.1. Network Design Problem

The transportation NDP aims to achieve certain objectives, for example, reducing traffic congestion, energy consumption, and environmental pollution, by choosing improvements or additions to an existing network [5]. A common methodology used to formulate the NDP is bilevel programming. The upper level is the system level, which optimizes the system benefits subject to limited resources, while the lower level is the users’ level, which models users’ route choice behavior in the network. The upper level can be formulated with different decision variables and objective functions. The decision variables can be merely continuous or discrete or can contain both continuous and discrete elements. Based on the types of decision variables, network design problems are generally divided into three categories. The network design problem with only continuous variables is called the continuous network design problem (CNDP) (see [6–11]). In road network design problems, continuous variables are usually introduced in order to simplify computation. For example, the capacity expansion of a roadway can be continuous (see [12, 13]). However, continuous variables do not necessarily indicate the changes that are practical, because road capacity is normally measured by the number of lanes. Hence, despite the fact that it may be more computationally expensive, the discrete network design problem (DNDP) with solely discrete variables (see [14–22]) and the mixed network design problem (MNDP) with both continuous and discrete variables (see [23–26]) are still worth investigating.Previous studies have made substantial contributions to the understanding and applications of DNDP. Some have studied various applications associated with DNDP. For instance, Drezner and Wesolowsky [18] formulated a DNDP for the purpose of selecting the best distribution of one-way and two-way routes in a road network. Wu et al. [27] solved the DNDP of choosing the location of pedestrian-only streets in a multimodel network. Song et al. [28] developed a DNDP model that settled the problems of selecting locations for high-occupancy vehicle (HOV)/high-occupancy vehicle (HOT) lanes and determining toll rates on HOT lanes. Miandoabchi and Farahani [29] determined street orientations and expansions, as well as lane allocations, based on the reserve capacity concept in a DNDP model. Others have developed different kinds of approaches to solve DNDP. It is well known that solving a bilevel network design problem is very difficult because the problem is NP-hard and nonconvex. After Leblanc [15] proposed a branch-and-bound algorithm to solve this bilevel problem, many researchers began to seek better approaches to assess the trade-off between computation of speed and solution accuracy. For example, Dantzig et al. [6] transformed the nonconvex programming problem to a convex problem using system equilibrium flow to replace user equilibrium flow. Poorzahedy and Turnquist [30] utilized approximation to transform the bilevel problem into a single-level problem. Solanki et al. [31] decomposed the highway network design problem in a sequence of small subproblems and limited the search using heuristics to reduce computation time. Poorzahedy and Abulghasemi [20] adapted metaheuristic algorithms to solve NDP for the Sioux Falls network. Poorzahedy and Rouhani [32] improved the metaheuristic algorithm and designed the hybrid metaheuristic algorithm. A genetic algorithm is also widely used (see [19, 33, 34]). Gao et al. [21] transformed the upper-level programming of the traditional DNDP to a nonlinear problem based on the support function concept. Zhang et al. [35] developed the active-set algorithm, which eliminates complementarity constraints in the DNDP by assigning initial values and solving binary knapsack problems. Farvaresh and Sepehri [36] revised the branch-and-bound algorithm proposed by Leblanc [15] for bilevel DNDP.


### 2.2. Time-Dependent Network Design Problem

In recent years, the time varying evolution of road networks began to gain interest in transportation network design problems. Different time scales were studied in the literature, ranging from the smallest day-to-day dynamics [2, 3, 37] to network upgrades spanning years [38–40]. Lo and Szeto [4] introduced the time dimension to CNDP and built a comprehensive and practical model that considered not only user equilibrium (UE), but also travel demand and land-use patterns as time-dependent. In conjunction with other researchers, they further studied a series of time-dependent NDP problems, including budget sensitivity analysis among users, private toll road operators, and the government [41]; the trade-off between the social and financial aspects of three possible network improvement strategies under demand and the value of time uncertainty [42]; the trade-off between social benefit and intergeneration equity [38]; cost recovery issues over time [40, 43]; land-use transport interaction over time [44]; sustainability with land-use transport interaction over time [45]; health impacts attributable to network construction [46]; and a multiobjective time-dependent model to determine the sequence of link expansion projects and link construction projects [47]. Time dimension was also introduced in other studies. For instance, Kim et al. [48] formulated a time-dependent DNDP framework to address the project scheduling problem; Ukkusuri and Patil [49] developed a multiperiod flexible network design model with demand uncertainty and demand elasticity; Hosseininasab and Shetab-Boushehri [50] integrated project selection and scheduling into a single time-dependent DNDP model.However, in the literature referenced above, the road network is optimized for a certain future time without considering the construction impact. In practice, modifications to a network are gradual processes rather than one-off events. Hence, the construction process, which results in a negative impact to traffic, should also be considered. The construction process is explicitly modeled in this paper.


## 2.1. Network Design Problem

The transportation NDP aims to achieve certain objectives, for example, reducing traffic congestion, energy consumption, and environmental pollution, by choosing improvements or additions to an existing network [5]. A common methodology used to formulate the NDP is bilevel programming. The upper level is the system level, which optimizes the system benefits subject to limited resources, while the lower level is the users’ level, which models users’ route choice behavior in the network. The upper level can be formulated with different decision variables and objective functions. The decision variables can be merely continuous or discrete or can contain both continuous and discrete elements. Based on the types of decision variables, network design problems are generally divided into three categories. The network design problem with only continuous variables is called the continuous network design problem (CNDP) (see [6–11]). In road network design problems, continuous variables are usually introduced in order to simplify computation. For example, the capacity expansion of a roadway can be continuous (see [12, 13]). However, continuous variables do not necessarily indicate the changes that are practical, because road capacity is normally measured by the number of lanes. Hence, despite the fact that it may be more computationally expensive, the discrete network design problem (DNDP) with solely discrete variables (see [14–22]) and the mixed network design problem (MNDP) with both continuous and discrete variables (see [23–26]) are still worth investigating.Previous studies have made substantial contributions to the understanding and applications of DNDP. Some have studied various applications associated with DNDP. For instance, Drezner and Wesolowsky [18] formulated a DNDP for the purpose of selecting the best distribution of one-way and two-way routes in a road network. Wu et al. [27] solved the DNDP of choosing the location of pedestrian-only streets in a multimodel network. Song et al. [28] developed a DNDP model that settled the problems of selecting locations for high-occupancy vehicle (HOV)/high-occupancy vehicle (HOT) lanes and determining toll rates on HOT lanes. Miandoabchi and Farahani [29] determined street orientations and expansions, as well as lane allocations, based on the reserve capacity concept in a DNDP model. Others have developed different kinds of approaches to solve DNDP. It is well known that solving a bilevel network design problem is very difficult because the problem is NP-hard and nonconvex. After Leblanc [15] proposed a branch-and-bound algorithm to solve this bilevel problem, many researchers began to seek better approaches to assess the trade-off between computation of speed and solution accuracy. For example, Dantzig et al. [6] transformed the nonconvex programming problem to a convex problem using system equilibrium flow to replace user equilibrium flow. Poorzahedy and Turnquist [30] utilized approximation to transform the bilevel problem into a single-level problem. Solanki et al. [31] decomposed the highway network design problem in a sequence of small subproblems and limited the search using heuristics to reduce computation time. Poorzahedy and Abulghasemi [20] adapted metaheuristic algorithms to solve NDP for the Sioux Falls network. Poorzahedy and Rouhani [32] improved the metaheuristic algorithm and designed the hybrid metaheuristic algorithm. A genetic algorithm is also widely used (see [19, 33, 34]). Gao et al. [21] transformed the upper-level programming of the traditional DNDP to a nonlinear problem based on the support function concept. Zhang et al. [35] developed the active-set algorithm, which eliminates complementarity constraints in the DNDP by assigning initial values and solving binary knapsack problems. Farvaresh and Sepehri [36] revised the branch-and-bound algorithm proposed by Leblanc [15] for bilevel DNDP.


## 2.2. Time-Dependent Network Design Problem

In recent years, the time varying evolution of road networks began to gain interest in transportation network design problems. Different time scales were studied in the literature, ranging from the smallest day-to-day dynamics [2, 3, 37] to network upgrades spanning years [38–40]. Lo and Szeto [4] introduced the time dimension to CNDP and built a comprehensive and practical model that considered not only user equilibrium (UE), but also travel demand and land-use patterns as time-dependent. In conjunction with other researchers, they further studied a series of time-dependent NDP problems, including budget sensitivity analysis among users, private toll road operators, and the government [41]; the trade-off between the social and financial aspects of three possible network improvement strategies under demand and the value of time uncertainty [42]; the trade-off between social benefit and intergeneration equity [38]; cost recovery issues over time [40, 43]; land-use transport interaction over time [44]; sustainability with land-use transport interaction over time [45]; health impacts attributable to network construction [46]; and a multiobjective time-dependent model to determine the sequence of link expansion projects and link construction projects [47]. Time dimension was also introduced in other studies. For instance, Kim et al. [48] formulated a time-dependent DNDP framework to address the project scheduling problem; Ukkusuri and Patil [49] developed a multiperiod flexible network design model with demand uncertainty and demand elasticity; Hosseininasab and Shetab-Boushehri [50] integrated project selection and scheduling into a single time-dependent DNDP model.However, in the literature referenced above, the road network is optimized for a certain future time without considering the construction impact. In practice, modifications to a network are gradual processes rather than one-off events. Hence, the construction process, which results in a negative impact to traffic, should also be considered. The construction process is explicitly modeled in this paper.


## 3. Basic Considerations

This paper considers the problem of simultaneously determining the selection and scheduling of road expansion projects for a transportation network. The evaluation of a design is based on system performance throughout a given planning horizon, which includes the construction process. Below, we summarize our basic considerations and assumptions for the modeling and analysis of the construction process of road expansion projects.(1)
Within the planning horizon, a road segment has at most one expansion project. This consideration is not overly restrictive, as we can always divide a road segment into several parallel links and assign each link with a project.(2)
The construction procedure of an expansion project spans a continuous period of time.(3)
Throughout the planning horizon, the route choice behaviors of drivers in the network follow the UE principle. Considering the construction process, the traffic network will change, as will the UE pattern.(4)
The potential demand growth over time is known.(5)
The interest and inflation rates are constant within the planning horizon.For the convenience of readers, below we list some notations frequently used in the paper.Sets
N: set of nodes
L: set of links
L
1: set of links with a potential expansion project
L
2: set of links without a potential expansion project
W: set of O-D pairsParameters
a: link a=(i,j)∈L
w: O-D pair w∈W
M: the total number of unit time intervals for the planning horizon
M
C: the total number of unit time intervals for the construction time window
m: time interval m∈1,2,…,M
d
m
w: travel demand between O-D pair w∈W in time interval m∈1,2,…,M
D
a
0: fixed time cost for the expansion project on link a∈L1
D
a
1: variable time cost per additional lane for the expansion project on link a∈L1
c
a: average cost per time interval during construction for the expansion project on link a∈L1 without overtime workVariables
x
a
,
m
w: traffic flow on link a for O-D pair w∈W in time interval m∈1,2,…,M
v
a
,
m: aggregate traffic flow on link a∈L in time interval m∈1,2,…,M
t
a
,
m: travel time of link a∈L in time interval m∈1,2,…,M
C
a
,
m: capacity of link a∈L in time interval m∈1,2,…,M
y
a
,
m: a binary variable, representing whether link a∈L1 is under construction in time interval m∈1,2,…,M. If yes, ya,m=1; otherwise, ya,m=0
z
a
,
m: a binary variable, representing whether construction has been finished on link a∈L1 in time interval m∈1,2,…,M. If yes, za,m=1; otherwise, za,m=0
S
a
,
m: a binary variable, representing whether time interval m∈1,2,…,M is the start date of construction on link a∈L1. If yes, Sa,m=1; otherwise, Sa,m=0
E
a
,
m: a binary variable, representing whether time interval m∈1,2,…,M is the end date of construction on link a∈L1. If yes, Ea,m=1; otherwise, Ea,m=0
l
a: number of newly added lanes on link
D
a
e: the estimated construction duration for the expansion project on link a∈L1 without overtime work
D
a
r: reduced construction duration for the expansion project on link a∈L1 through overtime work.


## 4. Problem Formulation

Consider a general transportation networkG(N,L), where N and L are the set of nodes and the set of directed links, respectively. The latter are represented as a node pair (i,j), where i,j∈N and i≠j, or a single letter a. There are two types of links in the network, the links with a potential road-widening project, and the links without a potential project, denoted as L1 and L2, respectively. In this study, the planning horizon 0,T is equally divided into M unit intervals. The unit interval could be a month, a season, or another reasonable time interval. Note that the unit interval is the unit of measurement of the time cost of the construction process. The planning horizon includes a construction time window and a nonconstruction time window. All construction projects are supposed to be completed within the construction time window; the nonconstruction time window is designed to evaluate the continuing benefits realized through the finished road expansion projects. Planners determine the lengths of these two time windows. Approximately, the duration of the nonconstruction time window represents the service life of the improved roads before requiring extensive renovation. For an individual project, the benefit period begins immediately after the completion of the project. Therefore, the benefit period should be at least as long as the nonconstruction time window. Let MC denote the number of intervals in the construction time window, MC<M.Figure1 shows an example of the timeline of one road expansion project. In this example, the planning horizon is divided into 10 intervals, among which the former 5 intervals belong to the construction time window, and the latter 5 intervals belong to the nonconstruction time window. This project is scheduled to start at the beginning of the second time interval, and the estimated construction duration is four unit intervals. The planner decides to shorten the construction duration by one interval through overtime work. Therefore, the actual construction duration is reduced to 3 unit intervals, and the benefit lasts for 6 unit intervals (the detailed description of the flexible construction duration will be presented in the following model).Figure 1
An example of the timeline of a road expansion project.


### 4.1. Time-Dependent Traffic Assignment Constraints

Feasible Region.To describe the feasible flow distributions of a network, let A be the node-arc incidence matrix associated with the network, and let Ew be an “input-output” vector indicating the origin and destination of O-D pair w. Ew has exactly two nonzero components: one has the value 1 corresponding to the origin node of the O-D pair w, and the other’s value is −1, corresponding to the destination node. For all other nodes in this O-D pair, Ew equals 0. The flow distributions are said to be feasible if and only if the following constraints hold for xmw:(1)Axmw=Ewdmw∀w∈W,m∈1,2,…,M(2)xmw≥0∀w∈W,m∈1,2,…,M(3)vm=∑wxmw∀m∈1,2,…,M,where xmw∈RL is a vector whose components, xa,mw, represent a link flow on link a for O-D pair w in interval m, and vm is a vector whose components, va,m, represent an aggregate link flow on link a in interval m. dmw represents the travel demand between O-D pair w in interval m. For simplicity, the travel demand of each O-D pair is assumed to be increasing at a constant rate. For an O-D pair w∈W, given the travel demand in the first interval, that is, d1w, the demand in interval m∈1,2,…,M is calculated as(4)dmw=d1w·1+εwm-1∀w∈W,m∈1,2,…,M,where εw is the growth factor of demand between O-D pair w.To make the subsequent expressions more easily discernable, we introduce a setVmF for each period m to cover all of the feasible flow distributions: (5)VmF=vm:vm=∑wxmw,Axmw=Ewdmw,xmw≥0,∀w∈W∀m∈1,2,…,M.Time-Dependent Link Capacity.Within the planning horizon, if a link is selected for expansion, its capacity will be time-dependent. During construction, the capacity of a link may be reduced due to the impact of construction; after construction, the capacity of a link will be improved due to added lanes. Two binary variables, ya,m and za,m, are introduced to indicate the status of a link a∈L1 with a potential widening project in time interval m∈1,2,…,M. ya,m represents whether link a∈L1 is under construction in time interval m∈1,2,…,M. If yes, ya,m=1; otherwise, ya,m=0. za,m represents whether construction has been finished on link a∈L1 in time interval m∈1,2,…,M. If yes, za,m=1; otherwise, za,m=0. Note that if link a∈L1 is not selected for expansion, there will be no construction process on link a, and ya,m=0,za,m=0,∀m∈1,2,…,M. The time-dependent capacity function can be formulated in (6)–(8):(6)Ca,m=Ca0-ya,m·Car+za,m·la·Ca1∀a∈L1,m∈1,2,…,M(7)Ca,m≤Camax∀a∈L1,m∈1,2,…,M(8)Ca,m=Ca0∀a∈L2,m∈1,2,…,M,where Ca0, Car, Ca1, and Camax are the initial capacity, the reduced capacity during construction, the capacity of a single lane, and the maximum allowable capacity of link a, respectively. la denotes the number of lanes added after construction, which is a decision variable to be optimized in our model. la is an integer variable. Equation (7) restricts the capacity of a link to be less than its maximum allowable capacity.Travel Time.In this paper, the Bureau of Public Roads (BPR) function is used to define the link travel time. The travel time of an existing link in each period, ta,m, is determined by the link travel flow, va,m, and the link capacity, Ca,m.(9)ta,m=ta01+0.15va,mCa,m4∀a∈L,m∈1,2,…,M,where ta0 is the free flow travel time on link a.User Equilibrium Assignment.For each time interval m∈1,2,…,M, the user’s route choice behavior is assumed to follow Wardrop’s first principle [51], which is ensured by(10)minvm∑a∈L∫0va,mta,mωdω,s.t.vm∈VmFDefinitional  constraints6,8,9.The KKT conditions of this user equilibrium model are shown as follows:(11)ti,j,mvi,j,m,yi,j,m,zi,j,m,li,j-ρi,mw-ρj,mw≥0∀w∈W,i,j∈L,m∈1,2,…,Mxi,j,mti,j,mvi,j,m,yi,j,m,zi,j,m,li,j-ρi,mw-ρj,mw=0∀w∈W,i,j∈L,where the multipliers ρi,mw and ρj,mw are associated with (1) and are called “node potentials” [52].


### 4.2. Time-Dependent Construction Constraints

Design Constraints with Flexible Construction Duration.In practice, for each expansion project, the workload can be estimated based on the planner’s experience. We assume that the normal working hours per day are fixed, for example, 8 hours, and the work efficiency of a crew team is stable. The construction duration for a project can then be roughly estimated according to the workload of that project. The estimated construction duration, denoted as Dae, can be expressed as a function of the number of newly added lanes la, given by(12)Dae=fala.In this model, we assume thatDae is linearly related to la for simplicity. Other functional forms can be adopted in our model framework without difficulty:(13)Dae=Da0+Da1·la∀a∈L1(14)la∈Z∀a∈L1,where Da0 represents the fixed time cost of the project on link a regardless how many lanes are added, for example, the required time for construction preparation and quality control, and Da1 denotes the extra time cost for each additional lane.In practice, planners may choose to pay extra money for overtime work to accelerate a project if necessary. In this paper, we introduce an integer variable,Dar, to denote the reduced component of the construction duration. The actual duration for the project on link a should then be Dae-Dar. Even though overtime work can speed up the process, project duration cannot be infinitely shortened. Let Damax denote the maximum allowable shortened duration for a project on link a.(15)Dar≤Damax∀a∈L1(16)Dar∈Z⍈∀a∈L1.Within the planning horizon, the construction process on linka∈L1 should be a continuous period of unit intervals. To properly model the timeline of the construction process, we introduce two additional binary variables, Sa,m and Ea,m. Sa,m=1 implies that the construction process on link a starts at the beginning of interval m, and Sa,m=0 otherwise. Ea,m=1 implies that the construction process on link a ends by the end of interval m, and Ea,m=0 otherwise. Note that if a link a∈L1 is not selected for expansion, there will be no construction process on link a, and Sa,m=0,Ea,m=0,∀m∈1,2,…,M. Moreover, there should be only one starting time and one ending time for each chosen project. As shown in Figure 2, we use the same road expansion project used in Figure 1 to illustrate the values of Sa,m, Ea,m, ya,m, and za,m throughout the entire planning horizon.Figure 2
An example to illustrate the values ofSa,m, Ea,m, ya,m, and za,m throughout the entire planning horizon.VariablesSa,m, Ea,m, ya,m, and za,m are not mutually independent. Based on their definitions and the fact that they are all binary variables, the relationships among them can be specified by a series of conditional constraints. Let the construction time window be [1,MC]. Subsequently, the nonconstruction time window is [MC+1,M]. This yields the following constraints:(17)Sa,m,Ea,m,ya,m,za,m∈0,1,∀a∈L1,m∈1,2,…,M(18)Sa,m,Ea,m,ya,m=0∀a∈L1,m∈MC+1,…,M(19)za,m=za,MC+1∀a∈L1,m∈MC+2,…,M.Equation (17) requires variables Sa,m, Ea,m, ya,m, and za,m to be binary. Equation (18) ensures that no project can start, end, or be under construction in the nonconstruction time window. Equation (19) ensures that the completion status of the potential expansion project on link a∈L1 will not change in the nonconstruction time window.The logical relationship betweenSa,m and ya,m can then be given by the following conditional constraints:(20)Sa,m≤ya,m∀a∈L1,m∈1,2,…,MC(21)Sa,m≤1-ya,m-1∀a∈L1,m∈2,3,…,MC(22)Sa,m≥ya,m-ya,m-1∀a∈L1,m∈2,3,…,MC.Equation (20) ensures that if the project on link a starts at time interval m, that is, Sa,m=1, this project must be under construction at interval m: that is, ya,m=1. Equation (21) guarantees that if link a is under construction at time interval m-1, that is, ya,m-1=1, it cannot start at time interval m: that is, Sa,m=0. Equation (22) ensures that if the project on link a is not under construction at interval m-1 and is under construction at time interval m, that is, ya,m=1,ya,m-1=0, then interval m must be the starting time of the project: that is, Sa,m=1. These three equations cover all possible relationships between Sa,m and ya,m.Similarly, the relationships betweenEa,m and ya,m are specified by the following constraints:(23)Ea,m≤ya,m∀a∈L1,m∈1,2,…,MC(24)Ea,m≤1-ya,m+1∀a∈L1,m∈1,2,…,MC-1(25)Ea,m≥ya,m-ya,m+1∀a∈L1,m∈1,2,…,MC-1.Equation (23) means that if the project on link a is to end at time interval m, that is, Ea,m=1, this project must be under construction at interval m: that is, ya,m=1. Equation (24) ensures that if the project on link a is to end at time interval m, that is, Ea,m=1, this project cannot be under construction at time interval m+1: that is, ya,m+1=0. Additionally, (25) guarantees that if the project on link a is under construction at interval m and is no longer under construction at time interval m+1, that is, ya,m=1,ya,m+1=0, then interval m must be the ending time of the project; that is, Ea,m=1.Likewise, the logical relationships betweenEa,m and za,m are given as follows:(26)Ea,m≤za,m+1∀a∈L1,m∈1,2,…,MC(27)Ea,m≤1-za,m∀a∈L1,m∈1,2,…,MC(28)Ea,m≥za,m+1-za,m∀a∈L1,m∈1,2,…,MC.Equation (26) ensures that if time interval m is the ending time of the project on link a, that is, Ea,m=1, then in the next interval m+1, the project must have been finished: that is, za,m+1=1. Equation (27) indicates that if in time interval m the project on link a has already been finished, that is, za,m=1, then time interval m cannot be the ending time: that is, Ea,m=0. Equation (28) ensures that if in time interval m+1 the project on link a∈L1 has already been finished, that is, za,m+1=1, but in interval m the project has not been finished, that is, za,m=0, then interval m must be the ending time of the project: that is, Ea,m=1.Moreover,Sa,m and Ea,m should satisfy the following constraints:(29)∑m=1MCSa,m≤1∀a∈L1∑m=1MCEa,m≤1∀a∈L1∑m=1MCSa,m=∑m=1MCEa,m∀a∈L1.Equations (29) ensure that the potential expansion project on link a∈L1 either has no starting time and no ending time, that is, the project is not selected, or has exactly one starting time and one ending time.Finally, the following two constraints must also hold:(30)∑m=1MCya,m=Dae-Dar·∑m=1MCSa,m∀a∈L1(31)∑m=1MCya,m+∑m=1Mza,m=M·∑m=1MCSa,m-∑m=1MCSa,m·m-1∀a∈L1.The value of∑m=1MCSa,m can represent whether the potential expansion project on link a∈L1 is selected. If the project is selected, ∑m=1MCSa,m=1, and ∑m=1MCSa,m=0 otherwise. Therefore, (30) guarantees that if the potential expansion project on link a∈L1 is selected, that is, ∑m=1MCSa,m=1, the total length of the time intervals under construction equals the actual construction duration. Equation (31) ensures that if the potential expansion project on link a∈L1 is selected, that is, ∑m=1MCSa,m=1, the total duration of the construction period and benefit period is equal to the planning horizon, subtracting the duration before construction. Note that ∑m=1MCSa,m·(m-1) can represent the duration before construction if the potential expansion project on link a∈L1 is selected.These above constraints, that is, (13)–(31), ensure that if the potential expansion project on link a∈L1 is selected, different phases of the project (i.e., before construction, under construction, and after construction) occur in correct sequence.In order to reduce the complexity of our model and improve computational speed, the nonlinear constraint (30), together with constraints (7) and (15), can be equivalently replaced by the following linear constraints:(32)∑m=1MCya,m=Da0·∑m=1MCSa,m+Da1·la-Dar∀a∈L1(33)la·Ca1≤Camax-Ca0·∑m=1MCSa,m∀a∈L1(34)Dar≤Damax·∑m=1MCSa,m∀a∈L1.We briefly prove the equivalence by examining both the selected and unselected projects. If the potential expansion project on linka∈L1 is not selected, ∑m=1MCSa,m=0. Equations (14) and (33) imply that la=0. Equations (16) and (34) imply that Dar=0. Consequently, (32) implies that ∑m=1MCya,m=0=Dae-Dar·∑m=1MCSa,m, which is identical to (30). If the potential expansion project on link a∈L1 is selected, ∑m=1MCSa,m=1. Equation (33) is reduced to (7), and (34) is reduced to (15). Equations (13) and (32) imply that ∑m=1MCya,m=Dae-Dar=Dae-Dar·∑m=1MCSa,m, which is identical to (30).Budget and Resource Constraints.We assume that the government allocates a certain amount of construction budget Bτ at the beginning of time interval τ. This time interval τ does not have to be the same as the predefined time interval m. We introduce a conversion factor β to express the ratio between τ and m. For example, if the unit of m is month, and the unit of τ is year, then β should be 12. In this study, we assume that the remaining budget in period τ is available for use in period τ+1. Similar assumptions have been employed in [4]. Apart from the budget limitation, we should also consider other resource limitations, for example, the limitation of construction personnel and the limited number of specialized construction equipment. For the sake of simplicity, we only consider the construction personnel limitation in this paper. We assume that all construction teams have the same construction capability, and each ongoing project requires one construction team. The total number of available construction teams is limited and denoted by Rmax. The budget and construction personnel constraints are then given as follows:(35)TC1+RB1=B1(36)TCτ+RBτ=RBτ-1+Bτ∀τ>1,τ∈1,2,…,MCβ(37)∑a∈L1ya,m≤Rmax∀m∈1,2,…,MC,where TCτ is the total construction cost generated in period τ and RBτ is the cumulative remaining budget in period τ. Equations (35) and (36) represent the budget constraints. MC/β converts the construction time to the same time unit as τ. If the government allocates the entire budget at the beginning of the planning horizon, the budget constraints will be reduced to (35). Equation (37) specifies that, for each time interval m∈1,2,…,MC, the total construction teams at work should not exceed the number of available teams.The total construction cost of a project consists of two components: basic costs to complete the project (e.g., equipment cost, material cost, and labor cost) and extra costs for overtime work. Based on the previous assumption that a construction team works a fixed number of hours per day under normal condition, we assume that, without overtime work, each construction time interval for the expansion project on linka∈L1 includes an identical and fixed basic cost, denoted as ca. ca includes all of the wages for workers and other costs (e.g., material costs, equipment costs) needed in a normal construction time interval. If the planner wants to shorten the duration of a project, workers may choose any period to work overtime as long as they meet the time limit requirement. To simplify our model, we assume the overtime cost to be placed in the starting time interval of any project (Figure 3). The example in Figure 3 corresponds to the example in Figures 1 and 2. The expansion project originally lasts for four months, and it is reduced to three months through overtime. Therefore, both the basic cost in the fourth construction interval and the additional wages attributable to overtime work are allocated to the first construction interval when applying overtime work.Figure 3
Illustration of construction costs for a project.The total construction cost in periodτ can be formulated as(38)TCτ=∑m=βτ-1+1βτ∑a∈L1ya,m·ca+∑a∈L1OCa,τ·1+θ1τ-1∀τ∈1,2,…,MCβ,where OCa,τ is the overtime cost for the project on link a in period τ. θ1 represents the inflation rate.(39)∑τ=1MC/βOCa,τ=λ·ca·1+μ·Dar+1-λ·ca·Dar∀a∈L1(40)OCa,τ≥0∀a∈L1,∀τ∈1,2,…,MCβ(41)OCa,τ≤∑m=βτ-1+1βτSa,m·Q∀a∈L1,∀τ∈1,2,…,MCβ,where λ denotes the percentage of the workers’ salary in the total construction cost, μ is the increased rate of overtime salary, and Q is a large constant value. The first term on the right-hand side of (39) represents the salary portion of the overtime cost, and the second term represents the remaining portion. Equations (39)–(41) ensure that the overtime cost for the expansion project on link a∈L1 is placed in the starting period.


### 4.3. Objective Function

As aforementioned, during the construction period, the system performance may deteriorate due to work zones or closure of lanes. Different decision makers may have different preferences when selecting road expansion projects. Some may focus more on future benefits of the projects, while others may focus more on reducing adverse impacts of the projects during construction. To provide a flexible model, the objective function is to minimize the weighted sum of the total travel time during construction period and the total travel time during benefit period. This can be stated as(42)NPV=α1∑τ=1MC/βTTτ1+θ2τ-1+α2∑τ=MC/β+1M/βTTτ1+θ2τ-1,where α1 and α2 are the weighting factors for the construction period and benefit period, respectively, TTτ is the total travel time occurring in period τ, θ2 is the discount rate, and 1+θ2τ-1 represents the discount factor for period τ. TTτ is given in(43)TTτ=∑m=βτ-1+1βτ∑a∈Lta,mva,m∀τ∈1,2,…,Mβ.


### 4.4. The Base Model

Based on the above notations, the time-dependent discrete network design problem considering construction impact and flexible duration can be formulated as the following mathematical programP1.P1minNPV=α1∑τ=1MC/β∑m=βτ-1+1βτ∑a∈Lta,mva,m1+θ2τ-1+α2∑τ=MC/β+1M/β∑m=βτ-1+1βτ∑a∈Lta,mva,m1+θ2τ-1s.t.vm∈VmF∀m∈1,2,…,MTime-dependent  definitional  constraints,  equations6,8,9;Traffic  assignment  constraints,  equations11;Design  constraints,  equations13,14,16–29,31–34;Budget  and  resource  constraints,  equations35–41.This formulation involves two integer variables (i.e.,la and Dar). As is generally known, it is much more difficult to solve optimization problems with integer variables, especially for large-scale networks. Hence, we introduce two sets of binary variables, pab1 and qab2, to replace la and Dar as follows:(44)la=∑b1=1B12b1-1pab1∀a∈L1(45)Dar=∑b2=1B22b2-1qab2∀a∈L1.According to (44), the number of newly built lanes la can take the value 0 to (2B1-1). For example, if we use three binary variables to represent la, that is, B1=3, then la=pa1+2pa2+4pa3, ranging from 0 to 7. Similarly, the reduced value of construction interval Dar can range from 0 to (2B2-1). Note that the binary variables can be written in the form of complementarity constraints so that the binary variable can be treated as continuous variables as follows:(46)0≤pab1≤1∀a∈L1pab11-pab1=0∀a∈L10≤qab1≤1∀a∈L1qab11-qab1=0∀a∈L1.Then,la and Dar in previous equations can be replaced by ∑b1=1B12(b1-1)pab1 and ∑b2=1B22(b2-1)qab2, respectively. Equations (6), (13), (32), (33), (34), and (39) are replaced by (47), (48), (49), (50), (51), and (52), respectively.(47)Ca,m=Ca0-ya,m·Car+za,m·∑b1=1B12b1-1pab1·Ca1∀a∈L,m∈1,2,…,M(48)Dae=Da0+Da1·∑b1=1B12b1-1pab1∀a∈L1(49)∑m=1MCya,m=Da0·∑m=1MCSa,m+Da1·∑b1=1B12b1-1pab1-∑b2=1B22b2-1qab2∀a∈L1(50)∑b1=1B12b1-1pab1·Ca1≤Camax-Ca0·∑m=1MCSa,m∀a∈L1(51)∑b2=1B22b2-1qab2≤Damax·∑m=1MCSa,m∀a∈L1(52)∑τ=1MC/βOCa,τ=λ·ca·1+μ·∑b2=1B22b2-1qab2+1-λ·ca·∑b2=1B22b2-1qab2∀a∈L1.We also use the following complementarity constraints to replace (17) so that the binary variables Sa,m, Ea,m, ya,m, and za,m can be treated as continuous variables:(53)0≤Sa,m≤1∀a∈L1,m∈1,2,…,MCSa,m1-Sa,m=0∀a∈L1,m∈1,2,…,MC0≤Ea,m≤1∀a∈L1,m∈1,2,…,MCEa,m1-Ea,m=0∀a∈L1,m∈1,2,…,MC0≤ya,m≤1∀a∈L1,m∈1,2,…,MCya,m1-ya,m=0∀a∈L1,m∈1,2,…,MC0≤za,m≤1∀a∈L1,m∈1,2,…,MC+1za,m1-za,m=0∀a∈L1,m∈1,2,…,MC+1.Based on the above discussions, the base model can be reformulated as follows:P2minNPV=α1∑τ=1MC/β∑m=βτ-1+1βτ∑a∈Lta,mva,m1+θ2τ-1+α2∑τ=MC/β+1M/β∑m=βτ-1+1βτ∑a∈Lta,mva,m1+θ2τ-1s.t.vm∈VmF∀m∈1,2,…,M46–53;Time-dependent  definitional  constraint,  equations8,9;Traffic  assignment  constraints,  equations11;Design  constraints,  equations18–29,31;Budget  and  resource  constraints,  equations35–38,40-41.


## 4.1. Time-Dependent Traffic Assignment Constraints

Feasible Region.To describe the feasible flow distributions of a network, let A be the node-arc incidence matrix associated with the network, and let Ew be an “input-output” vector indicating the origin and destination of O-D pair w. Ew has exactly two nonzero components: one has the value 1 corresponding to the origin node of the O-D pair w, and the other’s value is −1, corresponding to the destination node. For all other nodes in this O-D pair, Ew equals 0. The flow distributions are said to be feasible if and only if the following constraints hold for xmw:(1)Axmw=Ewdmw∀w∈W,m∈1,2,…,M(2)xmw≥0∀w∈W,m∈1,2,…,M(3)vm=∑wxmw∀m∈1,2,…,M,where xmw∈RL is a vector whose components, xa,mw, represent a link flow on link a for O-D pair w in interval m, and vm is a vector whose components, va,m, represent an aggregate link flow on link a in interval m. dmw represents the travel demand between O-D pair w in interval m. For simplicity, the travel demand of each O-D pair is assumed to be increasing at a constant rate. For an O-D pair w∈W, given the travel demand in the first interval, that is, d1w, the demand in interval m∈1,2,…,M is calculated as(4)dmw=d1w·1+εwm-1∀w∈W,m∈1,2,…,M,where εw is the growth factor of demand between O-D pair w.To make the subsequent expressions more easily discernable, we introduce a setVmF for each period m to cover all of the feasible flow distributions: (5)VmF=vm:vm=∑wxmw,Axmw=Ewdmw,xmw≥0,∀w∈W∀m∈1,2,…,M.Time-Dependent Link Capacity.Within the planning horizon, if a link is selected for expansion, its capacity will be time-dependent. During construction, the capacity of a link may be reduced due to the impact of construction; after construction, the capacity of a link will be improved due to added lanes. Two binary variables, ya,m and za,m, are introduced to indicate the status of a link a∈L1 with a potential widening project in time interval m∈1,2,…,M. ya,m represents whether link a∈L1 is under construction in time interval m∈1,2,…,M. If yes, ya,m=1; otherwise, ya,m=0. za,m represents whether construction has been finished on link a∈L1 in time interval m∈1,2,…,M. If yes, za,m=1; otherwise, za,m=0. Note that if link a∈L1 is not selected for expansion, there will be no construction process on link a, and ya,m=0,za,m=0,∀m∈1,2,…,M. The time-dependent capacity function can be formulated in (6)–(8):(6)Ca,m=Ca0-ya,m·Car+za,m·la·Ca1∀a∈L1,m∈1,2,…,M(7)Ca,m≤Camax∀a∈L1,m∈1,2,…,M(8)Ca,m=Ca0∀a∈L2,m∈1,2,…,M,where Ca0, Car, Ca1, and Camax are the initial capacity, the reduced capacity during construction, the capacity of a single lane, and the maximum allowable capacity of link a, respectively. la denotes the number of lanes added after construction, which is a decision variable to be optimized in our model. la is an integer variable. Equation (7) restricts the capacity of a link to be less than its maximum allowable capacity.Travel Time.In this paper, the Bureau of Public Roads (BPR) function is used to define the link travel time. The travel time of an existing link in each period, ta,m, is determined by the link travel flow, va,m, and the link capacity, Ca,m.(9)ta,m=ta01+0.15va,mCa,m4∀a∈L,m∈1,2,…,M,where ta0 is the free flow travel time on link a.User Equilibrium Assignment.For each time interval m∈1,2,…,M, the user’s route choice behavior is assumed to follow Wardrop’s first principle [51], which is ensured by(10)minvm∑a∈L∫0va,mta,mωdω,s.t.vm∈VmFDefinitional  constraints6,8,9.The KKT conditions of this user equilibrium model are shown as follows:(11)ti,j,mvi,j,m,yi,j,m,zi,j,m,li,j-ρi,mw-ρj,mw≥0∀w∈W,i,j∈L,m∈1,2,…,Mxi,j,mti,j,mvi,j,m,yi,j,m,zi,j,m,li,j-ρi,mw-ρj,mw=0∀w∈W,i,j∈L,where the multipliers ρi,mw and ρj,mw are associated with (1) and are called “node potentials” [52].


## 4.2. Time-Dependent Construction Constraints

Design Constraints with Flexible Construction Duration.In practice, for each expansion project, the workload can be estimated based on the planner’s experience. We assume that the normal working hours per day are fixed, for example, 8 hours, and the work efficiency of a crew team is stable. The construction duration for a project can then be roughly estimated according to the workload of that project. The estimated construction duration, denoted as Dae, can be expressed as a function of the number of newly added lanes la, given by(12)Dae=fala.In this model, we assume thatDae is linearly related to la for simplicity. Other functional forms can be adopted in our model framework without difficulty:(13)Dae=Da0+Da1·la∀a∈L1(14)la∈Z∀a∈L1,where Da0 represents the fixed time cost of the project on link a regardless how many lanes are added, for example, the required time for construction preparation and quality control, and Da1 denotes the extra time cost for each additional lane.In practice, planners may choose to pay extra money for overtime work to accelerate a project if necessary. In this paper, we introduce an integer variable,Dar, to denote the reduced component of the construction duration. The actual duration for the project on link a should then be Dae-Dar. Even though overtime work can speed up the process, project duration cannot be infinitely shortened. Let Damax denote the maximum allowable shortened duration for a project on link a.(15)Dar≤Damax∀a∈L1(16)Dar∈Z⍈∀a∈L1.Within the planning horizon, the construction process on linka∈L1 should be a continuous period of unit intervals. To properly model the timeline of the construction process, we introduce two additional binary variables, Sa,m and Ea,m. Sa,m=1 implies that the construction process on link a starts at the beginning of interval m, and Sa,m=0 otherwise. Ea,m=1 implies that the construction process on link a ends by the end of interval m, and Ea,m=0 otherwise. Note that if a link a∈L1 is not selected for expansion, there will be no construction process on link a, and Sa,m=0,Ea,m=0,∀m∈1,2,…,M. Moreover, there should be only one starting time and one ending time for each chosen project. As shown in Figure 2, we use the same road expansion project used in Figure 1 to illustrate the values of Sa,m, Ea,m, ya,m, and za,m throughout the entire planning horizon.Figure 2
An example to illustrate the values ofSa,m, Ea,m, ya,m, and za,m throughout the entire planning horizon.VariablesSa,m, Ea,m, ya,m, and za,m are not mutually independent. Based on their definitions and the fact that they are all binary variables, the relationships among them can be specified by a series of conditional constraints. Let the construction time window be [1,MC]. Subsequently, the nonconstruction time window is [MC+1,M]. This yields the following constraints:(17)Sa,m,Ea,m,ya,m,za,m∈0,1,∀a∈L1,m∈1,2,…,M(18)Sa,m,Ea,m,ya,m=0∀a∈L1,m∈MC+1,…,M(19)za,m=za,MC+1∀a∈L1,m∈MC+2,…,M.Equation (17) requires variables Sa,m, Ea,m, ya,m, and za,m to be binary. Equation (18) ensures that no project can start, end, or be under construction in the nonconstruction time window. Equation (19) ensures that the completion status of the potential expansion project on link a∈L1 will not change in the nonconstruction time window.The logical relationship betweenSa,m and ya,m can then be given by the following conditional constraints:(20)Sa,m≤ya,m∀a∈L1,m∈1,2,…,MC(21)Sa,m≤1-ya,m-1∀a∈L1,m∈2,3,…,MC(22)Sa,m≥ya,m-ya,m-1∀a∈L1,m∈2,3,…,MC.Equation (20) ensures that if the project on link a starts at time interval m, that is, Sa,m=1, this project must be under construction at interval m: that is, ya,m=1. Equation (21) guarantees that if link a is under construction at time interval m-1, that is, ya,m-1=1, it cannot start at time interval m: that is, Sa,m=0. Equation (22) ensures that if the project on link a is not under construction at interval m-1 and is under construction at time interval m, that is, ya,m=1,ya,m-1=0, then interval m must be the starting time of the project: that is, Sa,m=1. These three equations cover all possible relationships between Sa,m and ya,m.Similarly, the relationships betweenEa,m and ya,m are specified by the following constraints:(23)Ea,m≤ya,m∀a∈L1,m∈1,2,…,MC(24)Ea,m≤1-ya,m+1∀a∈L1,m∈1,2,…,MC-1(25)Ea,m≥ya,m-ya,m+1∀a∈L1,m∈1,2,…,MC-1.Equation (23) means that if the project on link a is to end at time interval m, that is, Ea,m=1, this project must be under construction at interval m: that is, ya,m=1. Equation (24) ensures that if the project on link a is to end at time interval m, that is, Ea,m=1, this project cannot be under construction at time interval m+1: that is, ya,m+1=0. Additionally, (25) guarantees that if the project on link a is under construction at interval m and is no longer under construction at time interval m+1, that is, ya,m=1,ya,m+1=0, then interval m must be the ending time of the project; that is, Ea,m=1.Likewise, the logical relationships betweenEa,m and za,m are given as follows:(26)Ea,m≤za,m+1∀a∈L1,m∈1,2,…,MC(27)Ea,m≤1-za,m∀a∈L1,m∈1,2,…,MC(28)Ea,m≥za,m+1-za,m∀a∈L1,m∈1,2,…,MC.Equation (26) ensures that if time interval m is the ending time of the project on link a, that is, Ea,m=1, then in the next interval m+1, the project must have been finished: that is, za,m+1=1. Equation (27) indicates that if in time interval m the project on link a has already been finished, that is, za,m=1, then time interval m cannot be the ending time: that is, Ea,m=0. Equation (28) ensures that if in time interval m+1 the project on link a∈L1 has already been finished, that is, za,m+1=1, but in interval m the project has not been finished, that is, za,m=0, then interval m must be the ending time of the project: that is, Ea,m=1.Moreover,Sa,m and Ea,m should satisfy the following constraints:(29)∑m=1MCSa,m≤1∀a∈L1∑m=1MCEa,m≤1∀a∈L1∑m=1MCSa,m=∑m=1MCEa,m∀a∈L1.Equations (29) ensure that the potential expansion project on link a∈L1 either has no starting time and no ending time, that is, the project is not selected, or has exactly one starting time and one ending time.Finally, the following two constraints must also hold:(30)∑m=1MCya,m=Dae-Dar·∑m=1MCSa,m∀a∈L1(31)∑m=1MCya,m+∑m=1Mza,m=M·∑m=1MCSa,m-∑m=1MCSa,m·m-1∀a∈L1.The value of∑m=1MCSa,m can represent whether the potential expansion project on link a∈L1 is selected. If the project is selected, ∑m=1MCSa,m=1, and ∑m=1MCSa,m=0 otherwise. Therefore, (30) guarantees that if the potential expansion project on link a∈L1 is selected, that is, ∑m=1MCSa,m=1, the total length of the time intervals under construction equals the actual construction duration. Equation (31) ensures that if the potential expansion project on link a∈L1 is selected, that is, ∑m=1MCSa,m=1, the total duration of the construction period and benefit period is equal to the planning horizon, subtracting the duration before construction. Note that ∑m=1MCSa,m·(m-1) can represent the duration before construction if the potential expansion project on link a∈L1 is selected.These above constraints, that is, (13)–(31), ensure that if the potential expansion project on link a∈L1 is selected, different phases of the project (i.e., before construction, under construction, and after construction) occur in correct sequence.In order to reduce the complexity of our model and improve computational speed, the nonlinear constraint (30), together with constraints (7) and (15), can be equivalently replaced by the following linear constraints:(32)∑m=1MCya,m=Da0·∑m=1MCSa,m+Da1·la-Dar∀a∈L1(33)la·Ca1≤Camax-Ca0·∑m=1MCSa,m∀a∈L1(34)Dar≤Damax·∑m=1MCSa,m∀a∈L1.We briefly prove the equivalence by examining both the selected and unselected projects. If the potential expansion project on linka∈L1 is not selected, ∑m=1MCSa,m=0. Equations (14) and (33) imply that la=0. Equations (16) and (34) imply that Dar=0. Consequently, (32) implies that ∑m=1MCya,m=0=Dae-Dar·∑m=1MCSa,m, which is identical to (30). If the potential expansion project on link a∈L1 is selected, ∑m=1MCSa,m=1. Equation (33) is reduced to (7), and (34) is reduced to (15). Equations (13) and (32) imply that ∑m=1MCya,m=Dae-Dar=Dae-Dar·∑m=1MCSa,m, which is identical to (30).Budget and Resource Constraints.We assume that the government allocates a certain amount of construction budget Bτ at the beginning of time interval τ. This time interval τ does not have to be the same as the predefined time interval m. We introduce a conversion factor β to express the ratio between τ and m. For example, if the unit of m is month, and the unit of τ is year, then β should be 12. In this study, we assume that the remaining budget in period τ is available for use in period τ+1. Similar assumptions have been employed in [4]. Apart from the budget limitation, we should also consider other resource limitations, for example, the limitation of construction personnel and the limited number of specialized construction equipment. For the sake of simplicity, we only consider the construction personnel limitation in this paper. We assume that all construction teams have the same construction capability, and each ongoing project requires one construction team. The total number of available construction teams is limited and denoted by Rmax. The budget and construction personnel constraints are then given as follows:(35)TC1+RB1=B1(36)TCτ+RBτ=RBτ-1+Bτ∀τ>1,τ∈1,2,…,MCβ(37)∑a∈L1ya,m≤Rmax∀m∈1,2,…,MC,where TCτ is the total construction cost generated in period τ and RBτ is the cumulative remaining budget in period τ. Equations (35) and (36) represent the budget constraints. MC/β converts the construction time to the same time unit as τ. If the government allocates the entire budget at the beginning of the planning horizon, the budget constraints will be reduced to (35). Equation (37) specifies that, for each time interval m∈1,2,…,MC, the total construction teams at work should not exceed the number of available teams.The total construction cost of a project consists of two components: basic costs to complete the project (e.g., equipment cost, material cost, and labor cost) and extra costs for overtime work. Based on the previous assumption that a construction team works a fixed number of hours per day under normal condition, we assume that, without overtime work, each construction time interval for the expansion project on linka∈L1 includes an identical and fixed basic cost, denoted as ca. ca includes all of the wages for workers and other costs (e.g., material costs, equipment costs) needed in a normal construction time interval. If the planner wants to shorten the duration of a project, workers may choose any period to work overtime as long as they meet the time limit requirement. To simplify our model, we assume the overtime cost to be placed in the starting time interval of any project (Figure 3). The example in Figure 3 corresponds to the example in Figures 1 and 2. The expansion project originally lasts for four months, and it is reduced to three months through overtime. Therefore, both the basic cost in the fourth construction interval and the additional wages attributable to overtime work are allocated to the first construction interval when applying overtime work.Figure 3
Illustration of construction costs for a project.The total construction cost in periodτ can be formulated as(38)TCτ=∑m=βτ-1+1βτ∑a∈L1ya,m·ca+∑a∈L1OCa,τ·1+θ1τ-1∀τ∈1,2,…,MCβ,where OCa,τ is the overtime cost for the project on link a in period τ. θ1 represents the inflation rate.(39)∑τ=1MC/βOCa,τ=λ·ca·1+μ·Dar+1-λ·ca·Dar∀a∈L1(40)OCa,τ≥0∀a∈L1,∀τ∈1,2,…,MCβ(41)OCa,τ≤∑m=βτ-1+1βτSa,m·Q∀a∈L1,∀τ∈1,2,…,MCβ,where λ denotes the percentage of the workers’ salary in the total construction cost, μ is the increased rate of overtime salary, and Q is a large constant value. The first term on the right-hand side of (39) represents the salary portion of the overtime cost, and the second term represents the remaining portion. Equations (39)–(41) ensure that the overtime cost for the expansion project on link a∈L1 is placed in the starting period.


## 4.3. Objective Function

As aforementioned, during the construction period, the system performance may deteriorate due to work zones or closure of lanes. Different decision makers may have different preferences when selecting road expansion projects. Some may focus more on future benefits of the projects, while others may focus more on reducing adverse impacts of the projects during construction. To provide a flexible model, the objective function is to minimize the weighted sum of the total travel time during construction period and the total travel time during benefit period. This can be stated as(42)NPV=α1∑τ=1MC/βTTτ1+θ2τ-1+α2∑τ=MC/β+1M/βTTτ1+θ2τ-1,where α1 and α2 are the weighting factors for the construction period and benefit period, respectively, TTτ is the total travel time occurring in period τ, θ2 is the discount rate, and 1+θ2τ-1 represents the discount factor for period τ. TTτ is given in(43)TTτ=∑m=βτ-1+1βτ∑a∈Lta,mva,m∀τ∈1,2,…,Mβ.


## 4.4. The Base Model

Based on the above notations, the time-dependent discrete network design problem considering construction impact and flexible duration can be formulated as the following mathematical programP1.P1minNPV=α1∑τ=1MC/β∑m=βτ-1+1βτ∑a∈Lta,mva,m1+θ2τ-1+α2∑τ=MC/β+1M/β∑m=βτ-1+1βτ∑a∈Lta,mva,m1+θ2τ-1s.t.vm∈VmF∀m∈1,2,…,MTime-dependent  definitional  constraints,  equations6,8,9;Traffic  assignment  constraints,  equations11;Design  constraints,  equations13,14,16–29,31–34;Budget  and  resource  constraints,  equations35–41.This formulation involves two integer variables (i.e.,la and Dar). As is generally known, it is much more difficult to solve optimization problems with integer variables, especially for large-scale networks. Hence, we introduce two sets of binary variables, pab1 and qab2, to replace la and Dar as follows:(44)la=∑b1=1B12b1-1pab1∀a∈L1(45)Dar=∑b2=1B22b2-1qab2∀a∈L1.According to (44), the number of newly built lanes la can take the value 0 to (2B1-1). For example, if we use three binary variables to represent la, that is, B1=3, then la=pa1+2pa2+4pa3, ranging from 0 to 7. Similarly, the reduced value of construction interval Dar can range from 0 to (2B2-1). Note that the binary variables can be written in the form of complementarity constraints so that the binary variable can be treated as continuous variables as follows:(46)0≤pab1≤1∀a∈L1pab11-pab1=0∀a∈L10≤qab1≤1∀a∈L1qab11-qab1=0∀a∈L1.Then,la and Dar in previous equations can be replaced by ∑b1=1B12(b1-1)pab1 and ∑b2=1B22(b2-1)qab2, respectively. Equations (6), (13), (32), (33), (34), and (39) are replaced by (47), (48), (49), (50), (51), and (52), respectively.(47)Ca,m=Ca0-ya,m·Car+za,m·∑b1=1B12b1-1pab1·Ca1∀a∈L,m∈1,2,…,M(48)Dae=Da0+Da1·∑b1=1B12b1-1pab1∀a∈L1(49)∑m=1MCya,m=Da0·∑m=1MCSa,m+Da1·∑b1=1B12b1-1pab1-∑b2=1B22b2-1qab2∀a∈L1(50)∑b1=1B12b1-1pab1·Ca1≤Camax-Ca0·∑m=1MCSa,m∀a∈L1(51)∑b2=1B22b2-1qab2≤Damax·∑m=1MCSa,m∀a∈L1(52)∑τ=1MC/βOCa,τ=λ·ca·1+μ·∑b2=1B22b2-1qab2+1-λ·ca·∑b2=1B22b2-1qab2∀a∈L1.We also use the following complementarity constraints to replace (17) so that the binary variables Sa,m, Ea,m, ya,m, and za,m can be treated as continuous variables:(53)0≤Sa,m≤1∀a∈L1,m∈1,2,…,MCSa,m1-Sa,m=0∀a∈L1,m∈1,2,…,MC0≤Ea,m≤1∀a∈L1,m∈1,2,…,MCEa,m1-Ea,m=0∀a∈L1,m∈1,2,…,MC0≤ya,m≤1∀a∈L1,m∈1,2,…,MCya,m1-ya,m=0∀a∈L1,m∈1,2,…,MC0≤za,m≤1∀a∈L1,m∈1,2,…,MC+1za,m1-za,m=0∀a∈L1,m∈1,2,…,MC+1.Based on the above discussions, the base model can be reformulated as follows:P2minNPV=α1∑τ=1MC/β∑m=βτ-1+1βτ∑a∈Lta,mva,m1+θ2τ-1+α2∑τ=MC/β+1M/β∑m=βτ-1+1βτ∑a∈Lta,mva,m1+θ2τ-1s.t.vm∈VmF∀m∈1,2,…,M46–53;Time-dependent  definitional  constraint,  equations8,9;Traffic  assignment  constraints,  equations11;Design  constraints,  equations18–29,31;Budget  and  resource  constraints,  equations35–38,40-41.


## 5. Solution Algorithm

P
2 is a mathematical program with complementarity constraints (MPCC). It is well known that MPCC problems are difficult to solve because the feasible region of an MPCC problem is not convex, and the Mangasarian-Fromovitz constraint qualification (MFCQ) fails to hold [53]. Several previous efforts have been undertaken to make the problem easier to solve (see [54, 55]). In this paper, we extend the active-set algorithm (ASA) proposed by Zhang et al. [35] to solve the MPCC problem. Figure 4 shows the fundamental concepts of our model and the conceptual solution procedure of the ASA.Figure 4
Framework of the T-DNDP model and ASA.Instead of solving an MPCC directly, the ASA solves two simpler problems sequentially. The first problem is a restricted version ofP2, in which the variables pab1, qab1, Sa,m, Ea,m, ya,m, and za,m have a set of predefined values. The initial set of values is only a feasible solution, not necessarily the best solution. Therefore, we need to make adjustments to find a better solution, which is realized through the second problem, a SUB problem. For each variable, that is, pab1, qab1,Sa,m,Ea,m,ya,m, or za,m, there are only two possible values: 0 and 1. We divide all components of each variable into two active sets, where one set stores the components with a value of 0 and the other set stores the components with a value of 1. Then, (46) and (53) can be replaced by the following equations:(54)pab1=0∀a,b1∈Ωp,0,b1∈B1(55)pab1=1∀a,b1∈Ωp,1,b1∈B1(56)qab2=0∀a,b2∈Ωq,0,b2∈B2(57)qab2=1∀a,b2∈Ωq,1,b2∈B2(58)Sa,m=0∀a,m∈ΩS,0(59)Sa,m=1∀a,m∈ΩS,1(60)Ea,m=0∀a,m∈ΩE,0(61)Ea,m=1∀a,m∈ΩE,1(62)ya,m=0∀a,m∈Ωy,0(63)ya,m=1∀a,m∈Ωy,1(64)za,m=0∀a,m∈Ωz,0(65)za,m=1∀a,m∈Ωz,1.The restricted version ofP2 can be formulated asP3minv,p,q,S,E,y,z,ρNPV=α1∑τ=1MC/βTTτ1+θ2τ-1+α2∑τ=MC/β+1M/βTTτ1+θ2τ-1s.t.vm∈VmF∀m∈1,2,…,M47–5254–65Time-dependent  definitional  constraint,  equations8,9;Traffic  assignment  constraints,  equations11;Design  constraints,  equations18–29,31;Budget  and  resource  constraints,  equations35–38,40-41.Letv-m denote the solution of the UE problem for time period m(m∈1,2,…,M) for a given feasible design p-,q-,S-,E-,y-,z-, and combine v-m into one vector denoted as v- (i.e., v-=v-1,v-2,…,v-m=M). According to Proposition 1.1 in a study conducted by Facchinei and Pang [56], there must exist a multiplier vector ρ- associated with (1) so that p-,q-,S-,E-,y-,z-,v-,ρ- is also optimal to P3. Therefore, instead of solving P3 directly, we can obtain the optimal solution for P3 by solving a set of corresponding UE problems. Let δab1 and γab1 denote the multipliers associated with (54) and (55), respectively, and let σa,m, ξa,m, χa,m, and ϱa,m denote the multipliers associated with (62), (63), (64), and (65), respectively. The feasible design and the active sets can then be improved based on the information obtained from these multipliers. For example, if δab1<0 for some specific (a,b1)∈Ωp,0, shifting the (a,b1) from Ωp,0 to Ωp,1 may reduce the objective function value. And if γab1>0 for some specific (a,b1)∈Ωp,1, it may be beneficial to shift the (a,b1) from Ωp,1 to Ωp,0. Similarly, the multipliers σa,m, ξa,m, χa,m, and ϱa,m provide information on updating Ωy,0, Ωy,1, Ωz,0, and Ωz,1, respectively. The switching process, however, may make the budget and crew constraints unsatisfactory. For this reason, the following SUB problem is used to complete the switching process as well as preventing problem P3 from becoming infeasible. SUBming,h,η∑a,b1∈Ωp,0Kb1δab1gab1+∑a,m∈Ωy,0σa,mha,m+∑a,m∈Ωz,0χa,mηa,m-∑a,b1∈Ωp,1Kb1γab1gab1-∑a,m∈Ωy,1ξa,mha,m-∑a,m∈Ωz,1ϱa,mηa,ms.t.Designconstraints,equations17–29,31,47–52;Budget  and  resource  constraints,  equations35–38,40-41,52;(66)pab1=gab1∀a,b1∈Ωp,0(67)pab1=1-gab1∀a,b1∈Ωp,1(68)ya,m=ha,m∀a,m∈Ωy,0(69)ya,m=1-ha,m∀a,m∈Ωy,1(70)za,m=ηa,m∀a,m∈Ωz,0(71)za,m=1-ηa,m∀a,m∈Ωz,1(72)∑b1=1B1gab1≤1∀a∈L1(73)gab1∈0,1∀a∈L1,b1∈B1(74)ha,m,ηa,m∈0,1∀a∈L1,m∈1,2,…,MCP(75)qab2∈0,1∀a∈L1,b2∈B2(76)∑a,b1∈Ωp,0Kb1δab1gab1+∑a,m∈Ωy,0σa,mha,m+∑a,m∈Ωz,0χa,mηa,m-∑a,b1∈Ωp,1Kb1γab1gab1-∑a,m∈Ωy,1ξa,mha,m-∑a,m∈Ωz,1ϱa,mηa,m>φ,where binary variables gab1, ha,m, and ηa,m are “switch” variables, indicating whether to move the corresponding design variable to the complementary set. Equation (72) ensures that only one digit of variable pab1 can be changed at a time to prevent too much fluctuation in iterations. Equation (76) gives a predetermined lower bound to the objective function value of the SUB problem. A vector of constant Kb1 is introduced to ensure that changes are always made to the smallest digit possible, because the multipliers generated by the CONOPT solver [57] are linear in magnitude with respect to its digit b1. Note that although we only introduce “switch” variables for variables pab1, ya,m, and za,m, due to the dependency relationships among pab1, qab1, Sa,m, Ea,m, ya,m, and za,m, variables qab1, Sa,m, and Ea,m will also be determined.The procedure to solve the T-DNDP is as follows.Step  0. Choose an initial feasible design (pab1, qab1, Sa,m, Ea,m, ya,m, and za,m) and solve the UE problem. Initialize sets Ωp,0, Ωp,1, Ωq,0, Ωq,1, ΩS,0, ΩS,1, ΩE,0, ΩE,1, Ωy,0, Ωy,1, Ωz,0, and Ωz,1.Step  1. Solve P3 and denote the optimal objective function value as TT. Obtain multipliers δab1, γab1, σa,m, ξa,m, χa,m, and ϱa,m.Step  2. Set φ=-∞ and let (p-ab1, q-ab1, S-a,m, E-a,m, y-a,m, and z-a,m) solve the SUB problem. Denote the optimal objective function value as φ-. If φ-=0, stop, as (p-ab1, q-ab1, S-a,m, E-a,m, y-a,m, and z-a,m) is the best solution found. Otherwise, go to Step 3.Step  3. Solve the UE problem with (p-ab1, q-ab1, S-a,m, E-a,m, y-a,m, and z-a,m). If the total travel time associated with the UE distribution is greater than TT, set φ=φ-+ε, where ε>0 is sufficiently small, and return to Step 2. Otherwise, use (p-ab1, q-ab1, S-a,m, E-a,m, y-a,m, and z-a,m) to update the current design (pab1, qab1, Sa,m, Ea,m, ya,m, and za,m) and sets Ωp,0, Ωp,1, Ωq,0, Ωq,1, ΩS,0, ΩS,1, ΩE,0, ΩE,1, Ωy,0, Ωy,1, Ωz,0, and Ωz,1. Return to Step 1.


## 6. Numerical Studies

In this section, two numerical examples are presented to demonstrate the proposed model and solution algorithm.


### 6.1. Example 1: Nguyen-Dupuis Network

To illustrate the usefulness and advantages of our model, we first solve it for the Nguyen-Dupuis network [58] with two different scenarios. As shown in Figure 5, the Nguyen-Dupuis network consists of 13 nodes, 19 links, and four O-D pairs. Table 1 reports the link characteristics of the network. The travel demand is given by [58]: q1→2=400 veh/h; q1→3=800 veh/h; q4→2=600 veh/h; q4→3=200 veh/h.Table 1
Link characteristics of the Nguyen-Dupuis network.
Link
Free flow travel timeta0 (min)
Initial capacityCa0
1-5
11.17
177
1-12
14.36
104
4-5
14.36
163
4-9
18.88
235
5-6
4.79
245
5-9
14.36
121
6-7
7.98
295
6-10
70.75
213
7-8
7.98
183
7-11
14.36
291
8-2
14.36
275
9-10
12.32
221
9-13
11.25
278
10-11
12.76
241
11-2
14.36
283
11-3
12.77
169
12-6
11.17
164
12-8
5.05
179
13-3
11.25
278Figure 5
Nguyen-Dupuis network.Scenario 1: Considering Construction Impacts during Project Selection.In this scenario, we show that our model can consider the construction impacts during the project selection process and thus provide better solutions than conventional methods (i.e., separately optimizing the selection and schedule of road expansion projects).In order to clearly illustrate the results without being distracted by other factors, this scenario does not consider overtime policy. Assume that there are six candidate road expansion projects on links (5, 9), (7, 11), (9, 10), (10, 11), (9, 13), and (13, 3). The parameters for the candidate projects are given in Table2. Other parameters are given as follows:(1)
Planning horizon: 20 years (the planning horizon is equally divided into 240 design periods, namely, 240 months); construction period: two years; benefit period: 18 years(2)
Weighting for construction periodα1=0.5; weighting for benefit period α2=0.5(3)
Budget:B1=20, B2=20(4)
Number of available crew teams:Rmax=2(5)
Inflation rateθ1=0.01; discount rate θ2=0.05(6)
Conversion factor:β=12Table 2
Parameters for candidate projects in the Nguyen-Dupuis network.
Candidate link
Initial capacityCa0
Lane capacityCa1
Maximum allowable capacityCamax
Number of closed laneska
Fixed construction duration (month)
Extra duration for adding one laneDa1
5-9
121
121
242
0
3
3
7-11
291
291
582
1
4
2
9-10
241
241
482
0
6
6
9-13
278
278
556
1
7
8
10-11
241
241
482
1
5
7
12-6
164
164
328
0
3
5
13-3
278
278
556
0
6
9The ASA solution procedure is implemented using GAMS [59] and CONOPT solver [57] on a Dell computer with a 3.4 GHz processor and 16.0 GB RAM. It takes 23 minutes and 48 seconds to solve the model. The project selection and scheduling results are shown in Figure 6. To show the benefits of our model, we separately optimize the selection and schedule of road expansion projects. Figure 7 presents the results with separate optimization, and Table 3 compares the system performance under the two different approaches. It can be observed that the joint optimization approach improves the overall system performance by 29.6%. Compared with the separate optimization approach, the joint optimization results have much better performance in the construction period and a little bit worse performance in the benefit period.Table 3
System performance comparison for Scenario1.
Net user cost in construction period
Net user cost in benefit period
Total weighted net user costNPV
Separate optimization
105952239
132304481
119128360
Joint optimization
24516051
143304748
83910400
Improvement
29.6%Figure 6
Selection and scheduling results with joint optimization for Scenario1.Figure 7
Selection and scheduling results with separate optimization for Scenario1.Through further comparing the selected projects in the two approaches, we have the following observations: first, when other conditions keep the same, the project on link (9, 13) will have the same benefit as the project on link (13, 3); second, when other conditions keep the same, the project on link (10, 11) will have slightly higher benefit than the project on link (9,10); third, the projects on links (13, 3) and (9, 10) will have no adverse construction impact because they do not require lane closures, while the projects on links (9, 13) and (10, 11) will have great adverse construction impacts because they both require lane closures. Based on these observations, the results of the joint and separate optimization approaches can be further analyzed. Due to the fact that the separate optimization approach only considers the benefits but neglects the construction impacts when selecting road expansion projects, the projects on links (9, 13) and (10, 11) are selected. Nevertheless, because the joint optimization approach can explicitly consider the potential construction impact during project selection and scheduling, the projects on links (13, 3) and (9, 10) that have better overall performance are selected. Therefore, the proposed joint optimization approach has the potential of providing better solutions for planners.Compared with the conventional planning approach that separately selects and schedules road expansion projects, the proposed time-dependent joint optimization approach can help planners choose the projects that not only have significant benefits after completion but also yield relatively less adverse impacts during construction. As shown in the above numerical experiment, this joint optimization approach is beneficial, especially when there are projects with similar potential benefits but quite different construction impacts.Scenario 2: Focusing More on Future Benefits.In Scenario 1, we consider a 20-year planning horizon with a two-year construction period and an 18-year benefit period and assume that the weightings for construction period and benefit period are the same (i.e., α1=α2=0.5). This assumption is preferred for planners who focus on the near-term overall performance of a transportation network. For planners who focus more on future benefits of road expansion projects, they can choose relatively higher weighting for the benefit period.In this scenario, the weighting factors are given byα1=0.2 and α2=0.8 and other parameters are the same as Scenario 1. Note that, with these weighting factors, it is approximately equivalent to considering a 72-year benefit period. The new results from our joint optimization model are shown in Figure 8. The selection and scheduling results of the separate optimization approach will not change. Table 4 compares the system performance under the two different approaches. It can be observed that the joint optimization approach improves the overall system performance by 12.0%. Compared with the separate optimization approach, the joint optimization results have the same performance in the benefit period but have better performance in the construction period. Compared with Scenario 1, this scenario selects the project on link (10, 11) instead of the project on link (9, 10) because the project on link (10, 11) will lead to better overall system performance. We should note that, because the system performance in the benefit period for the two results is the same, the separate optimization approach may obtain the same optimal solution as the joint optimization approach under the best-case situation. However, because the separate optimization approach cannot consider the construction impact during project selection, it has a high chance to obtain the less optimal solutions.Table 4
System performance comparison for Scenario2.
Net user cost in construction period
Net user cost in benefit period
Total weighted net user costNPV
Separate optimization
105952239
132304481
127034033
Joint optimization
29964650
132304481
111836515
Improvement
12.0%Figure 8
Selection and scheduling results with joint optimization for Scenario2.This scenario first shows the flexibility of our model in considering planners with different preferences. It also further demonstrates that the proposed time-dependent joint optimization approach can provide better solutions than a separate optimization approach because it considers construction impacts during project selection.


### 6.2. Example 2: Sioux Falls Network

To further demonstrate the real-world applicability of our model, we solve it for the transportation network of the city of Sioux Falls. Figure9 shows the network of Sioux Falls. The yellow lines represent the links with candidate projects. The network data are derived from a study conducted by Leblanc et al. [15], and the attributes of all 10 candidate projects are given in Table 5. Other parameters are given as follows:(1)
Planning horizon: 20 years (the planning horizon is equally divided into 240 design periods, namely, 240 months); construction period: two years; benefit period: 18 years(2)
Weighting for construction periodα1=0.5; weighting for benefit period α2=0.5(3)
Budget:B1=15, B2=20(4)
Number of available crew teams:Rmax=2(5)
Inflation rateθ1=0.01; discount rate θ2=0.05(6)
Conversion factor:β=12(7)
Percentage of the workers’ salary in the total construction cost:λ=0.1(8)
Overtime salary parameter:μ=0.5(9)
Normal costs per period without overtime work:ca=1Table 5
Parameters for candidate projects in the Sioux Falls network.
Link
Lane capacityCa1
Maximum allowable capacityCamax
Number of closed laneska
Maximum allowable shortened durationDamax
Fixed durationDa0
Extra duration for adding one laneDa1
(1, 2)
13.0
40
1
4
8
8
(9, 8)
3.0
12
1
2
3
3
(11, 10)
5.0
15
1
1
3
3
(12, 13)
13.0
50
1
2
4
4
(14, 15)
3.0
9
1
1
2
2
(15, 19)
8.0
32
1
1
2
2
(16, 18)
10.0
40
1
1
2
3
(18, 20)
12.0
36
1
2
4
4
(23, 22)
2.4
8
1
0
1
1
(24, 21)
2.4
8
1
0
1
1Figure 9
Network of Sioux Falls.The ASA solution procedure is implemented using GAMS [59] and CONOPT solver [57] on a Dell computer with a 3.4 GHz processor and 16.0 GB RAM. It takes 4 hours, 13 minutes, and 30 seconds to solve the model. The project selection and scheduling results are provided in Table 6. To make the scheduling results more readable, Figure 10 provides a graphical representation. We can observe that six projects are chosen, among which four are chosen to be shortened by overtime work. The construction duration of the project on link (9, 8) is shortened by two months, and for the other three projects on links (11, 10), (14, 15), and (16, 18), the construction duration is shortened by one month. Total construction costs generated in the first and second years are 14.526 and 14.132, respectively, which are within the budget. According to the scheduling results, no more than two projects are under construction simultaneously. Hence, the resource constraint is also met. Without any road expansion projects, the total weighted net user cost will be 5.662×1010. The selected road expansion projects will reduce the total weighted net use cost to 4.274×1010. The overall system performance within the planning horizon is improved by 24.5%.Table 6
Selection and scheduling results for Example2.
Stating time
Ending time
Newly added lanes
Reduced construction duration
(9, 8)
11
17
2
2
(11, 10)
1
5
1
1
(14, 15)
3
5
1
1
(16, 18)
17
20
1
1
(23, 22)
13
14
1
0
(24, 21)
15
16
1
0Figure 10
Illustration of the scheduling results for Example2.


## 6.1. Example 1: Nguyen-Dupuis Network

To illustrate the usefulness and advantages of our model, we first solve it for the Nguyen-Dupuis network [58] with two different scenarios. As shown in Figure 5, the Nguyen-Dupuis network consists of 13 nodes, 19 links, and four O-D pairs. Table 1 reports the link characteristics of the network. The travel demand is given by [58]: q1→2=400 veh/h; q1→3=800 veh/h; q4→2=600 veh/h; q4→3=200 veh/h.Table 1
Link characteristics of the Nguyen-Dupuis network.
Link
Free flow travel timeta0 (min)
Initial capacityCa0
1-5
11.17
177
1-12
14.36
104
4-5
14.36
163
4-9
18.88
235
5-6
4.79
245
5-9
14.36
121
6-7
7.98
295
6-10
70.75
213
7-8
7.98
183
7-11
14.36
291
8-2
14.36
275
9-10
12.32
221
9-13
11.25
278
10-11
12.76
241
11-2
14.36
283
11-3
12.77
169
12-6
11.17
164
12-8
5.05
179
13-3
11.25
278Figure 5
Nguyen-Dupuis network.Scenario 1: Considering Construction Impacts during Project Selection.In this scenario, we show that our model can consider the construction impacts during the project selection process and thus provide better solutions than conventional methods (i.e., separately optimizing the selection and schedule of road expansion projects).In order to clearly illustrate the results without being distracted by other factors, this scenario does not consider overtime policy. Assume that there are six candidate road expansion projects on links (5, 9), (7, 11), (9, 10), (10, 11), (9, 13), and (13, 3). The parameters for the candidate projects are given in Table2. Other parameters are given as follows:(1)
Planning horizon: 20 years (the planning horizon is equally divided into 240 design periods, namely, 240 months); construction period: two years; benefit period: 18 years(2)
Weighting for construction periodα1=0.5; weighting for benefit period α2=0.5(3)
Budget:B1=20, B2=20(4)
Number of available crew teams:Rmax=2(5)
Inflation rateθ1=0.01; discount rate θ2=0.05(6)
Conversion factor:β=12Table 2
Parameters for candidate projects in the Nguyen-Dupuis network.
Candidate link
Initial capacityCa0
Lane capacityCa1
Maximum allowable capacityCamax
Number of closed laneska
Fixed construction duration (month)
Extra duration for adding one laneDa1
5-9
121
121
242
0
3
3
7-11
291
291
582
1
4
2
9-10
241
241
482
0
6
6
9-13
278
278
556
1
7
8
10-11
241
241
482
1
5
7
12-6
164
164
328
0
3
5
13-3
278
278
556
0
6
9The ASA solution procedure is implemented using GAMS [59] and CONOPT solver [57] on a Dell computer with a 3.4 GHz processor and 16.0 GB RAM. It takes 23 minutes and 48 seconds to solve the model. The project selection and scheduling results are shown in Figure 6. To show the benefits of our model, we separately optimize the selection and schedule of road expansion projects. Figure 7 presents the results with separate optimization, and Table 3 compares the system performance under the two different approaches. It can be observed that the joint optimization approach improves the overall system performance by 29.6%. Compared with the separate optimization approach, the joint optimization results have much better performance in the construction period and a little bit worse performance in the benefit period.Table 3
System performance comparison for Scenario1.
Net user cost in construction period
Net user cost in benefit period
Total weighted net user costNPV
Separate optimization
105952239
132304481
119128360
Joint optimization
24516051
143304748
83910400
Improvement
29.6%Figure 6
Selection and scheduling results with joint optimization for Scenario1.Figure 7
Selection and scheduling results with separate optimization for Scenario1.Through further comparing the selected projects in the two approaches, we have the following observations: first, when other conditions keep the same, the project on link (9, 13) will have the same benefit as the project on link (13, 3); second, when other conditions keep the same, the project on link (10, 11) will have slightly higher benefit than the project on link (9,10); third, the projects on links (13, 3) and (9, 10) will have no adverse construction impact because they do not require lane closures, while the projects on links (9, 13) and (10, 11) will have great adverse construction impacts because they both require lane closures. Based on these observations, the results of the joint and separate optimization approaches can be further analyzed. Due to the fact that the separate optimization approach only considers the benefits but neglects the construction impacts when selecting road expansion projects, the projects on links (9, 13) and (10, 11) are selected. Nevertheless, because the joint optimization approach can explicitly consider the potential construction impact during project selection and scheduling, the projects on links (13, 3) and (9, 10) that have better overall performance are selected. Therefore, the proposed joint optimization approach has the potential of providing better solutions for planners.Compared with the conventional planning approach that separately selects and schedules road expansion projects, the proposed time-dependent joint optimization approach can help planners choose the projects that not only have significant benefits after completion but also yield relatively less adverse impacts during construction. As shown in the above numerical experiment, this joint optimization approach is beneficial, especially when there are projects with similar potential benefits but quite different construction impacts.Scenario 2: Focusing More on Future Benefits.In Scenario 1, we consider a 20-year planning horizon with a two-year construction period and an 18-year benefit period and assume that the weightings for construction period and benefit period are the same (i.e., α1=α2=0.5). This assumption is preferred for planners who focus on the near-term overall performance of a transportation network. For planners who focus more on future benefits of road expansion projects, they can choose relatively higher weighting for the benefit period.In this scenario, the weighting factors are given byα1=0.2 and α2=0.8 and other parameters are the same as Scenario 1. Note that, with these weighting factors, it is approximately equivalent to considering a 72-year benefit period. The new results from our joint optimization model are shown in Figure 8. The selection and scheduling results of the separate optimization approach will not change. Table 4 compares the system performance under the two different approaches. It can be observed that the joint optimization approach improves the overall system performance by 12.0%. Compared with the separate optimization approach, the joint optimization results have the same performance in the benefit period but have better performance in the construction period. Compared with Scenario 1, this scenario selects the project on link (10, 11) instead of the project on link (9, 10) because the project on link (10, 11) will lead to better overall system performance. We should note that, because the system performance in the benefit period for the two results is the same, the separate optimization approach may obtain the same optimal solution as the joint optimization approach under the best-case situation. However, because the separate optimization approach cannot consider the construction impact during project selection, it has a high chance to obtain the less optimal solutions.Table 4
System performance comparison for Scenario2.
Net user cost in construction period
Net user cost in benefit period
Total weighted net user costNPV
Separate optimization
105952239
132304481
127034033
Joint optimization
29964650
132304481
111836515
Improvement
12.0%Figure 8
Selection and scheduling results with joint optimization for Scenario2.This scenario first shows the flexibility of our model in considering planners with different preferences. It also further demonstrates that the proposed time-dependent joint optimization approach can provide better solutions than a separate optimization approach because it considers construction impacts during project selection.


## 6.2. Example 2: Sioux Falls Network

To further demonstrate the real-world applicability of our model, we solve it for the transportation network of the city of Sioux Falls. Figure9 shows the network of Sioux Falls. The yellow lines represent the links with candidate projects. The network data are derived from a study conducted by Leblanc et al. [15], and the attributes of all 10 candidate projects are given in Table 5. Other parameters are given as follows:(1)
Planning horizon: 20 years (the planning horizon is equally divided into 240 design periods, namely, 240 months); construction period: two years; benefit period: 18 years(2)
Weighting for construction periodα1=0.5; weighting for benefit period α2=0.5(3)
Budget:B1=15, B2=20(4)
Number of available crew teams:Rmax=2(5)
Inflation rateθ1=0.01; discount rate θ2=0.05(6)
Conversion factor:β=12(7)
Percentage of the workers’ salary in the total construction cost:λ=0.1(8)
Overtime salary parameter:μ=0.5(9)
Normal costs per period without overtime work:ca=1Table 5
Parameters for candidate projects in the Sioux Falls network.
Link
Lane capacityCa1
Maximum allowable capacityCamax
Number of closed laneska
Maximum allowable shortened durationDamax
Fixed durationDa0
Extra duration for adding one laneDa1
(1, 2)
13.0
40
1
4
8
8
(9, 8)
3.0
12
1
2
3
3
(11, 10)
5.0
15
1
1
3
3
(12, 13)
13.0
50
1
2
4
4
(14, 15)
3.0
9
1
1
2
2
(15, 19)
8.0
32
1
1
2
2
(16, 18)
10.0
40
1
1
2
3
(18, 20)
12.0
36
1
2
4
4
(23, 22)
2.4
8
1
0
1
1
(24, 21)
2.4
8
1
0
1
1Figure 9
Network of Sioux Falls.The ASA solution procedure is implemented using GAMS [59] and CONOPT solver [57] on a Dell computer with a 3.4 GHz processor and 16.0 GB RAM. It takes 4 hours, 13 minutes, and 30 seconds to solve the model. The project selection and scheduling results are provided in Table 6. To make the scheduling results more readable, Figure 10 provides a graphical representation. We can observe that six projects are chosen, among which four are chosen to be shortened by overtime work. The construction duration of the project on link (9, 8) is shortened by two months, and for the other three projects on links (11, 10), (14, 15), and (16, 18), the construction duration is shortened by one month. Total construction costs generated in the first and second years are 14.526 and 14.132, respectively, which are within the budget. According to the scheduling results, no more than two projects are under construction simultaneously. Hence, the resource constraint is also met. Without any road expansion projects, the total weighted net user cost will be 5.662×1010. The selected road expansion projects will reduce the total weighted net use cost to 4.274×1010. The overall system performance within the planning horizon is improved by 24.5%.Table 6
Selection and scheduling results for Example2.
Stating time
Ending time
Newly added lanes
Reduced construction duration
(9, 8)
11
17
2
2
(11, 10)
1
5
1
1
(14, 15)
3
5
1
1
(16, 18)
17
20
1
1
(23, 22)
13
14
1
0
(24, 21)
15
16
1
0Figure 10
Illustration of the scheduling results for Example2.


## 7. Concluding Remarks

The primary significance of the model developed in this paper is that it introduces time dimension into the traditional NDP to consider the impact of road construction work and applies overtime policy to further improve the design. The proposed model can solve the capacity expansion project selection and project scheduling problems simultaneously. The proposed T-DNDP model also allows for the addition of time-dependent resource constraints. We employ the active-set algorithm to solve this problem and test two numerical examples to demonstrate the effectiveness of the proposed model. The results show that the proposed T-DNDP model has the potential of providing better solutions than the conventional approach that separately optimizes the selection and scheduling of road expansion projects.A number of research extensions can be considered in the future. For instance, the objective function of the proposed T-DNDP formulation only takes into account total system travel time. In future studies, we plan to integrate multiple objectives that are often considered by decision makers.



---

*Source: 2738930-2018-01-15.xml*