# Time-Dependent Transportation Network Design considering Construction Impact.

1. IntroductionTransportation 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 maybe 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 abranch-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.sub.1]: set of links with a potential expansion project

[L.sub.2]: set of links without a potential expansion project

W: set of O-D pairs

Parameters

a: link a = (i, j) [member of] L

w: O-D pair w [member of] W

M: the total number of unit time intervals for the planning horizon

[M.sup.C]: the total number of unit time intervals for the construction time window

m: time interval m [member of] {1, 2, ..., M}

[d.sup.w.sub.m]: travel demand between O-D pair w [member of] W in time interval m [member of] {1, 2, ..., M}

[D.sup.0.sub.a]: fixed time cost for the expansion project on link a [member of] [L.sub.1]

[D.sup.1.sub.a]: variable time cost per additional lane for the expansion project on link a [member of] [L.sub.1]

[c.sub.a]: average cost per time interval during construction for the expansion project on link a [member of] [L.sub.1] without overtime work

Variables

[x.sup.w.sub.a,m]: traffic flow on link a for O-D pair w [member of] W in time interval m [member of] {1, 2, ..., M}

[v.sub.a,m]: aggregate traffic flow on link a [member of] L in time interval m [member of] {1, 2, ..., M}

[t.sub.a,m]: travel time of link a [member of] L in time interval m [member of] {1, 2, ..., M}

[C.sub.a,m]: capacity of link a [member of] L in time interval m [member of] {1, 2, ..., M}

[y.sub.a,m]: a binary variable, representing whether link a [member of] [L.sub.1] is under construction in time interval m [member of] {1, 2, ..., M}. If yes, [y.sub.a,m] = 1; otherwise, [y.sub.a,m] = 0

[z.sub.a,m]: a binary variable, representing whether construction has been finished on link a [member of] [L.sub.1] in time interval m [member of] {1, 2, ..., M}. If yes, [z.sub.a,m] = 1; otherwise, [z.sub.a,m] = 0

[S.sub.a,m]: a binary variable, representing whether time interval m [member of] {1, 2, ..., M} is the start date of construction on link a [member of] [L.sub.1]. If yes, [S.sub.a,m] = 1; otherwise, [S.sub.a,m] = 0

[E.sub.a,m]: a binary variable, representing whether time interval m [member of] {1, 2, ..., M} is the end date of construction on link a [member of] [L.sub.1]. If yes, [E.sub.a,m] = 1; otherwise, [E.sub.a,m] = 0

[l.sub.a]: number of newly added lanes on link

[D.sup.e.sub.a]: the estimated construction duration for the expansion project on link a [member of] [L.sub.1] without overtime work

[D.sup.r.sub.a]: reduced construction duration for the expansion project on link a [member of] [L.sub.1] through overtime work.

4. Problem Formulation

Consider a general transportation network G(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 [member of] N and i [not equal to] 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 [L.sub.1] and [L.sub.2], 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 [M.sup.C] denote the number of intervals in the construction time window, [M.sup.C] < M.

Figure 1 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).

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 [E.sup.w] be an "input-output" vector indicating the origin and destination of O-D pair w. [E.sup.w] 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, [E.sup.w] equals 0. The flow distributions are said to be feasible if and only if the following constraints hold for [x.sup.w.sub.m]:

[mathematical expression not reproducible] (1)

[x.sup.w.sub.m] [greater than or equal to] 0 [for all]w [member of] W, m [member of] {1, 2, ..., M} (2)

[v.sub.m] = [summation over (w)][x.sup.w.sub.m] [for all]m {1, 2, ..., M}, (3)

where [x.sup.w.sub.m] [member of] [R.sup.[absolute value of L]] is a vector whose components, [x.sup.w.sub.a,m], represent a link flow on link a for O-D pair w in interval m, and [v.sub.m] is a vector whose components, [v.sub.a,m], represent an aggregate link flow on link a in interval m. [d.sup.w.sub.m] 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 [member of] W, given the travel demand in the first interval, that is, [d.sup.w.sub.1], the demand in interval m [member of] {1, 2, ..., M} is calculated as

[mathematical expression not reproducible], (4)

where [[epsilon].sup.w] is the growth factor of demand between O-D pair w.

To make the subsequent expressions more easily discernable, we introduce a set [V.sup.F.sub.m] for each period m to cover all of the feasible flow distributions:

[mathematical expression not reproducible]. (5)

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, [y.sub.a,m] and [z.sub.a,m], are introduced to indicate the status of a link a [member of] [L.sub.1] with a potential widening project in time interval m [member of] {1, 2, ..., M}. [y.sub.a,m] represents whether link a [member of] [L.sub.1] is under construction in time interval m [member of] {1, 2, ..., M}. If yes, [y.sub.a,m] = 1; otherwise, [y.sub.a,m] = 0. [z.sub.a,m] represents whether construction has been finished on link a [member of] [L.sub.1] in time interval m [member of] {1, 2, ..., M}. If yes, [z.sub.a,m] = 1; otherwise, [z.sub.a,m] = 0. Note that if link a [member of] [L.sub.1] is not selected for expansion, there will be no construction process on link a, and [y.sub.a,m] = 0, [z.sub.a,m] = 0, [for all]m [member of] {1, 2, ..., M}. The time-dependent capacity function can be formulated in (6)-(8):

[mathematical expression not reproducible] (6)

[C.sub.a,m] [less than or equal to] [C.sup.max.sub.a] [for all]a [member of] {1, 2, ..., M} (7)

[C.sub.a,m] = [C.sup.0.sub.a] [for all]a [member of] [L.sub.2], m [member of] {1, 2, ..., M}, (8)

