Bi-level optimization of long-term highway work zone scheduling considering elastic demand

Abstract

Purpose

More and more work zone projects come with the needs of new construction and regular maintenance-related investments in transportation. Work zone projects can have many significant impacts socially, economically and environmentally. Minimizing the total impacts of work zone projects by optimizing relevant schedules is extremely important. This study aims to analyze the impacts of scheduling long-term work zone activities.

Design/methodology/approach

Optimal scheduling of the starting dates of each work zone project is determined by developing and solving using a bi-level genetic algorithm (GA)–based optimization model. The upper level sub-model is to minimize the total travel delay caused by work zone projects over the entire planning horizon, whereas the lower level sub-model is a traffic assignment problem under user equilibrium condition with elastic demand.

Findings

Sioux Falls network is used to develop and test the proposed GA-based model. The average and minimum total travel delays (TTDs) over generations of the proposed GA algorithm decrease very rapidly during the first 20 generations of the GA algorithm; after the 20th generations, the solutions gradually level off with a certain level of variations in the average TTD, showing the capability of the proposed method of solving the multiple work zone starting date optimization problem.

Originality/value

The proposed model can effectively identify the near-optimal solution to the long-term work zone scheduling problem with elastic demand. Sensitivity analysis of the impact of the elastic demand parameter is also conducted to show the importance of considering the impact of elastic demand parameter.

Citation

Li, Y. and Fan, W. (2021), "Bi-level optimization of long-term highway work zone scheduling considering elastic demand", Smart and Resilient Transportation, Vol. 3 No. 2, pp. 118-130. https://doi.org/10.1108/SRT-01-2021-0004

1. Introduction

With the rapid development of transportation system, an increasing number of work zone projects comes with the needs of new construction and regular maintenance-related investments in transportation. However, the negative impacts of the work zone projects on the traffic in the transportation network may be inevitable and can cause many issues socially, economically and environmentally. As such, work zone projects that aim at relieving congestion while expanding capacity of the network are becoming more important. Last year, Federal Highway Administration (FHWA) issued a notice of proposed rulemaking for performance-based planning and programming (Federal Highway Administration, 2017). It requires state departments of transportation and metropolitan planning organizations to measure and report on the performance of infrastructures on the National Highway System within their jurisdictions. A series of enhanced performance measures have been developed and included in this new rule. However, it is still lacking in performance measures for assessing congestion under special events including the presence of work zones (Ramadan and Sisiopiku, 2018). Despite such absence of metrics, which can be used for evaluation, attention should also be paid to minimize the impacts of relevant work zone activities.

In two publications by FHWA (Jeannotte and Chandra, 2005; Sankar et al., 2006), impacts caused by work zone events can be categorized into following six groups: safety impacts, mobility impacts, economic considerations, environmental concerns, user cost and contractor’s maintenance costs. From the contractor’s standpoint, the total maintenance cost of work zone activities might carry more weight to be minimized (Meng and Weng, 2013). On the other side, roadway users are also concerned about the interruptions that work zone events cause to their travel mobility and cost. While from a high level of planning, local agencies need to comprehensively take at least some of the six aspects into consideration to balance the total impacts. There is no doubt that the there is no simple relationships among all those impacts. According to Hardy and Wunderlich (2008), among all six impact types, the impact of mobility is the key for assessing the remaining five aspects associated with work zone events. They further pointed out that after thoroughly evaluating the mobility impacts, all other aspects could be determined as well.

Therefore, many research efforts have been carried out to model the impacts of the work zone events to develop the corresponding solutions for minimizing such impacts. By striking a balance between work zone project contractors and roadway users, many existing studies have been trying to focus on minimizing the total costs from both sides (users’ travel delays and the work zone maintenance costs) (Schonfeld and Chien, 1999; Chien and Schonfeld, 2001; Miralinaghi et al., 2020). Traditional deterministic queuing theory (Dudek and Richards, 1982; Jiang and Adeli, 2003; Yang et al., 2009; Abdelmohsen and El-Rayes, 2018) and shock wave theory (Wirasinghe, 1978; Newell, 1993) can be used to evaluate travel delay and queue length on local roadway segments where road work exists (Gong and Fan, 2016). However, such methods are not able to consider the broader impacts of work zones at a network level. Recently, researchers applied microscopic traffic simulation to quantify work zone delays (Chung et al., 2012; He et al., 2019). Well-calibrated simulation models can generate high fidelity traffic measures under various work zone configurations. CORSIM and VISSIM are among the most widely used models. However, the simulation approaches for delay prediction generally suffer from high computational time, and the results only represent the traffic measures for a specific work zone on a specific segment of a highway. Furthermore, most of the research studies are related to short-term work zones within a short time frame. Few studies have focused on modeling the impact of the work zone activities on the transportation network itself over the whole planning horizon before considering other detailed issues. Moreover, when dealing with the route user behavior change because of the impacts of work zone activities (such as traffic congestion), traffic diversion is one of the common strategies considered in many literatures (Chen et al., 2005; Tang and Chien, 2009; Chien and Tang, 2014; Zhao et al., 2019). This is useful for short-term work zone events analysis. As route users are already on roads, it would also be a sufficient way to deal with local roadway segments. However, for the long-term work zone projects planning and management, such practice may not be desirable, as it ignores the fact that some of the route users would rather choose other transportation modes to accomplish their trips or daily commuting. In other words, it would be more realistic to consider elastic demand in this case to take such user behavior change into consideration for the highway work zone scheduling optimization problem.

Building upon the work of (Gong and Fan, 2016), this study uses a macroscopic optimization model to evaluate the mobility impacts of long-term work zone events (i.e. total travel delay) and optimizing the scheduling of starting dates of work zone projects. Rather than using the fixed traffic demand, elastic demand is explicitly accounted for in this study. A bi-level optimization model is developed and solved by a proposed genetic algorithm (GA)-based solution framework. Network experiments are conducted. Numerical results are also given, followed by a summary and discussion on future research directions.

2. Problem statement

2.1 Assumption

The main purpose of this research is to evaluate the mobility impacts of long-term work zone events and optimize the scheduling of starting dates of work zone projects from the perspective of decision-makers. The major assumptions are stated as follows: the topological information of the transportation network and the O–D matrix are known (based on which the user equilibrium [UE] with elastic demand model is built); the number of work zones and the project duration of each work zone are known; and drivers have perfect information and knowledge of the network, and they are all homogeneous and rational decision-makers (UE assumption).

2.2 Notations

The network design problem can be represented in terms of “nodes,” “links” and “route.” Consider a connected network with N nodes and A links, G (N, A), which consists of a finite set of N nodes and A links. Note that link a ∈ K, which connects pairs of nodes. To formulate the model, the following notations are used:

• a = arc, or link index, a = 1, 2,…, A;

• w = OD pair inde, w ∈ W;

• B = the subset of A, a set of selected work zone projects on link a, a ∈ B ⊆ A;

• P_w = a set of paths of OD pair w;

• fpw = the flow on the p – path of OD pair w(p ∈ P_w);

• C_a = the basis capacity of link a;

• T_a = the estimated duration of the work zone project (on link a, a ∈ B);

• γ_a = the capacity reduction factor of work zone (on link a), 0 ≤ γ_a ≤ 1;

• δapw = 1 if link a is used in path p which connects OD pair w; otherwise = 0;

• d_0w = a priori demand of OD pair w;

• t_a(x_a) = the travel time on link a given link volume x_a;

• q_a = the project starting date of the work zone; and

• T_max = the maximum project deadline for all work zone activities.

2.3 Model formation

As mentioned previously, this study proposes a bi-level programming model for determining the starting date of each work zone project. In general, there are two players involved in the bi-level model, the leader and the follower. Thus, there are two sets of decision variables and objectives that correspond to these two levels, and two players try to optimize their own objectives in sequence (Fan and Gurmu, 2014). The bi-level programming has been successfully applied by many researches during the past years for various network design problems (Constantin and Florian, 1995; Yang, 1996; Yang and Bell, 1998; Clegg et al., 2001; Zhang and Yang, 2004; Fan and Machemehl, 2011; Bagloee et al., 2018). In this paper, the upper level sub-model is to minimize the total travel delay (in terms of veh*time) caused by work zone projects over the entire planning horizon, and the lower level sub-model is a network UE with elastic demand model in terms of generalized travel cost.

The upper level sub-model that minimizes the total travel delay (TTD) is written as given in equations 1–3:

(1) minqa, a∈B∑s=12|B|∑a∈Ams(qa)⋅[tsa(xsa)−t0a]⋅xsa

Subject to:

(2) 1≤qa≤Tmax−Ta, a∈B

(3) ∑s=12|B|ms(qa)=Tmax, a∈B