where [C.sup.0.sub.a], [C.sup.r.sub.a], [C.sup.1.sub.a], and [C.sup.max.sub.a] are the initial capacity, the reduced capacity during construction, the capacity of a single lane, and the maximum allowable capacity of link a, respectively. [l.sub.a] denotes the number of lanes added after construction, which is a decision variable to be optimized in our model. [l.sub.a] 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, [t.sub.a,m], is determined by the link travel flow, [v.sub.a,m], and the link capacity, [C.sub.a,m].

[mathematical expression not reproducible], (9)

where [t.sup.0.sub.a] is the free flow travel time on link a.

User Equilibrium Assignment. For each time interval m [member of] {1, 2, ..., M}, the user's route choice behavior is assumed to follow Wardrop's first principle [51], which is ensured by

[mathematical expression not reproducible] (10)

Definitional constraints (6), (8), (9).

The KKT conditions of this user equilibrium model are shown as follows:

[mathematical expression not reproducible], (11)

where the multipliers [[rho].sup.w.sub.i,m] and [[rho].sup.w.sub.j,m] 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 [D.sup.e.sub.a], can be expressed as a function of the number of newly added lanes [l.sub.a], given by

[D.sup.e.sub.a] = [f.sub.a] ([l.sub.a]). (12)

In this model, we assume that [D.sup.e.sub.a] is linearly related to [l.sub.a] for simplicity. Other functional forms can be adopted in our model framework without difficulty:

[D.sup.e.sub.a] = [D.sup.0.sub.a] + [D.sup.1.sub.a] x [l.sub.a] [for all]a [member of] [L.sub.1] (13)

[l.sub.a] [member of] Z [for all]a [member of] [L.sub.1], (14)

where [D.sup.0.sub.a] 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 [D.sup.1.sub.a] 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, [D.sup.r.sub.a], to denote the reduced component of the construction duration. The actual duration for the project on link a should then be [D.sup.e.sub.a] - [D.sup.r.sub.a]. Even though overtime work can speed up the process, project duration cannot be infinitely shortened. Let [D.sup.max.sub.a] denote the maximum allowable shortened duration for a project on link a.

[D.sup.r.sub.a] [less than or equal to] [D.sup.max.sub.a] [for all]a [member of] [L.sub.1]. (15)

[D.sup.r.sub.a] [member of] ZaNL[for all]a [member of] [L.sub.1]. (16)