where m_s is the number of days when the network is under status s (s = 1, 2, …, 2^|B|), and s here is supply status of the network corresponding to possible combination of the starting date of each work zone project. t_0a is the free flow travel time on link a (a = 1, 2, …, A), and x_sa is the solution to the following lower-level sub-model, which represents the UE with elastic O-D demand, as in equations 4–7:

(4) min(∑a∈A∫0xaCa(ω)dω−∑w∈W∫0dwDw−1(ω)dω)

Subject to:

(5) xa=∑w∈W∑p∈Pwfpw×δapw, a∈A

(6) ∑p∈Pwfpw=dw, w∈W

(7) fpw≥0, p∈Pw, w∈W

where the C_a(ω) is the generalized link cost function and uses the most widely used Bureau of Public Roads (BPR) link performance function, as given in equation (8):

(8) Ca(ω)=t0a[1+α(ωγa×Capa)β] (γa=1, if a∈A\B;=0.5, if a∈B)

where α and β are empirical coefficients with common values of 0.15 and 0.4, respectively. d_w is the demand function, which can be expressed as in given equation (9):

(9) dw=d0w⋅e−Ωw×μw, w∈W

where d_0w is the fixed demand between O–D pair w that was first proposed by Bar-Gera (2016); μ_w is the minimum generalized travel time between O–D pair w; and Ω_w denotes the demand parameter measuring the impact of the travel time on elastic demand. Note that this relationship used here is adopted from the studies of Chen and Yang (2004) and Recker et al. (2005).

2.4 Simple example illustration for s

As shown in the Figure 1, this simple network contains four nodes and eight links. Links with bold arrows are chosen to be maintained, denoted as the top link and bottom link. It is assumed that they have the same project duration (i.e. T_top = T_bottom) with corresponding starting dates q_top and q_bottom. Thus, there will be potentially four different network supply statuses during the entire planning horizon [0, T_max], including the basic status without any work zone activities, which are shown in the Figure 1. a to d. Scenario 1, as shown in Figure 1. e, can be explained as follows: (1) periods [0, q_top] and [q_bottom+T_bottom, T_max] are basic status when s = 1, without any work zone activities; (2) when s = 2, only top link (i.e. top work zone in Figure 1) is under maintenance with capacity reduction of top link from C_top to C_top·γ_top (0 ≤ γ_top ≤ 1), and the corresponding period is [q_top, q_bottom]; (3) when s = 4, both links are work zones of which both link capacities are reduced from C_top and C_bottom to C_top·γ_top and C_bottom · γ_bottom (0 ≤ γ ≤ 1), and the corresponding period is [q_bottom, q_top + T_top]; (4) when s = 3, it is similar to s = 2, however, only bottom link (i.e. bottom work zone in Figure 1) is under maintenance with capacity reduction of link above from C_bottom to C_bottom · γ_bottom (0 ≤ γ_bottom ≤ 1), and the corresponding period is [q_top+T_top, q_bottom, q_bottom+T_bottom]. In Scenario 2, as displayed in Figure 1 f, both work zone events start at the same date, and as such, only two different network supply status exist (i.e. s = 1 and s = 4).

In a more complicated and general scenario with |B| work zones, the number of link work zone (s) could possibly be any integer number that falls into the range of [0, |B|] for each single day during [0, T_max]. Such situation will yield a total number of 2^|B| potential network supply status.

3. Model solution methodology

It is important to note that the time for finding the optimal long-term highway work zone scheduling (i.e. the combination of starting date for each work zone project) will increase remarkably when |B| increases. Hence, it is worthwhile to design an efficient solution method for solving the bi-level optimization model that has been built for the long-term highway work zone scheduling problem. Inspired by the evolutionary ideas of natural selection and genetics (Holland, 1992; Goldberg and Holland, 1988; Michalewicz, 2013), the GA has already been a well-known type of adaptive heuristic search algorithm. Many research efforts have proven that GA can provide a robust and near-optimal solution within a reasonable amount of time. There are several intermediate steps within the GA process as well. For instance, the lower level network analysis involves the determination of the link flows and O–D demands, which will be used as input to the upper level sub-model, by applying the Frank–Wolfe algorithm. Figure 2 shows the flow chart of the whole GA process for the stated problem.

4. Numerical example

4.1 Example network description

As shown in Figure 3, the Sioux Falls network is considered as the example network in this study, which consists of 24 travel demand zones, 76 links and 576 O–D pairs. Network data used in this paper are adopted from LeBlanc, Morlok and Pierskalla (1975). The data could be accessed from the repository of the Transportation Networks for Research Core Team. It should be worth mentioning that the input data for the model only include the files of “SiouxFalls_net” and “SiouxFalls_trips”, which show the ease of use of the proposed model. Meanwhile, Bar-Gera (2016) found the Sioux Falls user equilibrium solution by applying the quadratic BPR cost functions, which could be used for cross-checking results. This solution corresponds to the minimum generalized travel time between O–D pair w (i.e. μ_w).

Adopted form Gong and Fan (2016), five links in the example network are selected to be maintained as the work zone projects, which are displayed in red lines in Figure 3 (i.e. B = {12, 36, 41, 56, 68}). The corresponding durations for these five selected work zones are T_a = [90, 180, 270, 360, 450]. For convenience, the capacity reduction factor for all the selected work zones is assumed to be 0.5, which means the capacity of the road will be reduced by a half because of work zone events (i.e. γ_a = 0.5).

Parameters inherent in the GA algorithms need to be selected carefully; otherwise, they might have some effects on the optimal solution. Some research work has been done for determining the inherent parameters in the GA algorithm. Based on the studies of Chen and Yang (2004) and Recker et al. (2005), the following parameters are chosen in this study for numerical analysis: population size, 64; maximum number of generations, 200; crossover probability, 0.7; mutation probability, 0.05; and elastic demand parameter (Ω_w), 0.02.

Based on all the assumptions above, the proposed GA procedure is performed via MATLAB software package. The total elapsed time for the model is 54.327 s.

4.2 Results of the genetic algorithm–based bi-level model

Figure 4 shows the average and minimum TTDs over generations of the proposed GA algorithm. It can be seen that both TTDs decrease very rapidly during the first 20 generations of the GA algorithm; after the 20th generations, the solutions gradually level off with a certain level of variations in the average TTD. Such variations could be explained as results of the mutation operations in the GA algorithm. This illustrates that the proposed GA-based framework is capable of solving the multiple work zone starting date optimization problem with elastic demand and can provide efficient and stable solutions.

Table 1 exhibits all the specific combinations of work zone links corresponding to each network status associated with the TTD values. The “Rank” column shows the rankings of TTD for each network status. The impacts of each work zone combination are also examined and displayed as the percentage changes compared to the uninterrupted network status. It is noticeable that the combinations “4” and “8” have highest impacts compared to other combinations within their subgroups, respectively (i.e. one work zone combination and two work zone combination, respectively). Moreover, “4” even has a higher impact than combinations “9” and “16.” The other two similar results are obtained with both “8” and “15” when it compares to combination “22.” Also, compared to Gong and Fan (2016), the results of TTDs are less, and this might be the reason that the reduction in traffic volumes in the whole network because of the consideration of elastic demand.

One example of the optimal solutions is also given in Table 1. It should be pointed out that in the proposed GA, the duration of each network status is actually determined by the relative gap between the starting dates of different work zone events, other than the absolute starting date of each project within the whole planning horizon. Discussions can be referred to Gong and Fan (2016). Thus, the proposed GA-based algorithm could find the near optimal solution very quickly.

4.3 Effect of elastic demand parameter (Ω_w)

As discussed previously, the demand function used in this paper is shown in equation 9. It is hypothesized that how much TTDs are generated might greatly depend upon how traffic flows change in the elastic demand scenario. As the elastic demand parameter (Ω_w) is the key to connect the traffic demand with travel time, it would be worthwhile to conduct the sensitivity analysis and evaluate the impacts of this parameter.

Table 2 shows the results of the sensitivity analysis for the demand parameter. As the elastic demand parameter increases, the TTD in the optimal solution also decreases. As the elastic demand parameter increases, travelers become more sensitive to the generalized travel time, and therefore, it is likely that more travelers may forego their trips or switch to alternative modes. As a result, less demand is produced. As shown in the Table 2, such phenomenon is also supported by the total traffic volume under the status of uninterrupted network (corresponding to “status 1” in Table 1). Note that changes under other work zone combinations are examined and the same trends are also obtained. This clearly highlights the importance of considering the impact of elastic demand parameter when planning for the starting date of each work zone event to minimize the total travel delay because of the long-term work zone activities.

5. Conclusion and future study