Within the planning horizon, the construction process on link a [member of] [L.sub.1] should be a continuous period of unit intervals. To properly model the timeline of the construction process, we introduce two additional binary variables, [S.sub.a,m] and [E.sub.a,m]. [S.sub.a,m] = 1 implies that the construction process on link a starts at the beginning of interval m, and [S.sub.a,m] = 0 otherwise. [E.sub.a,m] = 1 implies that the construction process on link a ends by the end of interval m, and [E.sub.a,m] = 0 otherwise. Note that if a link a [member of] [L.sub.1] is not selected for expansion, there will be no construction process on link a, and [S.sub.a,m] = 0, [E.sub.a,m] = 0, [for all]m [member of] {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 [S.sub.a,m], [E.sub.a,m], [y.sub.a,m], and [z.sub.a,m] throughout the entire planning horizon.

Variables [S.sub.a,m], [E.sub.a,m], [y.sub.a,m], and [z.sub.a,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, [M.sup.C]]. Subsequently, the nonconstruction time window is [[M.sup.C] + 1, M]. This yields the following constraints:

[mathematical expression not reproducible] (17)

[mathematical expression not reproducible] (18)

[mathematical expression not reproducible] (19)

Equation (17) requires variables [S.sub.a,m], [E.sub.a,m], [y.sub.a,m], and [z.sub.a,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 [member of] [L.sub.1] will not change in the nonconstruction time window.

The logical relationship between [S.sub.a,m] and [y.sub.a,m] can then be given by the following conditional constraints:

[S.sub.a,m] [less than or equal to] [y.sub.a,m] [for all]a [member of] [L.sub.1], m [member of] {1, 2, ..., [M.sup.C]} (20)

[S.sub.a,m] [less than or equal to] 1 - [y.sub.a,m-1] [for all]a [member of] [L.sub.1], m [member of] {2, 3, ..., [M.sup.C]} (21)

[S.sub.a,m] [greater than or equal to] [y.sub.a,m] - [y.sub.a,m-1] [for all]a [member of] [L.sub.1], m [member of] {2, 3, ..., [M.sup.C]} (22)

Equation (20) ensures that if the project on link a starts at time interval m, that is, [S.sub.a,m] = 1, this project must be under construction at interval m: that is, [y.sub.a,m] = 1. Equation (21) guarantees that if link a is under construction at time interval m - 1, that is, [y.sub.a,m-1] = 1, it cannot start at time interval m: that is, [S.sub.a,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, [y.sub.a,m] = 1 [y.sub.a,m-1] = 0, then interval m must be the starting time of the project: that is, [S.sub.a,m] = 1. These three equations cover all possible relationships between [S.sub.a,m] and [y.sub.a,m].

Similarly, the relationships between [E.sub.a,m] and [y.sub.a,m] are specified by the following constraints:

[E.sub.a,m] [less than or equal to] [y.sub.a,m] [for all]a [member of] [L.sub.1], m [member of] {1, 2, ..., [M.sup.C]} (23)

[E.sub.a,m] [less than or equal to] 1 - [y.sub.a,m+1] [for all]a [member of] [L.sub.1], m [member of] {1, 2, ..., [M.sup.C] - 1} (24)

[E.sub.a,m] [greater than or equal to] [y.sub.a,m] - [y.sub.a,m+1] [for all]a [member of] [L.sub.1], m [member of] {1, 2, ..., [M.sup.C] - 1}. (25)

Equation (23) means that if the project on link a is to end at time interval m, that is, [E.sub.a,m] = 1, this project must be under construction at interval m: that is, [y.sub.a,m] = 1. Equation (24) ensures that if the project on link a is to end at time interval m, that is, [E.sub.a,m] = 1, this project cannot be under construction at time interval m +1: that is, [y.sub.a,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, [y.sub.a,m] = 1, [y.sub.a,m+1] = 0, then interval m must be the ending time of the project; that is, [E.sub.a,m] = 1.

Likewise, the logical relationships between [E.sub.a,m] and [z.sub.a,m] are given as follows:

[E.sub.a,m] [less than or equal to] [z.sub.a,m+1] [for all]a [member of] [L.sub.1], m [member of] {1, 2, ..., [M.sup.C]} (26)

[E.sub.a,m] [less than or equal to] 1 - [z.sub.a,m] [for all]a [member of] [L.sub.1], m [member of] {1, 2, ..., [M.sup.C]} (27)

[E.sub.a,m] [greater than or equal to] [z.sub.a,m+1] - [z.sub.a,m] [for all]a [member of] [L.sub.1], m [member of] {1, 2, ..., [M.sup.C]}. (28)

Equation (26) ensures that if time interval m is the ending time of the project on link a, that is, [E.sub.a,m] = 1, then in the next interval m +1, the project must have been finished: that is, [z.sub.a,m+1] = 1. Equation (27) indicates that if in time interval m the project on link a has already been finished, that is, [z.sub.a,m] = 1, then time interval m cannot be the ending time: that is, [E.sub.a,m] = 0. Equation (28) ensures that if in time interval m + 1 the project on link a [member of] [L.sub.1] has already been finished, that is, [z.sub.a,m+1] = 1, but in interval m the project has not been finished, that is, [z.sub.a,m] = 0, then interval m must be the ending time of the project: that is, [E.sub.a,m] = 1.

Moreover, [S.sub.a,m] and [E.sub.a,m] should satisfy the following constraints:

[mathematical expression not reproducible]. (29)

Equations (29) ensure that the potential expansion project on link a [member of] [L.sub.1] 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:

[mathematical expression not reproducible] (30)

[mathematical expression not reproducible]. (31)

The value of [mathematical expression not reproducible] can represent whether the potential expansion project on link a [member of] [L.sub.1] is selected. If the project is selected, [mathematical expression not reproducible], and [mathematical expression not reproducible] otherwise. Therefore, (30) guarantees that if the potential expansion project on link a [member of] [L.sub.1] is selected, that is, [mathematical expression not reproducible], 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 [member of] [L.sub.1] is selected, that is, [mathematical expression not reproducible], the total duration of the construction period and benefit period is equal to the planning horizon, subtracting the duration before construction. Note that [mathematical expression not reproducible] can represent the duration before construction if the potential expansion project on link a [member of] [L.sub.1] is selected.

These above constraints, that is, (13)-(31), ensure that if the potential expansion project on link a [member of] [L.sub.1] 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:

[mathematical expression not reproducible] (32)

[mathematical expression not reproducible] (33)

[mathematical expression not reproducible]. (34)

We briefly prove the equivalence by examining both the selected and unselected projects. If the potential expansion project on link a [member of] [L.sub.1] is not selected, [mathematical expression not reproducible]. Equations (14) and (33) imply that [l.sub.a] = 0. Equations (16) and (34) imply that [D.sup.r.sub.a] = 0. Consequently, (32) implies that [mathematical expression not reproducible], which is identical to (30). If the potential expansion project on link a [member of] [L.sub.1] is selected, [mathematical expression not reproducible]. Equation (33) is reduced to (7), and (34) is reduced to (15). Equations (13) and (32) imply that [mathematical expression not reproducible], which is identical to (30).

Budget and Resource Constraints. We assume that the government allocates a certain amount of construction budget [B.sub.[tau]] at the beginning of time interval [tau]. This time interval [tau] does not have to be the same as the predefined time interval m. We introduce a conversion factor [beta] to express the ratio between [tau] and m. For example, if the unit of m is month, and the unit of [tau] is year, then [beta] should be 12. In this study, we assume that the remaining budget in period [tau] is available for use in period [tau] + 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 [R.sup.max]. The budget and construction personnel constraints are then given as follows:

[TC.sub.1] + [RB.sub.1] = [B.sub.1] (35)

[mathematical expression not reproducible] (36)

[mathematical expression not reproducible] (37)

where [TC.sub.[tau]] is the total construction cost generated in period [tau] and [RB.sub.[tau]] is the cumulative remaining budget in period [tau]. Equations (35) and (36) represent the budget constraints. [M.sup.C]/[beta] converts the construction time to the same time unit as [tau]. 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 [member of] {1, 2, ..., [M.sup.C]}, 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 link a [member of] [L.sub.1] includes an identical and fixed basic cost, denoted as [c.sub.a]. [c.sub.a] 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.

The total construction cost in period [tau] can be formulated as

[mathematical expression not reproducible], (38)

where [Oc.sub.a,[tau]] is the overtime cost for the project on link a in period [tau]. [[theta].sub.1] represents the inflation rate.

[mathematical expression not reproducible] (39)

[mathematical expression not reproducible] (40)

[mathematical expression not reproducible], (41)

where [lambda] denotes the percentage of the workers' salary in the total construction cost, [mu] 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 [member of] [L.sub.1] 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

[mathematical expression not reproducible], (42)

where [[alpha].sub.1] and [[alpha].sub.2] are the weighting factors for the construction period and benefit period, respectively, [TT.sub.[tau]] is the total travel time occurring in period [tau], [[theta].sub.2] is the discount rate, and [(1 + [[theta].sub.2]).sup.[tau]-1] represents the discount factor for period [tau]. [TT.sub.[tau]] is given in

[mathematical expression not reproducible]. (43)

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 program (P1).

[mathematical expression not reproducible]

Time-dependent definitional constraints, equations (6), (8), (9); Traffic assignment constraints, equations (11); Design constraints, equations (13), (14), (16) - (29), (31) - (34); Budget and resource constraints, equations (35) - (41). (P1)

This formulation involves two integer variables (i.e., [l.sub.a] and [D.sup.r.sub.a]). 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, [p.sup.b1.sub.a] and [p.sup.b2.sub.a], to replace [l.sub.a] and [D.sup.r.sub.a] as follows:

[mathematical expression not reproducible] (44)

[mathematical expression not reproducible]. (45)

According to (44), the number of newly built lanes [l.sub.a] can take the value 0 to ([2.sup.B1] - 1). For example, if we use three binary variables to represent [l.sub.a], that is, B1 = 3, then [l.sub.a] = [p.sup.1.sub.a] + 2[p.sup.2.sub.a] + 4[p.sup.3.sub.a], ranging from 0 to 7. Similarly, the reduced value of construction interval [D.sup.r.sub.a] can range from 0 to ([2.sup.B2] - 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:

[mathematical expression not reproducible]. (46)

Then, [l.sub.a] and [D.sup.r.sub.a] in previous equations can be replaced by [[summation].sup.B1.sub.b1=1] [2.sup.(b1-1)] [p.sup.b1.sub.a] and [[summation].sup.B2.sub.b2=1] [2.sup.(b2-1)] [p.sup.b2.sub.a], respectively. Equations (6), (13), (32), (33), (34), and (39) are replaced by (47), (48), (49), (50), (51), and (52), respectively.

[mathematical expression not reproducible] (47)

[mathematical expression not reproducible] (48)

[mathematical expression not reproducible] (49)

[mathematical expression not reproducible] (50)

[mathematical expression not reproducible] (51)

[mathematical expression not reproducible]. (52)

We also use the following complementarity constraints to replace (17) so that the binary variables [S.sub.a,m], [E.sub.a,m], [y.sub.a,m], and [z.sub.a,m] can be treated as continuous variables:

[mathematical expression not reproducible]. (53)

Based on the above discussions, the base model can be reformulated as follows:

[mathematical expression not reproducible]; (P2)

Time-dependent definitional constraint, equations (8), (9); Traffic assignment constraints, equations (11); Design constraints, equations (18) - (29), (31); Budget and resource constraints, equations (35) - (38), (40) - (41).

5. Solution Algorithm

(P2) 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.

Instead of solving an MPCC directly, the ASA solves two simpler problems sequentially. The first problem is a restricted version of (P2), in which the variables [p.sup.b1.sub.a], [q.sup.b1.sub.a], [S.sub.a,m], [E.sub.a,m], [y.sub.a,m], and [z.sub.a,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, [p.sup.b1.sub.a], [q.sup.b1.sub.a], [S.sub.a,m], [E.sub.a,m], [y.sub.a,m] or [z.sub.a,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:

[p.sup.b1.sub.a] = 0 [for all] (a, b1) [member of] [[OMEGA].sub.p,0], b1 [member of] B1 (54)

[p.sup.b1.sub.a] = 1 [for all] (a, b1) [member of] [[OMEGA].sub.p,1], b1 [member of] B1 (55)

[q.sup.b2.sub.a] = 0 [for all] (a, b2) [member of] [[OMEGA].sub.q,0], b2 [member of] B2 (56)

[q.sup.b2.sub.a] = 1 [for all] (a, b2) [member of] [[OMEGA].sub.q,1], b2 [member of] B2 (57)

[S.sub.a,m] = 0 [for all](a, m) [member of] [[OMEGA].sub.S,0] (58)

[S.sub.a,m] = 1 [for all](a, m) [member of] [[OMEGA].sub.S,1] (59)

[E.sub.a,m] = 0 [for all](a, m) [member of] [[OMEGA].sub.E,0] (60)

[E.sub.a,m] = 1 [for all](a, m) [member of] [[OMEGA].sub.E,1] (61)

[y.sub.a,m] = 0 [for all](a, m) [member of] [[OMEGA].sub.y,0] (62)

[y.sub.a,m] = 1 [for all](a, m) [member of] [[OMEGA].sub.y,1] (63)

[z.sub.a,m] = 0 [for all](a, m) [member of] [[OMEGA].sub.z,0] (64)

[z.sub.a,m] = 1 [for all](a, m) [member of] [[OMEGA].sub.z,1] (65)

The restricted version of (P2) can be formulated as

[mathematical expression not reproducible]

(47)-(52)

(54)-(65)

Time-dependent definitional constraint, equations (8), (9);

Traffic assignment constraints, equations (11);

Design constraints, equations (18)-(29), (31);

Budget and resource constraints, equations (35)-(38), (40)-(41). (P3)

Let [[bar.v].sub.m] denote the solution of the UE problem for time period m (m [member of] {1, 2, ..., M}) for a given feasible design ([bar.p], [bar.q], [bar.S], [bar.E] [bar.y], [bar.z]), and combine [[bar.v].sub.m] into one vector denoted as [bar.v] (i.e., [bar.v] = {[[bar.v].sub.1], [[bar.v].sub.2], ..., [[bar.v].sub.m=M]}). According to Proposition 1.1 in a study conducted by Facchinei and Pang [56], there must exist a multiplier vector [bar.[rho]] associated with (1) so that ([bar.p], [bar.q], [bar.S], [bar.E], [bar.y], [bar.z], [bar.v], [bar.[rho]]) 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 [[delta].sup.b1.sub.a] and [[gamma].sup.b1.sub.a] denote the multipliers associated with (54) and (55), respectively, and let [[sigma].sub.a,m], [[xi].sub.a,m], [[chi].sub.a,m], and [[??].sub.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 [[delta].sup.b1.sub.a] < 0 for some specific (a, b1) [member of] [[OMEGA].sub.p,0], shifting the (a, b1) from [[OMEGA].sub.p,0] to [[OMEGA].sub.p,1] may reduce the objective function value. And if [[gamma].sup.b1.sub.a] > 0 for some specific (a, b1) [member of] [[OMEGA].sub.p,1], it maybe beneficial to shift the (a, b1) from [[OMEGA].sub.p,1] to [[OMEGA].sub.p,0]. Similarly, the multipliers [[sigma].sub.a,m], [[xi].sub.a,m], [[chi].sub.a,m], and [[??].sub.a,m] provide information on updating [[OMEGA].sub.y,0], [[OMEGA].sub.y,1], [[OMEGA].sub.z,0], and [[OMEGA].sub.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.

[mathematical expression not reproducible] (SUB)

s.t. Design constraints, equations (17) - (29), (31), (47) - (52); Budget and resource constraints, equations (35) - (38), (40) - (41), (52);

[p.sup.b1.sub.a] = [q.sup.b1.sub.a] [for all] (a, b1) [member of] [[OMEGA].sub.p,0] (66)

[p.sup.b1.sub.a] = [q.sup.b1.sub.a] [for all] (a, b1) [member of] [[OMEGA].sub.p,0] (66)

[p.sup.b1.sub.a] = 1 - [q.sup.b1.sub.a] [for all] (a, b1) [member of] [[OMEGA].sub.p,1] (67)

[y.sub.a,m] = [h.sub.a,m] [for all] (a, m) [member of] [[OMEGA].sub.y,0] (68)

[y.sub.a,m] = 1 - [h.sub.a,m] [for all] (a, m) [member of] [[OMEGA].sub.y,1] (69)

[z.sub.a,m] = [[eta].sub.a,m] [for all] (a, m) [member of] [[OMEGA].sub.z,0] (70)

[z.sub.a,m] = 1 - [[eta].sub.a,m] [for all] (a, m) [member of] [[OMEGA].sub.z,1] (71)

[B1.summation over (b1=1)] [g.sup.b1.sub.a] [less than or equal to] 1 [for all]a [member of] [L.sub.1] (72)

[g.sup.b1.sub.a] [member of] {0, 1} [for all]a [member of] [L.sub.1], b1 [member of] B1 (73)

[h.sub.a,m], [[eta].sub.a,m] [member of] {0, 1} [for all]a [member of] [L.sub.1], m [member of] {1, 2, ..., [M.sup.CP]} (74)

[q.sup.b2.sub.a] [member of] {0, 1} [for all]a [member of] [L.sub.1], b2 [member of] B2 (75)

[mathematical expression not reproducible], (76)

where binary variables [g.sup.b1.sub.a], [h.sub.a,m], and [[eta].sub.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 [p.sup.b1.sub.a] 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 [K.sup.b1] 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 [p.sup.b1.sub.a], [y.sub.a,m], and [z.sub.a,m], due to the dependency relationships among [p.sup.b1.sub.a], [q.sup.b1.sub.a], [S.sub.a,m], [E.sub.a,m], [y.sub.a,m], and [z.sub.a,m], variables [q.sup.b1.sub.a], [S.sub.a,m], and [E.sub.a,m] will also be determined.

The procedure to solve the T-DNDP is as follows.

Step 0. Choose an initial feasible design ([p.sup.b1.sub.a], [q.sup.b1.sub.a], [S.sub.a,m], [E.sub.a,m], [y.sub.a,m], and [z.sub.a,m]) and solve the UE problem. Initialize sets [mathematical expression not reproducible].

Step 1. Solve (P3) and denote the optimal objective function value as TT. Obtain multipliers [mathematical expression not reproducible].

Step 2 Set [phi] = -[infinity] and let ([mathematical expression not reproducible]) solve the (SUB) problem. Denote the optimal objective function value as [bar.[phi]]. If [bar.[phi]] = 0, stop, as ([mathematical expression not reproducible]) is the best solution found. Otherwise, go to Step 3.

Step 3. Solve the UE problem with ([mathematical expression not reproducible]). If the total travel time associated with the UE distribution is greater than TT, set [phi] = [bar.[phi]] + [epsilon], where [epsilon] > 0 is sufficiently small, and return to Step 2. Otherwise, use ([mathematical expression not reproducible]) to update the current design ([mathematical expression not reproducible]) and sets [mathematical expression not reproducible]. 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]: [q.sub.1[right] arrow]2] = 400 veh/h; [q.sub.1[right] arrow]3] = 800 veh/ h; [q.sub.4[right] arrow]2] = 600 veh/h; [q.sub.4[right] arrow]3] = 200 veh/h.

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 Table 2. 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 [[alpha].sub.1] = 0.5; weighting for benefit period [[alpha].sub.2] = 0.5

(3) Budget: [B.sub.1] = 20, [B.sub.2] = 20

(4) Number of available crew teams: [R.sup.max] = 2

(5) Inflation rate [[theta].sub.1] = 0.01; discount rate [[theta].sub.2] = 0.05

(6) Conversion factor: [beta] = 12

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 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.

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., [[alpha].sub.1] = [[alpha].sub.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 [[alpha].sub.1] = 0.2 and [[alpha].sub.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.

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. Figure 9 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 [[alpha].sub.1] = 0.5; weighting for benefit period [[alpha].sub.2] = 0.5

(3) Budget: [B.sub.1] = 15, [B.sub.2] = 20

(4) Number of available crew teams: [R.sup.max] = 2

(5) Inflation rate [[theta].sub.1] = 0.01; discount rate [[theta].sub.2] = 0.05

(6) Conversion factor: [beta] = 12

(7) Percentage of the workers' salary in the total construction cost: [lambda] = 0.1

(8) Overtime salary parameter: [mu] = 0.5

(9) Normal costs per period without overtime work: [c.sub.a] = 1

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 x [10.sup.10]. The selected road expansion projects will reduce the total weighted net use cost to 4.274 x [10.sup.10]. The overall system performance within the planning horizon is improved by 24.5%.

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.

https://doi.org/10.1155/2018/2738930

Disclosure

The views expressed are those of the authors and do not reflect the official policy or position of the project's sponsors. Part of this study has been presented as a poster at the Transportation Research Board (tRb) 97th Annual Meeting.

Conflicts of Interest

The authors declare that there are no conflicts of interest regarding the publication of this paper.

Acknowledgments

The study was partially sponsored by Mountain-Plains Consortium, a Regional University Transportation Center sponsored by the U.S. Department of Transportation, the National Natural Science Foundation of China under Projects 71401025 and 51338008, and Lloyd's Register Foundation that helps to protect life and property by supporting engineering-related education, public engagement, and the application of research.

References

[1] D. Schrank, B. Eisele, T. Lomax, and J. Bak, Urban mobility scorecard, 2015.

[2] T. L. Friesz, D. Bernstein, N. J. Mehta, R. L. Tobin, and S. Ganjalizadeh, "Day-to-day dynamic network disequilibria and idealized traveler information systems," Operations Research, vol. 42, no. 6, pp. 1120-1136, 1994.

[3] T. L. Friesz, D. Bernstein, and R. Stough, "Dynamic systems, variational inequalities and control theoretic models for predicting time-varying urban network flows," Transportation Science, vol. 30, no. 1, pp. 14-31, 1996.

[4] H. K. Lo and W. Y. Szeto, "Planning transport network improvements over time," Urban and Regional Transportation Modeling: Essays in Honor of David Boyce, pp. 157-176, 2004.

[5] M. Abdulaal and L. J. LeBlanc, "Continuous equilibrium network design models," Transportation Research Part B: Methodological, vol. 13, no. 1, pp. 19-32, 1979.

[6] G. B. Dantzig, R. P. Harvey, Z. F. Lansdowne, D. W. Robinson, and S. F. Maier, "Formulating and solving the network design problem by decomposition," Transportation Research Part B: Methodological, vol. 13, no. 1, pp. 5-17, 1979.

[7] H. Z. Aashtiani and T. L. Magnanti, "Equilibria on a congested transportation network," Society for Industrial and Applied Mathematics. Journal on Algebraic and Discrete Methods, vol. 2, no. 3, pp. 213-226, 1981.

[8] C. Suwansirikul, T. L. Friesz, and R. L. Tobin, "Equilibrium decomposed optimization: a heuristic for the continuous equilibrium network design problem," Transportation Science, vol. 21, no. 4, pp. 254-263, 1987.

[9] T. L. Friesz, H.-J. Cho, N. J. Mehta, R. L. Tobin, and G. Anandalingam, "Simulated annealing approach to the network design problem with variational inequality constraints," Transportation Science, vol. 26, no. 1, pp. 18-26, 1992.

[10] Q. Meng, H. Yang, and M. G. H. Bell, "An equivalent continuously differentiable model and a locally convergent algorithm for the continuous network design problem," Transportation Research PartB: Methodological, vol. 35, no. 1, pp. 83-105, 2001.

[11] Q. Meng and H. Yang, "Benefit distribution and equity in road network design," Transportation Research Part B: Methodological, vol. 36, no. 1, pp. 19-35, 2002.

[12] D. H. Lee, "Planning Transport Network Improvements over Time," in Urban and Regional Transportation Modeling: Essays in Honor of David Boyce, Edward Elgar Publishing, Inc., USA, 2004.

[13] Y. Yin and S. Lawphongpanich, "A robust approach to continuous network designs with demand uncertainty," Transportation and Traffic Theory, pp. 110-126, 2007.

[14] P. A. Steenbrink, "Transport network optimization in the Dutch integral transportation study," Transportation Research, vol. 8, no. 1, pp. 11-27, 1974.

[15] L. J. Leblanc, "An algorithm for the discrete network design problem," Transportation Science, vol. 9, no. 3, pp. 183-199,1975.

[16] M. Chen and A. S. Alfa, "A network design algorithm using a stochastic incremental traffic assignment approach," Transportation Science, vol. 25, no. 3, pp. 215-224, 1991.

[17] C. Lee and K. Yang, "Network design of one-way streets with simulated annealing," Papers in Regional Science, vol. 73, no. 2, pp. 119-134, 1994.

[18] Z. Drezner and G. O. Wesolowsky, "Selecting an optimum configuration of one-way and two-way routes," Transportation Science, vol. 31, no. 4, pp. 386-394, 1997

[19] Z. Drezner and G. O. Wesolowsky, "Network design: selection and design of links and facility location," Transportation Research Part A: Policy and Practice, vol. 37, no. 3, pp. 241-256, 2003.

[20] H. Poorzahedy and F. Abulghasemi, "Application of Ant System to network design problem," Transportation, vol. 32, no. 3, pp. 251-273, 2005.

[21] Z. Gao, J. Wu, and H. Sun, "Solution algorithm for the bi-level discrete network design problem," Transportation Research Part B: Methodological, vol. 39, no. 6, pp. 479-495, 2005.

[22] Q. Meng and H. L. Khoo, "Optimizing contraflow scheduling problem: Model and algorithm," Journal of Intelligent Transportation Systems: Technology, Planning, and Operations, vol. 12, no. 3, pp. 126-138, 2008.

[23] G. E. Cantarella, G. Pavone, and A. Vitetta, "Heuristics for urban road network design: lane layout and signal settings," European Journal of Operational Research, vol. 175, no. 3, pp. 1682-1695, 2006.

[24] G. E. Cantarella and A. Vitetta, "The multi-criteria road network design problem in an urban area," Transportation, vol. 33, no. 6, pp. 567-588, 2006.

[25] M. Gallo, L. D'Acierno, and B. Montella, "A meta-heuristic approach for solving the urban network design problem," European Journal of Operational Research, vol. 201, no. 1, pp. 144-157, 2010.

[26] P. Luathep, A. Sumalee, W. H. K. Lam, Z. Li, and H. K. Lo, "Global optimization method for mixed transportation network design problem: a mixed-integer linear programming approach," Transportation Research Part B: Methodological, vol. 45, no. 5, pp. 808-827, 2011.

[27] Z. X. Wu, W. H. K. Lam, and K. S. Chan, "Multi-model network design: Selection of pedestrianisation location," Journal of Eastern Asia Society for Transportation Studies, vol. 6, pp. 2275-2290, 2005.

[28] Z. Song, Y. Yin, and S. Lawphongpanich, "Optimal Deployment of Managed Lanes in General Networks," International Journal of Sustainable Transportation, vol. 9, no. 6, pp. 431-441, 2015.

[29] E. Miandoabchi and R. Z. Farahani, "Optimizing reserve capacity of urban road networks in a discrete Network Design Problem," Advances in Engineering Software, vol. 42, no. 12, pp. 1041-1050, 2011.

[30] H. Poorzahedy and M. A. Turnquist, "Approximate algorithms for the discrete network design problem," Transportation Research PartB: Methodological, vol. 16, no. 1, pp. 45-55, 1982.

[31] R. S. Solanki, J. K. Gorti, and F. Southworth, "Using decomposition in large-scale highway network design with a quasioptimization heuristic," Transportation Research Part B: Methodological, vol. 33, no. 2, pp. 127-140, 1998.

[32] H. Poorzahedy and O. M. Rouhani, "Hybrid meta-heuristic algorithms for solving network design problem," European Journal of Operational Research, vol. 182, no. 2, pp. 578-596, 2007.

[33] Y. Yin, "Genetic-algorithms-based approach for bilevel programming models," Journal of Transportation Engineering, vol. 126, no. 2, pp. 115-119, 2000.

[34] K. Jeon, J. S. Lee, S. Ukkusuri, and S. T. Waller, "Selectorecombinative genetic algorithm to relax computational complexity of discrete network design problem," Transportation Research Record, no. 1964, pp. 91-103, 2006.

[35] L. Zhang, S. Lawphongpanich, and Y. Yin, "An active-set algorithm for discrete network design problems," Transportation and Traffic Theory, pp. 283-300, 2009.

[36] H. Farvaresh and M. M. Sepehri, "A branch and bound algorithm for bi-level discrete network design problem," Networks and Spatial Economics, vol. 13, no. 1, pp. 67-106, 2013.

[37] T. L. Friesz and S. Shah, "An overview of nontraditional formulations of static and dynamic equilibrium network design," Transportation Research Part B: Methodological, vol. 35, no. 1, pp. 5-21, 2001.

[38] W. Y. Szeto and H. K. Lo, "Transportation network improvement and tolling strategies: the issue of intergeneration equity," Transportation Research Part A: Policy and Practice, vol. 40, no. 3, pp. 227-243, 2006.

[39] W. Y. Szeto and H. K. Lo, "Time-dependent transport network improvement and tolling strategies," Transportation Research Part A: Policy and Practice, vol. 42, no. 2, pp. 376-391, 2008.

[40] O. Liam and Y. W. Szeto, "The discrete network design problem over time," HKIE Transactions, vol. 14, no. 4, pp. 47-55, 2007.

[41] H. Lo and W. Y. Szeto, "Time-dependent transport network design: a study on budget sensitivity," Journal of the Eastern Asia Society for Transportation Studies, vol. 5, 2003.

[42] W. Y. Szeto and H. K. Lo, "Strategies for road network design over time: Robustness under uncertainty," Transportmetrica, vol. 1, no. 1, pp. 47-63, 2005.

[43] H. K. Lo and W. Y. Szeto, "Time-dependent transport network design under cost-recovery," Transportation Research Part B: Methodological, vol. 43, no. 1, pp. 142-158, 2009.

[44] W. Y. Szeto, X. Jaber, and M. O'Mahony, "Time-dependent discrete network design frameworks considering land use," Computer-Aided Civil and Infrastructure Engineering, vol. 25, no. 6, pp. 411-426, 2010.

[45] W. Y. Szeto, Y. Jiang, D. Z. Wang, and A. Sumalee, "A sustainable road network design problem with land use transportation interaction over time," Networks and Spatial Economics, vol. 15, no. 3, pp. 791-822, 2015.

[46] Y. Jiang and W. Y. Szeto, "Time-dependent transportation network design that considers health cost," Transportmetrica A: Transport Science, vol. 11, no. 1, pp. 74-101, 2015.

[47] E. Miandoabchi, F. Daneshzand, R. Zanjirani Farahani, and W. Y. Szeto, "Time-dependent discrete road network design with both tactical and strategic decisions," Journal of the Operational Research Society, vol. 66, no. 6, pp. 894-913, 2015.

[48] B. J. Kim, W. Kim, and B. H. Song, "Sequencing and scheduling highway network expansion using a discrete network design model," Annals of Regional Science, vol. 42, no. 3, pp. 621-642, 2008.

[49] S. V. Ukkusuri and G. Patil, "Multi-period transportation network design under demand uncertainty," Transportation Research PartB: Methodological, vol. 43, no. 6, pp. 625-642, 2009.

[50] S.-M. Hosseininasab and S.-N. Shetab-Boushehri, "Integration of selecting and scheduling urban road construction projects as a time-dependent discrete network design problem," European Journal of Operational Research, vol. 246, no. 3, pp. 762-771, 2015.

[51] J. Wardrop, "Some theoretical aspects of road traffic research," ICE Proceedings: Engineering Divisions, vol. 1, no. 3, pp. 325-362, 1952.

[52] R. K. Ahuja, T. L. Magnanti, and J. Orlin, Network Flows: Theory, Algorithms, and Applications, Prentice-Hall, 1993.

[53] H. Scheel and S. Scholtes, "Mathematical programs with complementarity constraints: stationarity, optimality, and sensitivity," Mathematics of Operations Research, vol. 25, no. 1, pp. 1-22, 2000.

[54] G. Bouza and G. Still, "Mathematical programs with complementarity constraints: convergence properties of a smoothing method," Mathematics of Operations Research, vol. 32, no. 2, pp. 467-483, 2007

[55] A. U. Raghunathan and L. T. Biegler, "An interior point method for mathematical programs with complementarity constraints (MPCCs)," SIAM Journal on Optimization, vol. 15, no. 3, pp. 720-750, 2005.

[56] F. Facchinei and J.-S. Pang, Finite-dimensional variational inequalities and complementarity problems. Vol. I, Springer Series in Operations Research, Springer-Verlag, NY, USA, 2003.

[57] A. S. Drud, "CONOPT--A Large-Scale GRG Code," ORSA Journal on Computing, vol. 6, no. 2, pp. 207-216, 1994.

[58] S. Nguyen and C. Dupuis, "An efficient method for computing traffic equilibria in networks with asymmetric transportation costs," Transportation Science, vol. 18, no. 2, pp. 185-202, 1984.

[59] R. E. Rosenthal, GAMS-A User's Guide, GAMS Development Corporation, Washington, DC, USA, 2012.

Yi He, (1) Ziqi Song (iD), (1) and Lihui Zhang (iD) (2)

(1) Department of Civil and Environmental Engineering, Utah State University, Logan, UT 84322, USA

(2) Institute of Transportation Engineering, Zhejiang University, Hangzhou, Zhejiang 310058, China

Correspondence should be addressed to Lihui Zhang; lihuizhang@zju.edu.cn

Received 21 August 2017; Revised 27 November 2017; Accepted 12 December 2017; Published 15 January 2018

Academic Editor: Martin Trepanier

Caption: Figure 1: An example of the timeline of a road expansion project.

Caption: Figure 2: An example to illustrate the values of [S.sub.a,m], [E.sub.a,m], [y.sub.a,m], and [z.sub.a,m] throughout the entire planning horizon.

Caption: Figure 3: Illustration of construction costs for a project.

Caption: Figure 4: Framework of the T-DNDP model and ASA.

Caption: Figure 5: Nguyen-Dupuis network.

Caption: Figure 6: Selection and scheduling results with joint optimization for Scenario 1.

Caption: Figure 7: Selection and scheduling results with separate optimization for Scenario 1.

Caption: Figure 8: Selection and scheduling results with joint optimization for Scenario 2.

Caption: Figure 9: Network of Sioux Falls.

Caption: Figure 10: Illustration of the scheduling results for Example 2.

Table 1: Link characteristics of the Nguyen-Dupuis network. Link Free flow Initial capacity travel time [C.sup.0.sub.a] [t.sup.0.sub.a] (min) 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 278 Table 2: Parameters for candidate projects in the Nguyen-Dupuis network. Candidate link Initial capacity Lane capacity [C.sup.0.sub.a] [C.sup.1.sub.a] 5-9 121 121 7-11 291 291 9-10 241 241 9-13 278 278 10-11 241 241 12-6 164 164 13-3 278 278 Candidate link Maximum allowable Number of closed capacity lanes [k.sub.a] [C.sup.max.sub.a] 5-9 242 0 7-11 582 1 9-10 482 0 9-13 556 1 10-11 482 1 12-6 328 0 13-3 556 0 Candidate link Fixed construction Extra duration for duration (month) adding one lane [D.sup.1.sub.a] 5-9 3 3 7-11 4 2 9-10 6 6 9-13 7 8 10-11 5 7 12-6 3 5 13-3 6 9 Table 3: System performance comparison for Scenario 1. Net user cost in Net user cost in construction period benefit period Separate optimization 105952239 132304481 Joint optimization 24516051 143304748 Improvement Total weighted net user cost NPV Separate optimization 119128360 Joint optimization 83910400 29.6% Table 4: System performance comparison for Scenario 2. Net user cost in Net user cost in construction period benefit period Separate optimization 105952239 132304481 Joint optimization 29964650 132304481 Improvement Total weighted net user cost NPV Separate optimization 127034033 Joint optimization 111836515 12.0% Table 5: Parameters for candidate projects in the Sioux Falls network. Link Lane capacity Maximum allowable Number of [C.sup.1.sub.a] capacity closed lanes [C.sup.max.sub.a] [k.sub.a] (1,2) 13.0 40 1 (9, 8) 3.0 12 1 (11, 10) 5.0 15 1 (12, 13) 13.0 50 1 (14, 15) 3.0 9 1 (15, 19) 8.0 32 1 (16, 18) 10.0 40 1 (18, 20) 12.0 36 1 (23, 22) 2.4 8 1 (24, 21) 2.4 8 1 Link Maximum allowable Fixed duration shortened duration [D.sup.0.sub.a] [D.sup.max.sub.a] (1,2) 4 8 (9, 8) 2 3 (11, 10) 1 3 (12, 13) 2 4 (14, 15) 1 2 (15, 19) 1 2 (16, 18) 1 2 (18, 20) 2 4 (23, 22) 0 1 (24, 21) 0 1 Link Extra duration for adding one lane [D.sup.1.sub.a] (1,2) 8 (9, 8) 3 (11, 10) 3 (12, 13) 4 (14, 15) 2 (15, 19) 2 (16, 18) 3 (18, 20) 4 (23, 22) 1 (24, 21) 1 Table 6: Selection and scheduling results for Example 2. Stating time Ending time Newly Reduced added lanes 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 0

Printer friendly Cite/link Email Feedback | |

Title Annotation: | Research Article |
---|---|

Author: | He, Yi; Song, Ziqi; Zhang, Lihui |

Publication: | Journal of Advanced Transportation |

Date: | Jan 1, 2018 |

Words: | 12349 |

Previous Article: | Air Traffic Efficiency Analysis of Airliner Scheduled Flights Using Collaborative Actions for Renovation of Air Traffic Systems Open Data. |

Next Article: | Optimal Bus-Bridging Service under a Metro Station Disruption. |

Topics: |