This paper analyzes the impacts of the long-term work zone events on the mobility performance of the network with the consideration of elastic demand. A bi-level optimization model is built, which is later solved by the GA algorithm. The impacts of all work zone combinations are examined, and the sensitivity analysis of the elastic demand parameter (Ω_w) is also conducted. Numerical results imply that the proposed model and algorithm are capable of providing near-optimal solutions for the long-term work zone scheduling problem with elastic demand at a network level during the entire planning horizon. The result of sensitivity analysis indicates that it is important to consider the impact of elastic demand parameter, as the fact that some of the route users would rather switch to alternative transportation modes to complete their trips or daily commuting, as a larger Ω_w indicates more sensitivity to the generalized travel time of the travelers.

As this research mainly focuses on the impacts of work zone from the perspective of traffic agencies and jurisdictions, concerns from other aspects (such as the maintenance cost to contractors) are not considered in this study. Meanwhile, the proposed method is not able to capture the characteristic of how traffic flow evolves with time (i.e. short periods); rather it intends to solve the long-term work zone scheduling problem during the planning stage. Thus, future research may consider bringing other benefits into the model and combine both long-term and short-term scheduling planning together. Finally, future research can also be directed toward examining the heterogeneity across drivers and applying the dynamic traffic assignment for solving the highway work zone scheduling optimization problem.

Figures

Figure 1.

Different combination of network supply status

Figure 2.

Flow chart of the GA-based solution framework

Figure 3.

Sioux Falls test network

Figure 4.

TTDs over generations

Table 1.

Analysis of the TTD for each network status and examples of optimal solution

Status	Combination of maintenance required roads					# of roads maintained	TTD	% change with respect to the uninterrupted network	Rank	Example of one optimal solution
ID										Duration of each network status	Starting date of each work zone
1	0	0	0	0	0	0	1011160	0.00	32	31
2	12	0	0	0	0	1	1029438	1.81	29	24	23
3	0	36	0	0	0	1	1036381	2.49	28	0	167
4	0	0	41	0	0	1	1043886	3.24	25	0	47
5	0	0	0	56	0	1	1022402	1.11	31	0	77
6	0	0	0	0	68	1	1028757	1.74	30	274	261
7	12	36	0	0	0	2	1057240	4.56	19	0	–
8	12	0	41	0	0	2	1059970	4.83	16	30	–
9	12	0	0	56	0	2	1040812	2.93	26	0	–
10	12	0	0	0	68	2	1047571	3.60	23	0	–
11	0	36	41	0	0	2	1057192	4.55	20	0	–
12	0	36	0	56	0	2	1046221	3.47	24	0	–
13	0	36	0	0	68	2	1055943	4.43	22	0	–
14	0	0	41	56	0	2	1056942	4.53	21	53	–
15	0	0	41	0	68	2	1059945	4.82	17	0	–
16	0	0	0	56	68	2	1040733	2.92	27	90	–
17	12	36	41	0	0	3	1077947	6.61	7	0	–
18	12	36	0	56	0	3	1066219	5.45	14	0	–
19	12	36	0	0	68	3	1075379	6.35	9	0	–
20	12	0	41	56	0	3	1072375	6.05	11	37	–
21	12	0	41	0	68	3	1076019	6.41	8	0	–
22	12	0	0	56	68	3	1059684	4.80	18	0	–
23	0	36	41	56	0	3	1067563	5.58	13	94	–
24	0	36	41	0	68	3	1075364	6.35	10	0	–
25	0	36	0	56	68	3	1064987	5.32	15	30	–
26	0	0	41	56	68	3	1071220	5.94	12	0	–
27	12	36	41	56	0	4	1090138	7.81	3	0	–
28	12	36	41	0	68	4	1097155	8.50	2	0	–
29	12	36	0	56	68	4	1087261	7.53	4	0	–
30	12	0	41	56	68	4	1086747	7.48	6	0	–
31	0	36	41	56	68	4	1086851	7.49	5	57	–
32	12	36	41	56	68	5	1108368	9.61	1	0	–
										qa = [23, 167, 47, 77, 261]
										TTD = 753343866
										Average TTD = 1046310

Table 2.

Demand parameter sensitivity analysis

Demand parameter value (Ωw)	TTD (optimal solution)	Uninterrupted network total traffic volume
0.001	28,37,30,0479	85,4592
0.002	25,45,94,4476	83,4460
0.005	19,38,19,9211	78,4,795
0.01	13,68,61,6643	72,0700
0.02	75,33,43,866	6,32,193
0.05	25,08,92088	46,2084
0.1	49,52,0431	2,93,889
0.2	72,05951	13,9,073
0.5	10,440	26,130