ABSTRACT Title of dissertation: INTEGRATED MANAGEMENT OF HIGHWAY MAINTENANCE AND TRAFFIC Chun-Hung Chen, Doctor of Philosophy, 2003 Dissertation directed by: Professor Paul M. Schonfeld Department of Civil and Environmental Engineering Highway maintenance, especially pavement rehabilitation or resurfacing, requires lane closures. This work develops an integrated model to help highway agencies in developing traffic control plans for maintenance activities and in efficiently managing traffic around highway work zones. Thus, the objective of this study is to develop methods for optimizing work zone characteristics in order to minimize the combined total costs for highway agencies and users. Work zone models are developed for three cases: (1) a single maintained road with steady traffic inflows, (2) a single maintained road with time-dependent inflows, and (3) a road network with multiple detour paths, as well as plans for maintenance activities and managing traffic around highway work zones. For Case 1, with steady traffic inflows, four alternatives for two-lane highways and four alternatives for four-lane highways are proposed. Analytical solutions are found for optimized work zone lengths and diversion fractions based on minimizing the total cost. Guidelines for selecting the best alternative for different characteristics of traffic flows, road and maintenance processes are developed by deriving thresholds among alternatives. In Case 2, the models for two-lane highway and four-lane highway work zones for time-dependent inflows are developed. Two optimization methods, Powell?s and Simulated Annealing, are adapted for this problem and compared. In numerical tests, a Simulated Annealing algorithm yields better solutions using less computer time than Powell?s Method. In testing the reliability of Simulated Annealing, the statistical analysis for 50 replications of the cost minimization indicates that Simulated Annealing is very likely to find solutions that are very close in value to the global optimum. The SAUASD (Simulated Annealing for Uniform Alternatives with a Single Detour) algorithm is developed to find the best single alternative within a maintenance project. The SAMASD (Simulated Annealing for Mixed Alternatives with a Single Detour) algorithm is developed to search through possible mixed alternatives and diverted fractions in order to further minimize total cost. Thus, traffic management plans with uniform alternatives or mixed alternatives within a maintenance project are developed. For Case 3, work zone optimization models for a road network with multiple detour paths and the SAMAMD (Simulated Annealing for Mixed Alternatives with Multiple Detour paths) algorithm are developed. For analyzing traffic diversion through multiple detour paths in a road network, the SAMAMD algorithm is used to optimize work zone lengths and schedule the resurfacing work. Analyses based on the CORSIM simulation are used not only to estimate delay cost, but also to evaluate the effectiveness of optimization models. A comparison of the results from optimization and simulation models indicates that they are consistent. The optimization models do significantly reduce total cost, including user cost and maintenance cost, compared to the total cost of the current resurfacing policy in Maryland. INTEGRATED MANAGEMENT OF HIGHWAY MAINTENANCE AND TRAFFIC by Chun-Hung Chen Dissertation submitted to the Faculty of the Graduate School of the University of Maryland, College Park in partial fulfillment of the requirements for the degree of Doctor of Philosophy 2003 Advisory Committee: Professor Paul M. Schonfeld, Chairman / Advisor Professor Frank B. Alt Professor Steven I. Chien Professor Dimitrios G. Goulias Professor Ali Haghani ii DEDICATION To my family iii ACKNOWLEDGEMENTS I would like to give my heartfelt appreciation to my advisor Dr. Paul Schonfeld for his support and encouragement throughout my Ph. D. study. His patience, passion and expert guidance made this work possible. Drs. Ali Haghani, Dimitrios Goulias, Frank Alt, and Steven Chien honored me by investing time and showing interest in my project. Their precious comments and advises makes this dissertation more solid and sound. I would like to express my appreciation to them. I thank the Maryland State Highway Administration for supporting project funding. I thank Mr. Jawad Paracha for many discussions concerning project progress and comments. I thank Dr. Xinmao Wang for his friendship and discussions concerning Visual Basic. I also thank Jason Lu for many interesting discussions concerning algorithm development. Special thanks go to all my past and present program members: Richard Huang, Lewis Chen, Shaojia Du, Ying Luo, Taehyung Kim, Hyoungsoo Kim, Xiaorong Lai, and Kyeongpyo Kang for their friendship and support. I would like to give my grateful thansks to my family especially my wife Jinzhi Chen, my grandparents, my parents, and my parents-in-law. Their understanding and support helped me achieve my goals. To my wife Jinzhi, thank you for supporting my decision to pursue a life-long dream. Your love has sustained me through my graduate study years. iv TABLE OF CONTENTS LIST OF TABLES............................................................................................................ vii LIST OF FIGURES ............................................................................................................ x Chapter I Introduction......................................................................................................... 1 1.1 Background............................................................................................................... 1 1.2 Problem Statement.................................................................................................... 2 1.3 Research Objectives.................................................................................................. 4 1.4 Research Scope and Tasks........................................................................................ 4 1.5 Technical Approach.................................................................................................. 5 1.6 Organization of Dissertation..................................................................................... 8 Chapter II Literature Review ............................................................................................ 11 2.1 Work Zone Issues ................................................................................................... 11 2.2 Work Zone Cost Items............................................................................................ 12 2.3 Research Trends...................................................................................................... 13 2.4 Optimization Algorithms ........................................................................................ 21 2.5 Summary................................................................................................................. 24 Chapter III Work Zone Optimization for Steady Traffic Inflows..................................... 26 3.1 Highway System Definition.................................................................................... 26 3.2 Work Zone Optimization - Two-Lane Two-Way Highway ................................... 30 3.2.1 Alternatives and Assumptions ......................................................................... 30 3.2.2 Model Formulation .......................................................................................... 32 3.3 Work Zone Optimization - Four-Lane Two-Way Highway................................... 41 3.3.1 Alternatives and Assumptions ......................................................................... 41 3.3.2 Model Formulation .......................................................................................... 42 3.4 Determination of Work Zone and Detour Speeds................................................... 55 3.5 Threshold Analysis ................................................................................................. 57 3.6 Numerical Analysis - Two-Lane Two-Way Highway............................................ 58 3.6.1 Sensitivity Analysis ......................................................................................... 58 3.6.2 Selection Guidelines ........................................................................................ 65 3.6.3 Optimizing the Diverted Fraction .................................................................... 68 3.6.4 Summary.......................................................................................................... 70 v 3.7 Numerical Analysis ? Four-Lane Two-Way Highways ......................................... 71 3.7.1 Sensitivity Analysis ......................................................................................... 71 3.7.2 Selection Guidelines ........................................................................................ 76 3.7.3 Optimizing the Diverted Fraction .................................................................... 79 3.7.4 Summary.......................................................................................................... 80 Chapter IV Work Zone Optimization for Time-Dependent Inflows ................................ 81 4.1 Work Zone Cost Function for Time-Dependent Inflows........................................ 83 4.1.1 Model Formulation ? Two-Lane Two-Way Highways (Alternative 2.1)........ 83 4.1.2 Model Formulation ? Four-Lane Two-Way Highways (Alternative 4.1) ....... 89 4.2 Optimization Methods ............................................................................................ 93 4.2.1 Powell?s Method .............................................................................................. 93 4.2.2 Simulated Annealing Algorithm...................................................................... 95 4.3 Numerical Analysis ? Two-Lane Two-Way Highway ......................................... 108 4.4 Numerical Analysis ? Four-Lane Two-Way Highway......................................... 118 4.5 Reliability of Simulated Annealing ...................................................................... 123 Chapter V Work Zone Optimization with a Detour........................................................ 125 5.1 Work Zone Cost Functions with a Detour ............................................................ 126 5.1.1 Queuing Delay on a Detour ........................................................................... 126 5.1.2 Two-Lane Highway Work Zone with a Detour............................................. 128 5.1.3 Four-Lane Highway Work Zone with a Detour............................................. 135 5.2 Optimization Methods .......................................................................................... 142 5.2.1 Uniform Alternatives and Mixed Alternatives .............................................. 142 5.2.2 Simulated Annealing Algorithm for Mixed Alternatives with a Single Detour- SAMASD...................................................................................................... 143 5.3 Numerical Examples - Two-Lane Highway Work Zone with a Detour............... 147 5.4 Numerical Examples - Four-Lane Highway Work Zone with a Detour............... 151 5.5 Numerical Examples ? Mixed Alternatives.......................................................... 157 Chapter VI Work Zone Optimization with Multiple Detour Paths................................. 163 6.1 Types of Multiple Detour Paths............................................................................ 163 6.2 Optimization Models for Work Zones with Multiple Detour Paths ..................... 167 6.2.1 Extension of Optimization Model for Multiple-lane Highway...................... 167 vi 6.2.2 Model Formulation ........................................................................................ 168 6.2.3 Simulated Annealing Algorithm for Mixed Alternatives with Multiple Detour Paths - SAMAMD................................ ......................................................... 174 6.3 Development of Simulation Model....................................................................... 177 6.3.1 Simulation Model for Work Zone.................................................................. 177 6.3.2 Evaluation of Optimization Models by Simulation ....................................... 178 6.4 Case Study ............................................................................................................ 181 6.4.1 Optimization Results...................................................................................... 181 6.4.2 Current Policy ................................................................................................ 188 6.4.3 Simulation Results ......................................................................................... 191 Chapter VII Conclusions and Recommendations ........................................................... 195 7.1 Summary............................................................................................................... 195 7.2 Conclusions........................................................................................................... 196 7.2.1 Work Zone Optimization for Steady Traffic Inflows .................................... 196 7.2.2 Work Zone Optimization for Time-Dependent Inflows ................................ 197 7.2.3 Work Zone Optimization with a Detour ........................................................ 199 7.2.4 Work Zone Optimization for Multiple Detour Paths..................................... 200 7.3 Recommendations for Future Research ................................................................ 200 Appendix A Variable List............................................................................................... 204 References ..................................................................................................................... 211 vii LIST OF TABLES Table 1.1 Organization of Dissertation............................................................................. 10 Table 3.1 Inputs for Numerical Example and Sensitivity Analysis for Two-Lane Two- Way Highway Work Zones........................................................................... 59 Table 3.2 Optimized work zone lengths and Total Costs for Different Flow Rates......... 60 Table 3.3. Comparison of Delay Costs with Different Directional Flows for Alternative 2.2 (p=o.6) ..................................................................................................... 61 Table 3.4 Circuity Threshold at Different Flow Rates ..................................................... 68 Table 3.5 Notation and Baseline Numerical Inputs Analysis for Four-Lane Two-Way Highway Work Zones ................................................................................... 71 Table 3.6 Optimized work zone lengths (km) and Total Costs ($/lane.km) for Various Flow Rates ..................................................................................................... 73 Table 4.1 Simulated Annealing Algorithm....................................................................... 96 Table 4.2 Notation and Baseline Numerical Inputs for Two-Lane Two-Way Highway Work Zones ................................................................................................. 108 Table 4.3 AADT and Hourly Traffic Distribution on a Two-Lane Two-Way Highway 109 Table 4.4(a) Optimized Results for Numerical Example (Two-Lane Highway), Project Starting Time: 11:00, vd=$800/hr................................................................ 111 Table 4.4(b) Optimized Results for Numerical Example (Two-Lane Highway), Project Starting Time: 17:00, vd=$800/hr................................................................ 111 Table 4.5(a) Optimized Results for Numerical Example (Two-Lane Highway), Project Starting Time: 11:00, vd = $2000/hr ............................................................ 113 Table 4.5(b) Optimized Results for Numerical Example (Two-Lane Highway), Project Starting Time: 11:00, vd = $200/hr .............................................................. 113 Table 4.6(a) Optimized Results for Numerical Example (Two-Lane Highway), Project Starting Time: 11:00, z2=$10,000/km ......................................................... 116 Table 4.6(b) Optimized Results for Numerical Example (Two-Lane Highway), Project Starting Time: 11:00, z2=$5,000/km ........................................................... 116 Table 4.6(c) Optimized Results for Numerical Example (Two-Lane Highway), Project Starting Time: 11:00, z2=$100/km .............................................................. 117 viii Table 4.7 Notation and Baseline Numerical Inputs for Four-Lane Two-Way Highway Work Zones ................................................................................................. 118 Table 4.8 AADT and Hourly Traffic Distribution on a Four-Lane Two-Way Highway119 Table 4.9 Optimized Results for Numerical Example (Four-Lane Highway), Project Starting Time: 21:00, vd=$800/hr................................................................ 120 Table 4.10(a) Optimized Results for Numerical Example (Four-Lane Highway), Project Starting Time: 21:00, vd = $2400/hr ............................................................ 122 Table 4.10(b) Optimized Results for Numerical Example (Four-Lane Highway), Project Starting Time: 21:00, vd = $100/hr .............................................................. 122 Table 4.11 Optimized Results for Numerical Example, Project Starting Time: 11:00, vd=$800/hr (10th replication), Alternative 2.1 ............................................. 124 Table 5.1 Inputs for Numerical Example for Two-Lane Highway Work Zones with Detour .......................................................................................................... 147 Table 5.2 AADT and Hourly Traffic Distribution on Detour (Two-lane Highway) ...... 148 Table 5.3 Optimized Results for Numerical Example, Project Starting Time: 11:00, vd=$800/hr, Alternative 2.3 ......................................................................... 149 Table 5.4 AADT and Hourly Traffic Distribution on Detour (Four-lane Highway)...... 152 Table 5.5(a) Optimized Results for Numerical Example, Main Road AADT=40,000 veh/day, Project Starting Time: 11:00, Alternative 4.1............................... 156 Table 5.5(b) Optimized Results for Numerical Example, Main Road AADT=40,000 veh/day, Project Starting Time: 11:00, Alternative 4.2, p=0.3 ................... 156 Table 5.6(a) Optimized Results for Numerical Example, Detour AADT=5,000 veh/day, Project Starting Time: 11:00, Alternative 2.3 ............................................. 159 Table 5.6(b) Optimized Results for Numerical Example, Detour AADT=5,000 veh/day, Project Starting Time: 11:00, Mixed Alternatives ...................................... 159 Table 5.7(a) Optimized Results for Numerical Example, Detour AADT=20,000 veh/day, Project Starting Time: 11:00, Alternative 2.3 ............................................. 160 Table 5.7(b) Optimized Results for Numerical Example, Detour AADT=20,000 veh/day, Project Starting Time: 11:00, Mixed Alternatives ...................................... 160 Table 5.8(a) Optimized Results for Numerical Example, Detour AADT=25,000 veh/day, Project Starting Time: 11:00, Mixed Alternatives ...................................... 161 ix Table 5.8(b) Optimized Results for Numerical Example, Detour AADT=30,000 veh/day, Project Starting Time: 11:00, Mixed Alternatives ...................................... 161 Table 5.8(c) Optimized Results for Numerical Example, Detour AADT=35,000 veh/day, Project Starting Time: 11:00, Mixed Alternatives ...................................... 162 Table 6.1 Inputs for Case Study for IS-95 Eight-Lane Freeway Work Zones ............... 182 Table 6.2 AADT and Hourly Traffic Distributions on Main Road (IS-95) and Detour (US-1).......................................................................................................... 184 Table 6.3 Optimized Results for Case Study, Project Starting Time: 20:00, Alternative 8.2 (p=0.1, k=0) ........................................................................................... 186 Table 6.4 Optimized Results for Case Study, Project Starting Time: 20:00, Alternative 8.2 (p=0.1, k=0.2) ........................................................................................ 187 Table 6.5 Optimized Results for Case Study, Project Starting Time: 20:00, Mixed Alternatives ................................................................................................. 188 Table 6.6 Current Work Zone Policy for Case Study (p=0, k=0), Project Starting Time: 9:00.............................................................................................................. 189 Table 6.7 Current Work Zone Policy for Case Study (p=0, k=0), Project Starting Time: 19:00............................................................................................................ 189 Table 6.8 Comparison Between Total Costs of Current Policy and Optimized Solution190 Table 6.9(a) Simulation (Simplified Network1) and Optimization Results of Current Policies and Optimized Solution ................................................................. 192 Table 6.9(b) Simulation (Complete Network1) and Optimization Results of Current Policies and Optimized Solution ................................................................. 193 Table 6.10 Comparison of the Results of Optimization Model and Simulation Model . 193 x LIST OF FIGURES Figure 1.1 Research Flow Chart ......................................................................................... 6 Figure 1.2 Conceptual Effect of Work Zone Length on Total Cost, Maintenance Cost, and User Cost ......................................................................................................... 7 Figure 3.1 Geometries of Analyzed Work Zones for Two-Lane Two-Way Highways ... 28 Figure 3.2 Geometries of Analyzed Work Zones for Four-Lane Two-Way Highways ... 31 Figure 3.3 Queue Length for Four-lane Highway Work Zone ......................................... 44 Figure 3.4 Total Cost vs. Detour Length .......................................................................... 57 Figure 3.5 User Costs versus Various Zone Lengths (Q1=400vph, Q2=400vph) ............. 61 Figure 3.6 Total Costs versus Various Work Zone Lengths (Q1=400vph, Q2=400vph) .. 62 Figure 3.7 Optimized Zone Length versus Setup Cost z1 (Q1=400vph, Q2=400vph) ...... 63 Figure 3.8 Optimized Zone Length versus Average Maintenance Time z4 (Q1=400vph, Q2=400vph) ................................................................................................... 63 Figure 3.9 User Delay Costs versus Combined Flows ..................................................... 64 Figure 3.10 Total Cost versus Detour Length for Various Alternatives (Q1=200vph, Q2=200vph) ................................................................................................... 66 Figure 3.11 Total Cost versus Detour Length for Various Alternatives (Q1=400vph, Q2=600vph) ................................................................................................... 66 Figure 3.12 Total Cost versus Detour Length for Various Alternatives (Q1=800vph, Q2=600vph) ................................................................................................... 67 Figure 3.13. Total Cost versus Diverted Fraction (Q2=400vph, Ld=6km)........................ 69 Figure 3.14 Total Cost versus Diverted Fraction (Q2=400vph, Ld=12km)....................... 70 Figure 3.15 Optimized Zone Length vs. Q1 ...................................................................... 72 Figure 3.16 User Delay Cost vs. Work Zone Length (Q1=1,000vph, Q2=500vph, Q3=500vph) ................................................................................................... 74 Figure 3.17 Total Cost vs. Work Zone Length (Q1=1,000vph, Q2=500vph, Q3=500vph)75 Figure 3.18 Optimized Work Zone Length vs. Setup Cost (Q1=1,000vph, Q2=500vph, Q3=500vph) ................................................................................................... 75 xi Figure 3.19 Minimized Total Cost vs. Q1 ......................................................................... 77 Figure 3.20 Minimized Total Cost vs. Detour Length (a) Q1=1,000 vph (b) Q1=1,500 vph (c) Q1=2,000 vph .................................................................................................... 78 Figure 3.21 Total Cost vs. Diverted Fraction ................................................................... 79 Figure 4.1 Work Zone Activities under Time-Dependent Inflows................................... 82 Figure 4.2 Duration for Work Zone i with Time-dependent Traffic Inflows ................... 85 Figure 4.3 Queuing Delay and Queue Dissipation for Four-Lane Highway Work Zone. 90 Figure 4.4 Flow Chart of Simulated Annealing Algorithm for Work Zone Optimization ..................................................................................................................... 100 Figure 4.5 Decrease Event .............................................................................................. 101 Figure 4.6 Increase Event ............................................................................................... 101 Figure 4.7 ?Increaseinend? Event ................................................................................... 102 Figure 4.8 ?Increaseinbegin? Event................................................................................ 102 Figure 4.9 ?Decreasinend? Event ................................................................................... 103 Figure 4.10 ?Decreaseinbegin? Event............................................................................. 103 Figure 4.11 ?Checklastzone? Event ................................................................................ 104 Figure 4.12 ?Deletezone? Event ..................................................................................... 105 Figure 4.13 Work Zone Durations .................................................................................. 106 Figure 4.14 Search for Best Project Starting Time ......................................................... 107 Figure 4.15 Hourly Traffic Distributions on Two-Lane Highway and Minimized Total Cost vs. Project Starting Time..................................................................... 110 Figure 4.16 Project Duration vs. Average Cost of Idling Time...................................... 112 Figure 4.17 Number of Zones vs. Average Cost of Idling Time .................................... 115 Figure 4.18 Minimized Total Cost vs. Average Cost of Idling Time ............................. 115 Figure 4.19 Hourly Traffic Distributions on Four-Lane Highway and Minimized Total Cost vs. Project Starting Time..................................................................... 120 Figure 4.20 Project Duration vs. Average Cost of Idling Time...................................... 121 xii Figure 4.21. Minimized Total Costs in 50 Replications (Two-lane Highway) .............. 124 Figure 5.1 Queuing Delay and Dissipation of Queue Length along Detour................... 127 Figure 5.2 Traffic Management Plan Combining Different Alternatives....................... 143 Figure 5.3 SAMASD Algorithm..................................................................................... 145 Figure 5.4 Determining Alternatives and Diverted Fractions in SAMASD................... 146 Figure 5.5 Minimized Total Cost vs. Project Starting Time (Two-lane Highway Work Zones) .......................................................................................................... 149 Figure 5.6 Minimized Total Cost vs. Detour AADT...................................................... 150 Figure 5.7 Minimized Total Cost vs. Project Starting Time (Four-lane Highway Work Zones) .......................................................................................................... 152 Figure 5.8 Minimized Total Cost vs. Detour AADT (a) Project Starting Time: 11:00 (b) Project Starting Time: 21:00 ....................................................................... 154 Figure 5.9 Minimized Total Cost vs. Main Road AADT (Project Starting Time: 11:00) ..................................................................................................................... 155 Figure 5.10 Minimized Total Cost vs. Detour AADT.................................................... 157 Figure 6.1 Types of Multiple Detour Paths for Work Zones.......................................... 165 Figure 6.1 Types of Multiple Detour Paths for Work Zones (continued) ...................... 166 Figure 6.2 Determining Alternatives and Diverted Fractions in SAMAMD.................. 176 Figure 6.3 Evaluation of Work Zone Optimization Model by Simulation ..................... 180 Figure 6.4 Minimized Total Cost vs. Project Starting Time (IS-95, Eight-lane Freeway Work Zones, k=0) (a) Minimized Total Cost Scale: 100,000 ? 2,500,000 (b) Minimized Total Cost Scale: 100,000 ? 210,000........................................ 185 Figure 6.5 Minimized Total Cost vs. Diverted Fraction k (p=0.1, Project Starting Time: 20:00, IS-95, Eight-lane Freeway Work Zones) ......................................... 186 1 Chapter I Introduction 1.1 Background Highway maintenance, especially pavement rehabilitation or resurfacing, requires lane closures. Given the very substantial cost of the maintenance and the very substantial traffic disruption and safety hazards associated with highway maintenance work, it is desirable to plan and manage the work in ways that minimize the combined cost of maintenance, traffic disruptions and accidents. Work zone delays due to highway maintenance have been increasing in the U.S (Federal Highway Administration (FHWA), 2000). The aging highway system in the U.S. is undergoing extensive of reconstruction and maintenance in recent years. According to the FHWA (Wunderlich, 2003), 13 percent in 2001 and 20 percent in 2002 of the National Highway System (NHS) were under construction during the peak summer road work season and work zones on the NHS resulted in a loss of over 60 million vehicles of capacity per day. The number of persons killed in motor vehicle crashes in work zones has risen from 693 fatalities in 1997 to 1,181 fatalities in 2002 (an average of 936 fatalities a year) and more than 40,000 people are injured each year as a result of motor vehicle crashes in work zones (Traffic Safety Facts 2002, National Highway Traffic Safety Administration (NHTSA), 2003). Highway maintenance and the management of traffic through or around work zones are important activities. Appropriate traffic management plans can increase the work efficiency and safety and decrease work zone delays. FHWA?s statistics also show that 53 percent of work zones are designated for day work, 22 percent for night work, and 18 percent are active all day or nearly all day (Wunderlich, 2003). However, no comprehensive method has been developed to evaluate whether these work zones are 2 dimensioned and scheduled appropriately, allowing motorists to travel safely and smoothly, and allowing work crews to accomplish their work safely. Therefore, it is worthwhile to develop appropriate work zone analysis methods that can be used to evaluate current work zone plans and to develop better traffic management plans for highway maintenance activities. 1.2 Problem Statement The overall costs of road maintenance and traffic disruption may be very significantly reduced through properly integrated decisions about the conduct and schedule of maintenance activities and the development of appropriate traffic management plans. Several questions should be considered for comprehensive analysis: How long and wide should work zones be? How does the availability of alternate routes and their characteristics (e.g., length, design speed, excess capacity, traffic patterns) influence the above decisions? What fraction of traffic should be diverted to alternate routes? When time-dependent inflows are considered, the analysis becomes more complex. Besides the above questions, the work scheduling, i.e., when the work should be done and how long closures should be last, must also be analyzed. The optimal work zone activities, including the optimized work zone lengths in different periods (day, night, peak period, off-peak period), the preferred starting time and ending time for each zone closure (e.g. terminating work during peak period to avoid to too serious traffic disruption), are also included among the problems considered. When considering time- dependent inflows, traffic management plans combining different alternatives, which 3 have different work zone configurations or diversion, for different periods might be developed and applied to highway maintenance projects. The above questions focus on a single maintained road. Furthermore, when a more complex road network is considered, not only should multiple detour paths be considered, but the scheduling of maintenance activities for roads in a road network must also be determined. Thus, the following two questions will be identified and solved: 1. How should roads and road networks be divided into work zones? 2. How does the effectiveness of various maintenance and traffic management solutions depend on the characteristics of particular road sections and the surrounding network, especially when considering multiple detour paths? Various methods have been previously developed for analyzing some aspects of the above questions. However, no comprehensive method has been previously developed to jointly analyze these questions. This study aims to develop an integrated model as a decision support system to help highway agencies in developing traffic control plans for maintenance activities and in efficiently managing traffic around highway work zones. Work zone models will be developed for three cases: (1) a single maintained road with steady traffic inflows, (2) a single maintained road with time-dependent traffic demands, and (3) a road network with multiple detour paths, as well as plans for maintenance activities and managing traffic around highway work zones. 4 1.3 Research Objectives The objective of this research is to develop an evaluation and decision support model for highway maintenance planning and traffic management. This research is intended to: 1. Identify feasible alternatives of work zone activities for various traffic control strategies and evaluate in detail their costs and other effectiveness measures for three different cases, namely, (1) steady traffic inflows, (2) time-dependent inflows, and (3) a road network with multiple detour paths. 2. Optimize the work zone characteristics to minimize the combined total costs for highway agencies and users. 3. Develop scheduling strategies and traffic management plans for the above three cases. 1.4 Research Scope and Tasks Based on highway configuration, the scope of this study will cover (1) two-lane two-way highway work zones and (2) multiple-lane two- way highway work zones. Based on traffic flow patterns, the scope will cover (1) steady traffic inflows and (2) time- dependent inflows. Based on detour type, the methods will cover (1) a single detour and (2) multiple detour paths. The research tasks include the following: Classification of highway configuration and identification of possible work zone closure alternatives 5 Development of work zone cost functions and an analytical optimization method for a single maintained road and a single detour with steady traffic inflows Development of work zone cost functions and optimization models (based on analytic method and Simulated Annealing algorithm) for a single maintained road and a single detour with time-dependent inflows Development of work zone cost functions and optimization models using analytic method, Simulated Annealing algorithm, and simulation model for a road network with multiple detour paths Development of appropriate traffic management plans combining different alternatives for all the cases analyzed Figure 1.1 shows a flow chart for the tasks in this study. 1.5 Technical Approach The objective of the work zone optimization problem is to minimize the total cost for work zone activities. The objective function for work zone activities can be expressed as follows: Min CT=CM+CU where CT is total cost, CM is maintenance cost, or supplier cost, and CU is user cost. The controllable variables affecting CM include work zone length, fixed setup cost, and average maintenance cost per unit length; the controllable variables affecting CU include work zone length, traffic volumes, speed, diverted fraction (if detour is available), etc. Both CM and CU are functions of work zone length since CM and CU are significantly influenced by work zone size. 6 Identify Highway Type and Work Zone Alternatives Development of Work Zone Cost Function with Steady Traffic Flows Optimization of Work Zones with Steady Traffic Flows Development of Work Zone Cost Function with Time Dependent Inflows Optimization of Work Zones with Time Dependent Inflows Development of Work Zone Cost Function in a Road Network Optimization of Work Zones in a Road Network Development of Traffic Management Plans for Work Zones Case 1 Steady Traffic Flow + Single Detour Case 2 Time Dependent Inflow + Single Detour Case 3 Road Network + Multiple Detours Figure 1.1 Research Flow Chart 7 To ta l c o st CM CT Work Zone Length CU L* Key: CM = Maintenance Cost CU = User Cost CT = Total Cost Figure 1.2 Conceptual Effect of Work Zone Length on Total Cost, Maintenance Cost, and User Cost Chien et al (2001, 2002) proposed that longer zones tend to increase the user delays, but the maintenance activities can be performed more efficiently with fewer repeated setups in longer zones. Since work zones lengths and maintenance duration affect maintenance and user cost, it is important to determine the tradeoffs between maintenance cost and user cost in order to minimize total cost, as shown in Figure 1.2. Maintenance cost usually includes labor cost, equipment cost, material cost and traffic management cost. The first step in estimating maintenance cost is to determine construction quantities/unit prices. Unit prices can be determined from highway agencies historical data on previously bid jobs of comparable scale (Wall, 1998). In this study, the cost of maintaining cost of length L is assumed to be a linear function of the form CM=z1+z2L, in which z1 represents the fixed cost for setting up a work zone and z2 is the average additional maintenance cost per work zone unit length. 8 In this study user cost includes user delay cost and accident cost. The user delay can be classified into queuing delay and moving delay (Cassidy and Bertini, 1999, Schonfeld and Chien, 1999, Chien and Schonfeld, 2001). The user delay cost is determined by multiplying the user dealy by the value of user time (Wall, 1998). The accident cost is related to the historical accident rate, delay, work zone configuration, and average cost per accident. Chien and Schonfeld (2001) determined accident cost from the number of accidents per 100 million vehicle hours multiplied by the product of the user delay and average cost per accident and then divided by work zone length. The proposed methodology includes the development and application of mathematical models for a single maintained road with steady traffic inflows, with time- dependent inflows, and finally, for a road network with multiple detour paths. The optimization approach is to formulate a total cost function, including agency cost (or maintenance cost) and user cost, and to find the work zone lengths and diversion fraction (if detour(s) is (are) available) which minimize that total cost function. Analytical solutions for optimized work zone lengths and diversion fraction are found. For cases where analytical solutions are impractical for time-dependent inflows and multiple detour paths, a heuristic algorithm is developed to find the optimized work zone lengths for each zone, zone start and end time, and the number of zones to minimize the total cost. 1.6 Organization of Dissertation In this dissertation, previous studies are reviewed and summarized in Chapter 2. Work zone optimization models for steady traffic inflows are formulated and optimized analytically for two-lane and four-lane highway work zones in Chapter 3. Guidelines for 9 selecting the best alternative for different characteristics of traffic flows, road and maintenance processes are developed by threshold analysis. In Chapter 4, the work zone optimization models for time-dependent inflows are developed. Two optimization methods, Powell?s and Simulated Annealing, are adapted for this problem and compared. The reliability of the Simulated Annealing algorithm is also tested. In Chapter 5 are developed the work zone optimization models of four alternatives for two-lane highway and four alternatives for four-lane highway work zones with time-dependent inflows. The SAUASD (Simulated Annealing for Uniform Alternatives with a Single Detour) algorithm is developed to find the best single alternative within a maintenance project. The SAMASD (Simulated Annealing for Mixed Alternatives with a Single Detour) algorithm is developed to search through possible mixed alternatives and diverted fractions in order to further minimize total cost. Thus, traffic management plans with uniform alternatives or mixed alternatives within a maintenance project are developed. In Chapter 6, work zone optimization models for a road network with multiple detour paths and SAMAMD (Simulated Annealing for Mixed Alternatives with Multiple Detour paths) algorithm are developed. For analyzing traffic diversion through multiple detour paths in a road network, the SAMAMD algorithm is used to optimize work zone lengths and schedule the resurfacing work. Analyses based on the CORSIM simulation, developed by the Federal Highway Administration, are used not only to estimate delay cost, but also to evaluate the effectiveness of optimization models. Finally, conclusions about this work and the opportunities for future research are discussed in Chapter 7. Table 1.1 shows which cases and models are developed in various sections of this dissertation. 10 Table 1.1 Organization of Dissertation Traffic Pattern Detour Type Methodology Traffic Management Plan Chapter Case Steady Traffic Inflows Analytical Method Chapter 3 Case 1 SAUASD UA Chapter 4, 5SD SAMASD MA Chapter 5 Case 2 SAUAMD UA SAMAMD Time-Dependent Inflows MD Simulation MA Chapter 6 Case 3 SA: Simulated Annealing UA: Uniform Alternatives MA: Mixed Alternatives SD: Single Detour MD: Multiple Detour Paths 11 Chapter II Literature Review The literature review consists of several sections. The first section identifies and summarizes the main issues for the analysis of work zones. The second section focuses on the work zone cost items that are important and sensitive to work zone configurations. Research trends for work zones and optimization algorithms are then discussed. 2.1 Work Zone Issues Work zone studies have considered various aspects of work zone configurations. Work zone issues include (1) capacity estimation for work zones, (2) work zone travel speed estimation, (3) delay estimation, (4) maximum queue length estimation, (5) work zone safety models, (6) optimization of work zone lengths, (7) scheduling of work zone activities, (8) resurfacing procedures, and (9) work zone cost estimation. The main variables considered in these studies are traffic volumes, work zone capacity, availability of alternate roads, road types, work zone configurations, work zone length, work time, and work intensity. These issues are directly related to the development of cost functions for analyzing work zones. Capacity estimation and work zone travel speed estimation are issues that many early work zone studies have focused on. Delay estimation and queue length estimation methods have been developed and used to analyze traffic disruptions and to determine the maximum feasible work intensity. Recently, work zone studies have sought to develop safety models that can predict the frequencies of accidents according to work zone configurations. 12 Optimizing work zone lengths is an important issue that has been relatively neglected. In general, longer zones tend to increase the user delays, but the maintenance activities can be performed more efficiently (i.e., with fewer repeated setups) in longer zones (Schonfeld and Chien, 1999). Such lengths have been usually designed to minimize costs for highway agencies and users. Meanwhile, highway agencies have developed associated regulations to design work zone configurations to improve workers? and users? safety. Related regulations about scheduling maintenance work have also been developed to enhance public awareness and to decrease traffic disruption in peak periods. Highway maintenance issues concern transportation engineers, structural engineers and construction management engineers, with different groups focusing on different aspects. 2.2 Work Zone Cost Items Work zone costs may be classified into two categories: (1) agency costs and (2) user costs. Agency costs are those expenses required to finish the work zone activities based on the work types. Those normally include labor costs, equipment costs, material costs and traffic maintenance costs. Meanwhile, user costs can be classified into (1) user delay costs and (2) safety (accident) costs. Since delays and accidents due to work zone activities are very important in optimizing work zone lengths and schedules, researchers have tried several methods to properly estimate the user delay and safety costs (McCoy and Peterson, 1987; Schonfeld and Chien, 1999; Venugopal and Tarko, 2000; Chien and Schonfeld, 2001; 13 and Chien et al., 2002). User costs have received such attention in work zone analysis because they tend to dominate other costs and because community concerns and reactions to work zone activities affect many aspects of work zone decisions. 2.3 Research Trends 1. Work Zone Capacity Krammes and Lopez (1994) provided recommendations for estimating the capacity of the remaining lanes during short-term lane closures based on 45-hour capacity counts between 1987 and 1991 at 33 Texas freeway locations with work zones. Adjustments were suggested for the effects of the intensity of work zone activities, percentage of heavy vehicles in the traffic stream, and presence of entrance ramps near the beginning of a lane closure. Dudek and Richards (1982) presented more detailed information based on field data analysis for estimating road capacity during maintenance work. They considered lane closure strategies and obtained cumulative distribution of observed work zone capacities. In a later study (Dudek et al., 1986), they estimated capacities for work zones on four-lane highways. Memmott and Dudek (1984) used a regression model to estimate the mean capacity for a work zone. The advantage of using the regression model was that most lane closure types were covered and the restricted capacity used for traffic management purposes could be estimated. However, they only used a capacity estimation risk factor as a variable instead of specifying other possible geometric variables. Kim and Lovell (2001) developed a multiple regression model to estimate capacity in work zones in order to establish a functional relationship between work zone capacity and several key 14 independent factors, including the number of closed lanes, the proportion of heavy vehicles, grade and the intensity of work activities. 2. Speed and Delay Since the travel delays of roadway users in a work zone are the primary determinant of user delay cost, studies related to speed and delay analysis for work zones have been reviewed. In a study of traffic characteristics on Illinois freeways with lane closures, Rouphail and Tiwari (1985) evaluated the effects of intensity and location of construction and maintenance activities on mean speeds through a work zone. The results showed that the mean speeds through a work zone decrease as the intensity of construction and maintenance activities increase. The mean speeds also decrease as the construction and maintenance activities move closer to the travel lanes. Pain et al. (1981) provided a detailed study of speeds in work zones. The mean speeds were found to vary depending on such factors as traffic volumes (e.g., in peak and off-peak hours), lane closure configurations (e.g., right lane closure, left lane closure, and a two-lane bypass), traffic control devices (e.g., cones, tubular cones, barricades, and vertical panels) and locations within work zones. Rouphail et al. (1988) derived various mean values and coefficients of variation to describe the speed change in work zones. They found that the average speed does not vary considerably at light traffic volumes and that the speed recovery time is longer at high traffic volumes. Their results also indicated that speed control has a very important role in reducing accident frequency. Memmott and Dudek (1984) developed a computer model, called Queue and User Cost Evaluation of Work Zone (QUEWZ), to estimate the average speed in work zones 15 and calculate user costs, including user delays costs and vehicle operating costs. The effects of different lane-closure strategies and the number of hours available for lane closures are determined based on an assumed lane capacity and various traffic volumes. However, that model does not consider any alternate path and the effect of diverting traffic to it. Jiang (1999) developed a traffic delay model to estimate work zone delay costs based on traffic data collected at work zones on Indiana?s freeways. The delays related to work zones were classified into four categories: (1) deceleration delay by vehicle deceleration before entering a work zone, (2) moving delay by vehicles passing through work zones with lower speed, (3) acceleration delay by vehicle acceleration after exiting work zone, and (4) queuing delay caused by the ratio of vehicle arrival and discharge rates. In addition to the user delay generalized as queuing delay and moving delay considered by others (Cassidy and Bertini, 1999, Schonfeld and Chien, 1999, Chien and Schonfeld, 2001), Jiang also considered deceleration and acceleration delays to users. 3. Delay and Queue Length Cassidy and Han (1994) used empirical data to estimate vehicle delays and queue lengths on two-lane highways operating under one-way traffic control. However, the work zone length was not optimized in that study. Jiang (2001) developed a queue estimation method to calculate traffic delay using queue-discharge rates instead of work zone capacity because author noted that queue- discharge rates are lower than work zone capacity (Jiang, 1999). 16 4. Models for Optimizing Work Zone Length and Safety McCoy et al. (1980) developed a method to optimize the work zone length by minimizing the road user and traffic control costs in construction and maintenance zones of rural four-lane divided highways. This method provided a framework for optimizing the lengths of work zones by minimizing the total costs, including construction costs. The user delay costs were modeled based on average daily traffic (ADT) volumes, while the accident costs were computed by assuming that the accident rate per vehicle mile was constant in a work zone area. The optimal work zone length was derived based on 1979 data. Because the unit cost factors had changed considerably since 1981, McCoy and Peterson (1987) found the optimum work zone lengths to be about 64% longer that those used previously. They (1987) also conducted a safety study for various lengths of work zones on four-lane divided highways. No relation was found between the lengths of work zones and accident rates or any of the speed distribution parameters, such as the standard deviation of vehicle speeds and the range of vehicle speeds. They also found the average accident rate was 30.8 accidents per 100 million vehicle miles (acc/100 mvm) on I-80 in Nebraska between 1978 and 1984. Considering traffic safety in construction and maintenance work zones, Pigman and Agent (1990) conducted a statewide work zone analysis. The accident data were collected from the Kentucky Accident Reporting System (KARS) for the 1983-1986 periods. They found that the work zone accident rate varied from 36 to 1,603acc/100 mvm on different highways. Some efforts to mitigate the impacts of work zones have been made by Janson et al (1987). One of such efforts optimized work zone traffic control design and practice 17 considering such aspects as optimal design of control devices, optimal lane closure configuration and optimal work zone length. Martinelli and Xu (1996) added the vehicle queue delay costs into McCoy?s (1980) model. The work zone length was optimized by minimizing the total user cost, excluding the maintenance and accident costs. To estimate the roadway maintenance costs, Underwood (1994) analyzed the work duration and the maintenance cost per 10,000 m2 for five different roadway maintenance activities (i.e., surface dressing, asphalt surface, porous asphalt, 10% patching, and milling out). The average maintenance costs were calculated based on prices quoted to highway authorities in the summer of 1993. Chien and Schonfeld (2001) developed a mathematical model to optimize the work zone lengths on four-lane highways using a single-lane closure approach. The objective of the study was to minimize the total cost including agency cost, accident cost and user delay cost based on two steady traffic inflows. They did not consider alternate paths and assumed uniform traffic flow. Viera-Colon (1999) developed a similar model of four-lane highways which considered the effect of different traffic conditions and an alternate path. However, that study did not develop alternative selection guidelines for different traffic flows or road characteristics. Schonfeld and Chien (1999) also developed a mathematical model to optimize the work zone lengths plus associated traffic control for two-lane, two-way highways where one lane at a time is closed. They found the optimal work zone length and cycle time for traffic control and minimized the total cost, including agency cost and user delay cost, but no alternative routes were considered in that study. 18 5. Scheduling Work Zone Activities Fwa, Cheu, and Muntasir (1998) developed a traffic delay model and used genetic algorithms to minimize traffic delays subject to constraints of maintenance operational requirements. Pavement sections, work teams, and start time and end for each section were scheduled. However, many conditions in that study were given, e.g. work zone configuration and available work duration for each team, and road section length. These variables were not optimized in that study. Chang, Sawaya, and Ziliaskopoulos (2001) used traffic assignment approaches to evaluate the traffic delay caused by work zones and a Tabu Search methodology was employed to select the schedule with the least total traffic delays, which include the impact of work zone combinations on an urban street network. Chang considered impact of network delay for urban areas while Fwa?s research neglected the impact of network delay due to detours. Chien, Tang, and Schonfeld (2002) developed a model to optimize the scheduling of work zone activities associated with traffic control for two-lane two-way highways where one lane at a time is closed. However: (1) the traffic pattern used in that research was simplified into four traffic volumes during four period in a day: morning peak, daytime, evening peak, and nighttime periods, which could not fully reflect the real traffic situation, (2) the search approach to determine each zone length is a greedy method, whose results may be sub-optimal, and (3) the effects of highway networks on work zone characteristics were not considered. Jiang and Adeli (2003) used neural networks and simulated annealing to optimize only one work zone length and starting time for a four-lane freeway, considering factors such as darkness and numbers of lanes 19 closed. More complete scheduling plans for multiple-zone maintenance projects were not attempted in that work. 6. Construction Congestion Cost Carr (2000) developed a construction congestion cost (CO3) system to estimate the impact of traffic maintenance contract provisions on congestion, road user cost, and construction cost. CO3 was implemented in a Microsoft Excel spread sheet and consists of three sheets: (1) route sheet computing equivalent average vehicle routes for complex diversion routes, (2) input sheet providing for documentation of vehicle and route inputs and computing user cost for single trips through the work zone, diversions, and cancellations, and (3) traffic sheet computing daily traffic impacts and user costs for each construction method. Although CO3 provides practical information with which engineers select construction methods, it does not optimize work zone configurations. 7. QuickZone Software for Work Zones The 1998 FHWA report ?Meeting the Customer?s Needs for Mobility and Safety During Construction and Maintenance Operations? recommends the development of an analytical tool to estimate and quantify work zone delays. This scope of work lays out a plan for the development of an easy-to-master analytic tool (currently under the working title "QuickZone") for quick and flexible estimation of work zone delay. The primary functions of QuickZone include quantification of corridor delay resulting from capacity decreases in work zones, identification of delay impacts of alternative project phasing plans, supporting tradeoff analyses between construction costs and delay costs, examination of impacts of construction staging, by location along mainline, time of day 20 (peak vs. off-peak) or season, and assessment of travel demand measures and other delay mitigation strategies. The costs can be estimated for both an average day of work and for the whole life cycle of construction. However, there is no optimization function in Quickzone. The Maryland State Highway Administration and the University of Maryland (Kim and Lovell, 2001) used QuickZone's open source code to customize the program to meet the State's needs. The University has added its own capacity estimation model to the program and has used a 24-hour traffic count, instead of the average daily traffic count found in original version. FHWA and Maryland?s Quickzone versions provide a useful to estimate work zone delay; however, there was still no optimization model in these programs. 8. Simulation Modeling for Work Zones CORSIM (Corridor Simulator) is a microscopic simulation model developed by the Federal Highway Administration (FHWA) and can simulate coordinate traffic operations on surface streets and freeways. Generally, work zone delays occurring in a single road section or simple road network can be derived from deterministic queuing theory; however, with a simulation method such as CORSIM, it is much easier to estimate work zone delays in a more complex road network. Nemeth and Rathi (1985), Cohen and Clark (1996), and Chien and Chowdhury (1998) used CORSIM to study velocity and analyze capacity for freeway operations. CORSIM can be adapted to simulate traffic operations around a work zone by assuming one more lane closure for a work zone as the lane closure caused by an incident. Schrock and Maze (2000) developed 21 a work zone simulation model and used CORSIM to evaluate four alternatives for work zones along Interstate 80 in Iowa. The simulation model was developed as a planning tool to determine the potential benefits of alternative traffic management plans at a long- term work zone. Maze and Kamyab (1999) used ARENA, a simulation model with an advanced animation module, to develop a work zone simulation model, including car-following and lane-changing algorithms, to estimate work zone delays. That study only applied ARENA for a work zone in a single road. No detours or road networks were considered. 2.4 Optimization Algorithms When work zone optimization is based on steady traffic inflows, the optimization result can often be obtained directly with an analytic method. When time-dependent inflows or multiple detour networks are considered, the cost functions will become more complex and thus more complex algorithms are needed for large optimization problems. Optimization techniques such as genetic algorithms (GA), simulated annealing (SA), and tabu search (TS) are widely used in combinatorial optimization problems (COP), where the objective is to choose a best solution out of a large number of possible solution, and obtain very good results in NP-hard combinatorial optimization problems. These three probabilistic heuristic methods share two main characteristics. One is that these three algorithms are inspired by real phenomena in physics, biology, and social science. The other is that they use a certain amount of repeated trials to find the optimal or near optimal solution (Colorni et al., 1996). Pham and Karaboga (2000) found that GA performs better than TS and SA for the traveling salesman problem. Sadek et al. (1999) 22 used SA and GA to solve a dynamic traffic routing problem and found that SA tends to perform better than GA. Nalamottu et al. (2002) compared GA to SA in solving transportation location-allocation problems and found SA to be better than GA in its convergence to exact solutions and its computation time. Zolfaghari and Liang (2002) compared GA, SA, and TS in terms of solution quality, search convergence behavior and presearch effort for solving binary comprehensive machine-grouping problems. Their results indicated that SA outperforms both GA and TS, particularly for large problems. Recently, hybrid methods combining these three algorithms were developed for combinatorial optimization problems (Liu et al., 2000, Adamopoulos et al, 1998). A hybrid method combines the advantages of each algorithm. For example, Liu et al. combined the advantages of GA, SA, and TS to solve the reactive power optimization problem. They adopt the acceptance probability of SA to improve the convergence of the GA, and apply TS to find more accurate solutions. Generally, it is recognized that GA?s are not well suited for finely tuned local search. However, after promising regions of the source space are identified by the GA, it may be useful to invoke a local search routine to optimize the members of the final population (Grefenstette, 1987). SA has been proven effective for the optimal or near- optimal solution for a local regional search (Pham and Karaboga, 2000). Li et al. (2002) used GA to generate a group of initial solutions and then used SA to search the local optimum for solving machine operation process plans. Colorni et al. (1996) concluded that SA has a ?well-defined? advantage with likely lower future developments, and TS and GA have a ?dynamic? advantage with large possibilities of novel research for theories and results. 23 In view of the above literature review, there are two main reasons why SA is applied in this study for work zone optimization problems. First, SA is more completely developed and provides more finely tuned results than other two methods for combinatorial optimization problems. Second, the methodology in Case 1 will be applied to generate the initial solutions for Case 2 and Case 3. From the research flow of this study, the results of Case 1 for steady traffic inflows are the fundamentals of Case 2 for time-dependent inflows and of Case 3 for multiple detour networks. Then SA can be used to seek a global or near global optimum by using the initial solution obtained by the methodology in Case 1. Due to these characteristics, SA will be applied to solve work zone optimization problems in this study. The SA approach was derived from statistical mechanics for finding near optimal solutions to large optimization problems. Simulated annealing was developed by Metropolis (1953) when it was used to simulate the annealing process of crystals on a computer. Kirkpatrick et al. (1983) generalized an approach by introducing a multi- temperature approach in which the temperature is lowered slowly in stages. Kirkpatrick et al. applied this methodology to solve the problems of combinatorial optimization, especially the problems of wire routing and the component placement in VLSI (Very Large Scale Integration) design. SA is sensitive to a number of control parameters and stopping rules (Wilhelm and Ward, 1987). The algorithm has potential to find high-quality solutions but at the cost of substantial computational efforts (Aarts and Korst, 1989). For example, if the initial temperature is too high and the cooling schedule is very slow, the cooling will takes long computational time to approach final temperature. However, it is inefficient even the 24 solution has high quality. If the initial temperature is too low and the cooling schedule is too fast, the solution may not be close to the optimum. Therefore, the cooling schedule should be chosen carefully. SA is widely used in transportation related research. Hadi and Wallace (1994), Oda et al. (1997), and Lee and Machemehl (1997) used SA to solve signal phasing and timing optimization problems. Taniguchi et al. (1999) and Kokubugata et al. (1997) applied SA to find optimal assignment for vehicle routing and scheduling problems. Chang (1994) used SA to solve flight sequencing and gate assignment problems. For the work zone optimization problem, Jiang and Adeli (2003) used neural networks and simulated annealing to optimize work zone length and starting time for a four-lane freeway. Only one zone length and starting time are optimized in that study. More complete scheduling plans for multiple-zone maintenance projects are needed in practice. 2.5 Summary After a review the above studies, it appears that work zone capacity, delays, work zone length, and costs have already been developed for steady traffic inflows and partially for time-dependent inflows. However, further research on work zone optimization with detours, including a single detour and multiple detour paths, for both steady and time-dependent inflows is quite necessary and important for the development of practical work zone project scheduling and traffic management plans. Some analytical and heuristic methods were proposed for solving work zone optimization problems in the above studies; however, those studies did not present 25 complete results for steady and time-dependent inflows, with and without detour(s). No comprehensive method has been previously developed to jointly analyze the work zone optimization problem. Therefore, this study will focus on the work zone optimization methods for steady and time-dependent inflows with a single detour and with multiple detour paths. 26 Chapter III Work Zone Optimization for Steady Traffic Inflows In this chapter, work zone optimization models for steady traffic inflows are developed for two-lane highway and four-lane highway work zones. The highway system and various work alternatives are defined in Section 3.1. Analytical optimization models are developed for two-lane highway and four-lane highway work zones in Sections 3.2 and 3.3. Sections 3.4 and 3.5 show the speeds along work zones and detours are determined and how the threshold analysis is conducted. Finally, numerical results for two-lane and four-lane highways are shown in Sections 3.6 and 3.7. 3.1 Highway System Definition In this study highway types are classified into two-lane two-way highways and multiple-lane two-way highways. Two-lane two-way highways often require closing one lane for a work zone. In such circumstances, vehicles travel in the remaining lane along the work zone, alternating direction within each control cycle. Such a two-lane work zone can be considered as a one-way traffic control system in which queuing and delay processes are analogous to those at a two-phase signalized intersection. Pavement maintenance on multiple-lane two-way highways often requires closing one or two lanes to set up a work zone. This does not require alternating one-way control as in a two-lane highway work zone because at least one lane is usually still available in the direction of closure. Because work zones in two-lane highways and multiple-lane highways have different delay and queuing patterns, the work zone cost functions are separately developed. 27 Several work zone alternatives of two-lane highways and multiple-lane highways are demonstrated as follows: 1. Two-Lane Two-Way Highway Work Zone Schonfeld and Chien (1999) analyzed the effect of longer work zones and cycle times in increasing the user delay and decreasing the total maintenance time and costs due to fewer setups for fewer zones. Note that this case in which traffic flows from both directions are alternated on one lane, without any detour, is considered the first alternative for two-lane roads, labeled Alternative 2.1. The geometries of all alternatives are shown in Figure 3.1. In the second alternative, we consider the best available alternate route that bypasses the work zone area, so that the original traffic flow on the road is divided between the flow passing along the work zone and the flow through the detour. Thus, in the second alternative considered, the remaining lane is still used for alternating two-way traffic, but traffic from the maintained road also can use the alternate route. In the third alternative all traffic in one direction is diverted to the alternate route, while the remaining lane is only used for traffic in the other direction. Thus, the diverted traffic percentage from one direction of the main road is 0% in Alternative 2.1, 100% in Alternative 2.3 and somewhere between those extremes in Alternative 2.2. In Alternative 2.4, all traffic in both directions is diverted to the alternate route and both lanes are closed for work. The preferred alternative can be determined after evaluating all four alternatives. 28 L Q3 Q1 Q2 Q4 (a) Alternative 2.1: without Detour L L2L1 Ld2 Ld1 Ld3 Q3 Q1 Q2 Q4 pQ1 (1-p)Q1 Q3+pQ1 pQ1 A B (b) Alternative 2.2: with Detour; pQ1 on Detour, (1-p)Q1 along Work Zone L L2L1 Ld2 Ld1 Ld3 Q3 Q1 Q2 Q4 Q1 Q3+Q1 Q1 A B (c) Alternative 2.3: Detour for Only One Direction L L2L1 Ld2 Ld1 Ld3 Q3 Q1 Q2 Q4Q1 Q3+Q1 Q1 A B Q2Q2 Q4+Q2 (d) Alternative 2.4: Two Directions Detoured Figure 3.1 Geometries of Analyzed Work Zones for Two-Lane Two-Way Highways 29 2. Multiple-Lane Two-Way Highway Work Zone Pavement maintenance on multiple-lane, two-way highways usually requires closing one or two lanes to set up a work zone. Chien and Schonfeld (2001) developed a work zone cost function (accounting for user delays, accidents, and agency costs) for four-lane two-way highways without considering detours. That case in which one of the two lanes in one direction is closed, without any detour, is considered Alternative 4.1, as shown in Figure 3.2(a). Here, four-lane highways are classified as ?multiple-lane? highways. Here we consider the best available alternate route that bypasses the work zone area, so that the original flow, Q1, in Direction 1 on the road is divided between the flow passing along the work zone and the flow through the detour, as shown in Figure 3.2(b). Thus, in Alternative 4.2 one lane in Direction 1 is closed, while the remaining lane in Direction 1 is still usable, but traffic in Direction 1 can also use the alternate route. In Alternative 4.3 all traffic in Direction 1 is diverted to the alternate route since both lanes are closed, as shown in Figure 3.2(c). Thus, the diverted traffic percentage from Direction 1 is 0% in Alternative 4.1, 100% in Alternative 4.3 and somewhere between those extremes in Alternative 4.2. In Alternative 4.4, both lanes in Direction 1 are closed for a work zone and all traffic in Direction 1 crosses over to one lane in the opposite direction, as shown in Figure 3.2(d). The preferred alternative can be again determined here after evaluating all four alternatives. In this chapter a methodology is proposed for minimizing the total cost, including agency cost, user delay cost, and accident cost, and to optimize the work zone length for each alternative, while considering the best available alternate route that bypasses the 30 work zone. Guidelines for determining the best alternative for different conditions of traffic flow, road characteristics (i.e. detour length, the distance of main road between the beginning and end of detour) and maintenance characteristics (i.e. maintenance setup cost, average maintenance time per kilometer) are developed in the following sections by deriving the minimum cost thresholds between pairs of alternatives with respect to key variables. 3.2 Work Zone Optimization - Two-Lane Two-Way Highway The basic method followed here for tow-lane two-way highway and four-lane two-way highway is to formulate a total cost objective function and use it to optimize work zone lengths at work zones for four alternatives. The queuing delays to users are formulated with deterministic queuing models. Then thresholds among alternatives are derived with respect to key variables, to determine the best alternative for different conditions of traffic flow, road characteristics and maintenance characteristics. 3.2.1 Alternatives and Assumptions The following four alternatives are considered for two-lane two-way highways in this study: 1. Alternating flow on one lane, without any detour 2. Alternating flow on one lane, with a detour 3. One-directional flow on one lane along work zone; other direction on detour 4. Both directions detoured and both lanes closed for work 31 L Q3 Q1 Q4 Q2 (a) Alternative 4.1: No Detour, One of the Two Lanes closed for Q1 Traffic L Q3 Q1 Q4 Q2 Ld2 Ld1 Ld3 pQ1 (1-p)Q1 pQ1 Q3+pQ1 A B (b) Alternative 4.2: A Fraction of Q1 Traffic through Detour L Q3 Q1 Q4 Q2 Ld2 Ld1 Ld3 Q1 Q1 Q3+Q1 BA (c) Alternative 4.3: All Q1 through Detour, Allowing Work Zone on Both Lanes in Direction 1 L Q3 Q1 Q4 Q2 (d) Alternative 4.4: Crossover of All Q1 into One Lane in Opposite Direction, Allowing Work Zone on Both Lanes in Direction 1 Figure 3.2 Geometries of Analyzed Work Zones for Four-Lane Two-Way Highways 32 The geometries of these four cases are shown in Figure 3.1. Several simplifying assumptions made in formulating this problem are listed below. 1. Traffic moves at a uniform speed through a work zone and at a different uniform speed elsewhere. 2. The effects on speeds of the original detour flows on the relatively short Ld1 and Ld3 in Figures 3.1 are negligible. 3. Queues in both directions will be cleared within each cycle for two-lane two-way highways. Thus, the one-lane work zone capacity exceeds the combined flows of both directions. 4. Possible signal or stop sign delays on the detour in Alternatives 2.2, 2.3, and 2.4 may be neglected. 5. Queue backups to the maintained road along the first detour Ld1 may be neglected. 6. The detour capacity always exceeds the original detour flow plus diverted flow, so queue delay on the detour may be neglected. 7. The value of user time used in numerical analysis is the weighted average cost of driver and passenger?s user time for cars and trucks. In this study vehicle operation costs are not considered separately but may be accounted for in the value of user time. 3.2.2 Model Formulation Work zone cost functions of four alternatives for two-lane highways are formulated in this section. Alternative 2.1 is based on the study by Schonfeld and Chien 33 (1999) but the model is modified by adding moving delay cost along work zone and accident cost. Other alternatives, Alternatives 2.2, 2.3, and 2.4, are developed here as extensions of Alternative 2.1 by considering an alternate route. Alternative 2.1: Flow on one lane without detour Schonfeld and Chien (1999) developed a work zone cost function which includes user delay cost and maintenance cost: UMT CCC += (3.1) where CT = total cost per lane-kilometer; CM = maintenance cost per lane-kilometer; CU = user delay cost per lane-kilometer. The user delay cost consists of the queuing delay costs due to a one-way traffic control and the moving delay costs through work zones. The queuing delay cost Cq per maintained lane-kilometer is the total delay per cycle Y in both directions multiplied by the number of cycles N per maintained lane-kilometer and the users? value of time v (in $/veh-hr): Cq = Ynv (3.2) where Y = summation of the delays (e.g., Y1 and Y2) incurred by the traffic flows from directions 1 and 2 per cycle. Y1 and Y2 can be derived by using deterministic queuing analysis. Schonfeld and Chien (1999) formulated the zone delay cost without any alternate route around the work zone and obtained the following relation: )QQ H 3600(V v)]Q H 3600(Q)Q H 3600(Q)[Lzz( C 21 221143 21 q  ++ = (3.3) 34 where C 21q = queuing delay cost per lane-kilometer for Alternative 2.1; z3 = setup time; z4 = average maintenance time per lane-kilometer; L = work zone length; Q1 = hourly flow rate in Direction 1; Q2 = hourly flow rate in Direction 2; H = average headway; V = average work zone speed; v = value of user time; and z3+z4L represents the maintenance duration per zone. Eq.(3.3) represents the queuing delay cost due to one-way traffic control, as proposed by Schonfeld and Chien (1999). Here we consider moving delay cost through work zone. The moving delay cost of the traffic flows Q1 and Q2, denoted as 21vC , is the cost increment due to the work zone. It is equal to the flow (Q1 + Q2) multiplied by: (1) the average maintenance duration per kilometer, 43 zL z + , (2) the travel time difference over zone length with the work zone, V L , and without the work zone, 0V L , and (3) the value of time, v. Thus: v) V L V L)(z L z)(QQ(C 0 4 3 21 21 v ++= (3.4) where V0 represents the speed on the original road without any work zone. The user delay cost for Alternative 1 C 21U is equal to the sum of queue delay cost 21 qC and moving delay cost 21vC . The accident cost incurred by the traffic passing the work zone can be determined from the number of accidents per 100 million vehicle hours na multiplied by the product of the increasing delay ( 21qC /v + 21vC /v) and the average cost per accident va (Chien and Schonfeld, 2001). The average accident cost per lane-kilometer 21aC is formulated as: 35 8 aa 0 4 3 21 21 221143 21 a 10 vn)] V L V L)(z L z)(QQ( )QQ H 3600(V )]Q H 3600(Q)Q H 3600(Q)[Lzz( [C +++  ++ = (3.5) The maintenance cost per zone is assumed to be z1+z2L, where z1 = fixed setup cost; and z2 = average maintenance cost per additional lane-kilometer. The average maintenance cost per lane-kilometer, CM, is the total maintenance cost per zone divided by the zone length L: 2 1 21 /)( zL zLLzzCM +=+= (3.6) Then the total cost for Alternative 2.1,C 21T , is 21a21UM CCC ++ . Its optimized work zone length of Alternative 1, L*21, obtained by setting the partial derivative of the total cost function C 21T with respect to L equal to zero and solving for L, is: ) V 1 V 1(z)QQ( )QQ H 3600(V )]Q H 3600(Q)Q H 3600(Q[z 10 vn v z L 0 421 21 22114 8 aa 1 21* ++  + + = (3.7) The second derivative of C 21T with respect to L is positive in this case and the following ones, indicating that function is convex and has a unique global minimum for L. Alternative 2.2: Flow on one lane as well as a detour It is assumed in Alternative 2.2 (Figure 3.1(b)) that the fraction p of the flow Q1 in Direction 1 is diverted to the alternate route. Then the user queuing delay cost of the remaining flow in Direction 1, (1-p)Q1, and Q2, denoted as C 22q , has the same formulation as Eq.(3.3) but with (1-p)Q1 substituted for Q1. 36 )QQ)p1( H 3600(V v)]Q H 3600(Q)Q)p1( H 3600(Q)p1)[(Lzz( C 21 221143 22 q  ++ = (3.8) The user moving delay cost of the remaining traffic flow in Direction 1, (1-p)Q1, and Q2, denoted as 22 2)p1(vC  , is the cost increment due to the work zone. It has the same formulation as Eq.(3.4) but with (1-p)Q1+Q2 substituted for Q1+Q2. v) V L V L)(z L z)(QQ)p1((C 0 4 3 21 22 2)p1(v ++= (3.9) The user moving delay cost of the diverted flow pQ1 from Direction 1, denoted as 22 vpC , is equal to the flow pQ1 multiplied by: (1) the average maintenance duration per kilometer, 43 zL z + , which is the maintenance duration per zone, z3+z4L, divided by work zone L, (2) the time difference between the time vehicles through the detour, 3* d 2d 0 3d1d V L V LL + + , and the time vehicles through the maintained road AB without work zone, 0V Lt , and (3) the value of time, v. Thus: v] V L V L V LL)[z L z(pQC 0 t 3* d 2d 0 3d1d 4 3 1 22 vp +++= (3.10) where Ld1, Ld2, Ld3 are the lengths of the first, second and third segments of the detour shown in Figure 3.1. V0 represents the speed on the maintained road without any work zone and 3*dV is the detour speed affected by diverted traffic in Direction 3 in Alternative 2.2. Both speeds are computed with Eq.(3.81), derived below in Section 3.5. In addition to delay costs of flows remaining on the maintained road, the moving delay cost to the original flow on the detour, Q3, as affected by the pQ1, is also 37 considered. Denoted as 223vC , it equals the flow Q3 multiplied by: (1) the average maintenance duration per kilometer, 43 zL z + , (2) the travel time difference over Ld2 with the diverted flow pQ1, 3* d 2d V L , and without it, 0 2 d d V L , and (3) the value of time, v. Thus: v) V L V L)(z L z(QC 0d 2d 3* d 2d 4 3 3 22 3v += (3.11) where Vd0 represents the original speed on Ld2 unaffected by pQ1. The combined user delay cost for the maintained road AB and the detour can be derived as: 22 3v 22 vp 22 2)p1(v 22 q 22 CCCCC U +++=  (3.12) The accident cost per maintained kilometer for, 22 aC , is: 8 aa 22 3v 22 vp 22 2)p1(v 22 q22 a 10 vn v )CCCC( C +++ =  (3.13) Then the total cost for Alternative 2.2, C 22T , is 22a22UM CCC ++ . Its optimized work zone length L*22 is obtained by setting the partial derivative of C 22T with respect to L equal to zero and then solving for L. This yields: ) V 1 V 1(z]QQ)p1[( )QQ)p1( H 3600V( )]Q H 3600(Q)Q)p1( H 3600(Q)p1[(z ) V L - V L(zQ) V L V LLL(zpQ 10 vn v z L 0 421 21 22114 d0 d2 3* d d2 333* d d2 0 t3dd1 31 8 aa 1 22* ++  + ++ + + + = (3.14) The second derivative of C 22T with respect to L is also positive in this case and the following ones, indicating that function is convex and has a unique global minimum for L. 38 Alternative 2.3: One direction along the work zone and the other detoured Here it is assumed that the entire flow Q1 in Alternative 2.1 is diverted to the alternate route. Then the user moving delay cost in Direction 1, denoted as C 231v , has the same formulation as Eq. (3.10) but with Q1 substituted for pQ1. v] V L V L V LL)[z L z(QC 0 t 3* d 2d 0 3d1d 4 3 1 23 1v +++= (3.15) The user moving delay cost of the traffic flow Q2, denoted as 232vC , is the cost increment due to the work zone. It is equal to the flow Q2 multiplied by: (1) the average maintenance duration per kilometer, 43 zL z + , (2) the time difference over section AB (in Figure 3.1(c)) with the work zone, V L V LL + + 0 21 , and without the work zone, 0V Lt , and (3) the value of time, v. Thus: v) V L V L)(z L z(Q v) V L V L V LL)(z L z(QC 0 4 3 2 0 t 0 21 4 3 2 23 2v += +++= (3.16) The moving delay cost 233vC of the original flow Q3 in Direction 3, as affected by the Q1, is also considered. It has the same formulation as Eq. (3.11) but 3*dV is affected by pQ1 in Alternative 2.2 and by Q1 in Alternative 2.3. v) V L V L)(z L z(QC 0d 2d 3* d 2d 4 3 3 23 3v += (3.17) The total user delay cost including original road and detour can be determined as follows: 23 3v 23 2v 23 1v 23 CCCC U ++= (3.18) 39 where 23UC = user delay cost per kilometer per lane for Alternative 2.3. The accident cost per maintained kilometer for, 23 aC , is: 8 aa 23 3v 23 2v 23 1v23 a 10 vn v )CCC(C ++= (3.19) Then the total cost for Alternative 2.3, C 23T , is 23a23UM CCC ++ . Its optimized work zone length 23*L is then found to be: ) 10 vn(v) V 1 V 1(zQ ) 10 vn)](v V L - V L(zQ) V L V LLL(zQ[z L 8 aa 0 42 8 aa d0 d2 3* d d2 333* d d2 0 t3dd1 311 23* + +++ + + = (3.20) Because the second derivatives L/C 221T  , L/C 222T  , L/C 223T  of all three objective functions C 21T ,C 22T and C 23T are positive, those functions are convex and 21*L , 22*L and 23*L are global optima. Alternative 2.4: Both directions detoured and both lanes closed for work Here it is assumed that the entire flows Q1 and Q2 are diverted to the alternate route as both lanes between A and B are entirely closed for maintenance. Then the user moving delay cost in Direction 1, denoted as 241vC , has the same formulation as Eq.(3.9) but with Q1 substituted for pQ1. v] V L V L V LL)[z L z(QC 0 t 3* d 2d 0 3d1d 4 3 1 24 1v +++= (3.21) The user moving delay cost of the flow Q2, denoted as 242vC , has the same formulation as Eq.(3.21) but with Q2 substituted for pQ 1 and with 4*dV substituted for 3dV * . v] V L V L V LL)[z L z(QC 0 t 4* d 2d 0 3d1d 4 3 2 24 2v +++= (3.22) 40 where 4*dV is the detour speed in Direction 4 affected by Q2. The moving delay cost 243vC of the original flow Q3 in Direction 3, as affected by the Q1, is also considered. It has the same formulation as Eq.(3.17): v) V L V L)(z L z(QC 0d 2d 3* d 2d 4 3 3 24 3v += (3.23) Similarly, the delay cost 244vC of the original flow Q4 in Direction 4, as affected by the Q2, is considered as well. It has the same formulation as Eq.(3.23) but with Q4 substituted for Q3 and 4*dV substituted for 3dV * . v) V L V L)(z L z(QC 0d 2d 4* d 2d 4 3 4 24 4v += (3.24) It is assumed here that Q3 and Q4 are equal so that the original detour speeds for Direction 3 and 4 are equal, Vdo, Those speeds, Vdo, will be derived in Eq.(3.81). The accident cost per maintained kilometer for, 24 aC , is: 8 aa 24 4v 24 3v 24 2v 24 1v24 a 10 vn v )CCCC(C +++= (3.25) The total user delay cost 24UC can be determined as follows: 24 a 24 4v 24 3v 24 2v 24 1v 24 CCCCCC U ++++= (3.26) Because Alternative 2.4 is a two-lane maintenance work zone, the maintenace cost for Alternative 2.4 differs from that of other one-lane alternatives. Here we define the parameter  to be a reduction factor that is equal to the maintenance cost for two lanes divided by the maintenance cost for one lane. It allows for the possibility that resurfacing cost per lane-kilometer may decrease when two adjacent lanes are resurfaced together. The maintenace cost per lane-kilometer is equal to the maintenance cost per 41 zone z1+z2L multiplied by  (for two-lane maintenance cost), and divided by (1) zone length L, (2) number of lanes, 2. The maintenance cost CM is: )z L z( 2 1C 21M +=  (3.27) In the numerical examples of this study,  is assumed to be equal to 2. Then the total cost for Alternative 2.4, C 24T , is CC 24UM + . The first and second partial derivatives of CT4 are then found to be: 0)v] V L - V L( L zQ)v V L - V L( L zQ )v V L - V L V LL( L zQ)v V L - V L V LL( L zQ L z[ L C d0 d2 4* d d2 2 34 d0 d2 3* d d2 2 33 0 t 4* d d2 0 3dd1 2 32 0 t 3* d d2 0 3dd1 2 31 2 1 24 T <+ ++ + ++ + +=  (3.28a) 0)v V L - V L( L zQ2)v V L - V L( L zQ2 )v V L - V L V LL( L zQ2)v V L - V L V LL( L zQ2 L z2 L C d0 d2 4* d d2 3 34 d0 d2 3* d d2 3 33 0 t 4* d d2 0 3dd1 3 32 0 t 3* d d2 0 3dd1 3 31 3 1 2 24 T 2 >+ ++ + ++ + +=  (3.28b) The first partial derivative of C 24T is negative and the second partial derivative is positive. Therefore the function C 24T is convex and has a unique global optimum for zone length Lt. 3.3 Work Zone Optimization - Four-Lane Two-Way Highway 3.3.1 Alternatives and Assumptions The following four alternatives are considered for four-lane two-way highways in this study: 1. There is no detour and one of the two lanes is closed for Q1 traffic. 2. A fraction of Q1 traffic is diverted through detour. 42 3. All of Q1 is diverted through detour, allowing work zone on both lanes in Direction 1. 4. All of Q1 crosses over into one lane in the opposite direction, allowing work on both lanes in Direction 1. The geometries of these four cases are shown in Figure 3.2. Several simplifying assumptions made in formulating this problem are listed below. 1. Traffic moves at a uniform speed through a work zone and at a different uniform speed elsewhere. 2. The effects on speeds of the original detour flows on the relatively short Ld1 and Ld3 in Figures 3.2 are negligible. 3. Possible signal or stop sign delays on the detour in Alternatives 4.2, 4.3 may be neglected. 4. Queue backups to the maintained road along the first detour Ld1 may be neglected. 5. The detour capacity always exceeds the original detour flow plus diverted flow, so queue delay on the detour may be neglected. 3.3.2 Model Formulation Work zone cost functions of four alternatives for four-lane highways are formulated in this section. Alternative 4.1 is based on the study by Chien and Schonfeld (2001). Other alternatives, Alternatives 4.2, 4.3, and 4.4, are developed here as extensions of Alternative 4.1 by considering an alternate route or crossover flow to the opposite direction. 43 Alternative 4.1: No Detour and One of the Two Lanes closed for Q1 Traffic Chien and Schonfeld (2001) developed a work zone cost function, which includes the user delay, the accident, and the agency costs, for four-lane two-way highway without considering a detour (Figure 3.2(a)). The user delay cost consists of the queuing delay costs upstream of work zones and the moving delay costs through work zones. The following variables are defined: Q1 = approaching traffic flow in Direction 1 of work zone maintained (veh/hr) cw = work zone capacity (veh/hr) D = maintenance duration per zone If Q1 exceeds the work zone capacity cw, a queue forms, which then dissipates when the closed lane is open again, shown in Figure 3.3. The area of A, queue length during D, is equal to the area of B, the number of dissipated vehicles. The queue dissipation time td is: Q(c Dc-(Q t 10 w1 d ) ) = (3.29) where c0 represents the road capacity in normal (two lanes) conditions in Direction 1 without work zone. The queuing delay cost per maintained kilometer for Alternative 4.1, 41qC , is queue delay 41qt multiplied by the average delay cost v and divided by L: L vt C 41 q41 q = (3.30) 44 Flow (vph) Time (hr) Queue Length Time (hr)D td c w c0 Q1 (Q1-cw)D A B C Figure 3.3 Queue Length for Four-lane Highway Work Zone (Chien and Schonfeld, 2001) where 41qt = queue delay incurred by the approaching traffic flow Q1 for Alternative 4.1while work on one zone is completed and the queue is dissipated, which is equal to the area C in Figure 3.3. If Q1 is less than the maximum discharge rate of work zone, cw, the queue delay 41qt is neglected. If Q1 is greater than cw, the queue delay 41qt is: 2 43w 10 w1 w1d 41 q )Lzz)(cQ)(Qc cQ1( 2 1 )]D)cQ)[(tD( 2 1 t +  += += (3.31) Then: w1 41 q cQn whe0C = (3.32a) w1 2 43w1 10 w141 q cQhen w)Lzz)(cQ)(Qc cQ1( L2 vC >+  += (3.32b) 45 The moving delay cost per maintained kilometer 41 vC is the moving delay 41mt multiplied by the average delay cost v and divided by L: L vt C 41 m41 v = (3.33) where 41 mt = moving delay incurred by the approaching traffic flow Q1. 41mt is a function of the difference between the travel time on a road with and without a work zone: w11 aw 41 m cQ whenDQ)V L V L(t = (3.34a) w1w aw 41 m cQ whenDc)V L V L(t >= (3.34b) where Va = average approaching speed; Vw = average work zone speed. If Q1 is greater than cw, the variable Q1 is reduced by cw, because the maximum flow allowed to pass through the work zone is cw. Then: w1431 aw 41 v cQ whenL)vzz(Q)V 1 V 1(C += (3.35a) w143w aw 41 v cQ whenL)vzz(c)V 1 V 1(C >+= (3.35b) Total user delay cost per maintained lane kilometer for Alternative 4.1 41UC is: 41 v 41 q 41 U CCC += (3.36) The accident cost incurred by the traffic passing the work zone can be determined from the number of accidents per 100 million vehicle hour na multiplied by the product of the increasing delay ( 41qt + 41mt ) and the average cost per accident va and then divided by work zone length L (Chien and Schonfeld, 2001). Average accident cost per maintained kilometer 41aC is formulated as: 46 8 aa 41 m 41 q41 a 10 vn L )tt( C + = (3.37) Then: w18 aa 431 aw 41 a cQ when10 vn)Lzz(Q) V 1 V 1(C += (3.38a) w18 aa 43w aw 2 43w1 10 w141 a cQwhen 10 vn)]Lzz(c) V 1 V 1( )Lzz)(cQ)(Qc cQ1( L2 1[C >++ +  += (3.38b) Total cost is: 41 a 41 UM 41 T CCCC ++= (3.39) Then: w18 aa 431 aw 2 141 T cQ when)10 vn v)(Lzz(Q) V 1 V 1()z L z(C ++++= (3.40a) w18 aa 43w aw 2 43w1 10 w1 2 141 T cQhen w) 10 vn v)](Lzz(c) V 1 V 1( )Lzz)(cQ)(Qc cQ 1( L2 1[)z L z(C >+++ +  +++= (3.40b) The resulting optimized work zone length 41*L is then found to be: w1 4314 141* cQ when PPQz z L = (3.41a) w1 4w43 2 4321 2 3321141* cQ when zcPP2zPPP zPPPz2L > + + = (3.41b) where w11 cQP = (3.42) 10 w1 2 Qc cQ1P   += (3.43) 47 8 aa 3 10 vn vP += (3.44) aw 4 V 1 V 1P = (3.45) The second derivative of C 41T with respect to L is positive in this case and the following ones, indicating that function is convex and has a unique global minimum for L. Alternative 4.2: A Fraction of Q1 Traffic through Detour It is assumed in Alternative 4.2 (Figure 3.2(b)) that the fraction p of the flow Q1 in Direction 1 is diverted to the alternate route. In this section pQ1 and (1-p)Q1 are considered separately. The user delay costs include queuing delay and moving delay cost. Total user delay cost per maintained lane kilometer for (1-p)Q1, 42 )p1(UC  , is: 42 )p1(v 42 )p1(q 42 )p1(U CCC  += (3.46) The user queuing delay cost of the remaining flow in Direction 1, (1-p)Q1, denoted as C 42 )p1(q  , is the queue delay t 42 )p1(q  for (1-p)Q1 multiplied by the average delay cost v and divided by L. t 42 )p1(q  has the same formulation as Eq.(3.31) but with (1-p)Q1 substituted for Q1: w1 42 )p1(q cp)Q-(1 when0t = (3.47a) w1 2 43w 10 w142 )p1(q cp)Q-(1 when)Lzz)(cQ)p1)((Q)p1(c cQ)p1(1( 2 1 t >+  += (3.47b) Then C 42 )p1(q  has the same formulation as Eq. (3.32) but with (1-p)Q1 substituted for Q1: w1 42 )p1(q cp)Q-(1 when0C = (3.48a) 48 w1 2 43w1 10 w142 )p1(q cp)Q-(1 when)Lzz)(cQ)p1)((Q)p1(c cQ)p1(1( L2 vC >+  += (3.48b) The moving delay cost per maintained kilometer C 42 )p1(v  for (1-p)Q1 is the moving delay 42 )p1(mt  for (1-p)Q1 multiplied by the average delay cost vd and divided by L. 42 )p1(mt  has the same formulation as Eq.(3.34) but with (1-p)Q1 substituted for Q1: w11 aw 42 )p1(m cp)Q-(1 whenDQ)p1)(V L V L(t = (3.49a) w1w aw 42 )p1(m cp)Q-(1 whenDc)V L V L(t >= (3.49b) Then, C 42 )p1(v  has the same formulation as Eq.(3.35) but with (1-p)Q1 substituted for Q1: w1431 aw 42 )p1(v cp)Q-(1 whenL)vzz(Q)p1)(V 1 V 1(C += (3.50a) w143w aw 42 )p1(v cp)Q-(1n wheL)vzz(c)V 1 V 1(C >+= (3.50b) The user delay cost per maintained lane kilometer for the detoured flow in Direction 1, pQ1, denoted as puC , is equal to: 42 vp 42 qp 42 Up CCC += (3.51) where 42qpC represents the queuing delay for pQ1 and 42vpC represents the moving delay for pQ1. We assume the detour capacity cd always exceeds pQ1 plus Q3, so the queuing delay of pQ1 is zero. The user moving delay cost of the diverted flow pQ1 from Direction 1, 42vpC , is equal to the flow pQ1 multiplied by: (1) the average maintenance duration per kilometer, 49 4 3 z L z + , which is the maintenance duration per zone, z3+z4L, divided by work zone L, (2) the time difference between the time vehicles through the detour, 2 d 2d a 3d1d V L V LL * + + , and the time vehicles through the maintained road AB without work zone, a t V L , and (3) the value of time, v. Thus: v] V L V L V LL)[z L z(pQC a t 3* d 2d a 3d1d 4 3 1 42 vp +++= (3.52) Therefore, the user delay cost for pQ1 is: v] V L V L V LL)[z L z(pQCCCC a t 3* d 2d a 3d1d 4 3 1 42 vp 42 vp 42 qp 42 Up +++==+= (3.53) where 3*dV is the detour speed affected by diverted flow pQ1 in Direction 3 in Alternative 4.2 The additional moving delay cost of the original flow Q3 in Direction 3, as affected by the detoured flow Q1, is denoted 423vC . It has the same formulation as Eq.(3.11). v) V L V L)(z L z(QC 0d 2d 3* d 2d 4 3 3 42 3v += (3.54) The total user delay cost 42UC can be determined as follows: 42 3v 42 Up 42 )p1(U 42 CCCC U ++=  (3.55) The average accident cost per maintained kilometer for (1-p)Q1, 42 )p1(aC  , is: 8 aa 42 )p1(m 42 )p1(q42 )p1(a 10 vn L )tt( C  + = (3.56) Then: 50 w18 aa 431 aw 42 )p1(a cp)Q-(1 when10 vn)Lzz(Q)p1)( V 1 V 1(C += (3.57a) w18 aa 43w aw 2 43w1 10 w142 )p1(a cp)Q-(1en wh 10 vn)]Lzz(c) V 1 V 1( )Lzz)(cQ)p1)((Q)p1(c cQ)p1(1( L2 1[C >++ +  += (3.57b) The average accident cost per maintained kilometer for pQ1, 42apC , is: 8 aa 42 mp 42 qp42 ap 10 vn L )tt( C + = (3.58) where cpQhen wL)zz(pQ) V L V L V LL( v LC t d1431 a t 3* d 2d a 3d1d d 42 vp42 mp +++== (3.59) and t 42qp =0. Then: cpQ when 10 vn)z L z(pQ) V L V L V LL(C d18aa431 a t 3* d 2d a 3d1d42 ap +++= (3.60) The average accident cost per maintained kilometer for Q3, 423aC , is 8 aa 42 3m42 3a 10 vn L tC = (3.61) where ) V L V L)(Lzz(Q v LC t 0d 2d 3* d 2d 433 42 3v42 3m +== (3.62) Then: 8 aa 0d 2d 3* d 2d 4 3 3 42 3a 10 vn) V L V L)(z L z(QC += (3.63) The total accident cost 42 aC can be determined as follows: 42 3a 42 ap 42 )p1(a 42 a CCCC ++=  (3.64) 51 Then, the total cost is: )CCC()CCC(CCCCC 423a42ap42 )p1(a423v42Up42 p)-U(1M42a42UM42T ++++++=++=  (3.65) The resulting optimized work zone length is: ) 10 vn v(zQ)p1)( V 1 V 1( ) 10 vn v)( V L V L(zQ) 10 vn v)( V L V L V LL(zpQz L 8 aa 41 aw 8 aa 0d 2d 2* d 2d 338 aa a t 2* 2d a 3d1d 311 42* + ++++++ = w1 cp)Q-(1when (3.66a) ) 10 vn v( 2 z)cQ)p1)((Q)p1(c cQ)p1(1() 10 vn v(zc) V 1 V 1( ) 10 vn v)( V L V L(zQ) 10 vn v)]( V L V L V LL(zpQ 2 z)cQ)p1)((Q)p1(c cQ)p1(1[(z L 8 aa 2 4 w1 10 w1 8 aa 4w aw 8 aa 0d 2d 2* d 2d 338 aa a t 2* 2d a 3d1d 31 2 3 w1 10 w1 1 42* +  +++ ++++++  ++ = w1 cQp)-(1 when > (3.66b) The second derivative of C 42T with respect to L is also positive in this case and the following ones, indicating that function is convex and has a unique global minimum for L. Alternative 4.3: All Q1 Traffic through Detour, Allowing a Work Zone on Both Lanes in Direction 1 Here it is assumed that the entire flow Q1 in Alternative 4.2 is diverted to the alternate route (Alternative 4.3, Figure 3.2(c)). Then the total cost in Direction 1 has the same formulation as Eq.(3.65) but with Q1 substituted for pQ1 and p is replaced by 1. Here Q1 may be greater than cw because Q1 would not pass through work zone. The total cost for Alternative 4.3 is: 52 8 aa 0d 2d 3* d 2d 4 3 3 8 aa 4 3 a t 2* d 2d a 3d1d 1 0d 2d 3* d 2d 4 3 3 a t 2* d 2d a 3d1d 4 3 1 2 143 T 10 vn) V L V L)(z L z(Q 10 vn)z L z)( V L V L V LL(Q v) V L V L)(z L z(Q v] V L V L V LL)[z L z(Q )z L z(C ++ ++++ ++ ++++ += (3.67) where 3*dV is the detour speed affected by Q1 in Direction 3 in Alternative 4.3. The first and second partial derivatives of C 43T are then found to be: 0] 10 vn) V L V L( L zQ 10 vn) V L - V L V LL( L zQ v) V L V L( L zQ)v V L - V L V LL( L zQ L z[ L C 8 aa 0d 2d 3* d 2d 2 33 8 aa a t 2* d d2 a 3dd1 2 31 0d 2d 3* d 2d 2 33 a t 2* d d2 a 3dd1 2 31 2 1 43 T <++++ ++++=  (3.68) 0 10 vn) V L V L( L zQ2 10 vn) V L - V L V LL( L z2Q v) V L V L( L zQ2)v V L - V L V LL( L z2Q L z2 L C 8 aa 0d 2d 3* d 2d 3 33 8 aa 0 t 4* d d2 0 3dd1 3 31 0d 2d 3* d 2d 3 33 a t 2* d d2 a 3dd1 3 31 3 1 2 43 T 2 >++++ ++++=  (3.69) The first partial derivative of C43T is negative and the second partial derivative is positive. Therefore the function C43T is convex and there is no local or global minimum for zone length is between 0 and Lt. The minimal cost occurs when the zone length is Lt. Alternative 4.4: Crossover of All Q1 Traffic into One Opposite Lane, Allowing a Work Zone on Both Lanes in Direction 1 Here it is assumed that the entire flow Q1 in Alternative 4.1 crosses over to one lane in the opposite direction (Figure 3.2(d)). Both lanes in Direction 1 are closed for work zone. The flow Q2 in Direction 2 only uses the remaining lane. In Alternative 4.4, 53 we assume (1) the vehicles in Q1 and Q2 along work zone have the same speed, Vw, (2) the capacity of each lane in Direction 2 between the start and end of work zone for Q1 and Q2 is equal to work zone capacity, cw, (3) the distance between the start and end of work zone in Direction 1 is equal to the distance of crossover route through alternate lane in Direction 2. In Alternative 4.4, the queuing delay and moving delay may occur for either Q1 or Q2. Below are all possible combinations for user queuing delay costs, moving delay costs, and accident costs. 1,2jcQhen w0C wj44qj = = (3.70a) 1,2jcQwhen)Lzz)(cQ)(Qc cQ1( L2 vC wj 2 43wi 10 wi44 qj =>+  += (3.70b) where C44qj is user queuing delay cost for Qj. 1,2jcQwhenL)vzz(Q) V 1 V 1(C wj43j aw 44 vj = += (3.71a) 1,2jcQwhenL)vzz(c) V 1 V 1(C wj43w aw 44 vj =>+= (3.71b) where C44vj is user moving delay cost for Qj. 1,2jcQ when 10 vn)Lzz(Q) V 1 V 1(C wj8aa43j aw 44 aj = += (3.72a) 1,2jcQ when 10 vn)]Lzz(c) V 1 V 1( )Lzz)(cQ)(Qc cQ 1( L2 1[C wj8 aa 43w aw 2 43wj i0 wj44 aj =>++ +  += (3.72b) where C44aj is accident cost for Qj. The total cost is then: 54 44 2a 44 1a 44 2v 44 2q 44 1v 44 1qM 44 2a 44 1a 44 2U 44 1UM 44 a 44 UM 44 T CCCCCCC )CC()CC(C CCCC ++++++= ++++= ++= (3.73) where 44UC is total user delay cost per maintained lane kilometer and 44 aC total accident cost per maintained lane kilometer for Alternative 4.4. Optimized work zone lengths L*44 are then derived for four combinations of conditions defined by whether Q1 and Q2 are above or below the capacity cw. (1) If w2w1 cQ&cQ : ) V 1 V 1)( 10 vn v)(QQ(z zL aw 8 aa 214 144* ++ = (3.74) (2) If w2w1 cQ&cQ > : ) 10 vn v)(cQ)(Qc cQ 1( 2 z) V 1 V 1)( 10 vn v)(Qc(z ) 10 vn v)(cQ)(Qc cQ 1( 2 z z L 8 aa w1 10 w1 2 4 aw 8 aa 2w4 8 aa w1 10 w1 2 3 1 44* +  ++++ +  ++ = (3.75) (3) If w2w1 cQ&cQ > : ) 10 vn v)(cQ)(Qc cQ 1( 2 z) V 1 V 1)( 10 vn v)(Qc(z ) 10 vn v)(cQ)(Qc cQ 1( 2 z z L 8 aa w2 20 w2 2 4 aw 8 aa 1w4 8 aa w2 20 w2 2 3 1 44* +  ++++ +  ++ = (3.76) (4) If w2w1 cQ&cQ >> : )]cQ)(Qc cQ1()cQ)(Qc cQ1)[( 10 vn v( 2 z) V 1 V 1)( 10 vn v(cz2 )]cQ)(Qc cQ1()cQ)(Qc cQ1)[( 10 vn v( 2 z z L w2 20 w2 w1 10 w1 8 aa 2 4 aw 8 aa w4 w2 20 w2 w1 10 w1 8 aa 2 3 1 44*   ++  ++++   ++  +++ = (3.77) 55 Because no alternate path is involved in Alternative 4.4, no detour parameters are shown in Eqs (74), (75), (76), and (77). 3.4 Determination of Work Zone and Detour Speeds The relations between speed and flow have been extensively researched in past decades. In 1935 Greenshield proposed a parabolic equation for speed-flow curve on the basis of a linear speed-density relationship together with the equation, flow = speed * density. This model was widely used and appeared in the 1965 Highway Capacity Manual (HCM) and the 1985 HCM. However, some objections to for Greenshield?s model have been made. One is that Greenshield?s model did not work with freeway data. The second is that the curve-fitting of this model by current standards of research and empirical data would not acceptable (Messer et al., 1997). Many studies show that the relationship between speed and flow is divided into three stages: uncongested, queue discharge, and within a queue (Hall, et al., 1992). In the speed-flow curve, speed remains flat as flows increases between half and two-thirds of capacity values, and has a very small decrease in speeds at capacity from those values (Messer et al., 1997). Such a curve is also shown in the 1994 HCM. To simplify the analytic work zone optimization models, Greenshield?s model is used below. In traffic flow theory, the relation among flow Q, density K, and speed V is: Q = KV (3.78) The speed function can be formulated by applying Greenshield?s model (Gerlough and Huber, 1975): 56 K K V VV j f f = (3.79) where Vf is free flow speed, Kj is jam density. Substituting (3.79) into (3.78), we obtain 2V V K VKQ f j j = (3.80) Solving the quadratic Eq.(3.80) for the speed V, we obtain two solutions. The first is: j fj 2 fjfj K2 QVK4)VK(VK V + = (3.81) Then, 0V , 0dV , 3*dV and 4*dV in Alternatives 2.2 and 2.3 or 4.2 and 4.3 can be determined from Eq.(3.81). The other solution of Eq.(3.80) is: j fj 2 fjfj K2 QVK4)VK(VK V  = (3.82) which is the speed under forced flow conditions (Gerlough and Huber, 1975). This speed is not used in Case 1 because 0V , 0dV , 3*dV and 4*dV are applied based on the assumption that the original road without work zone and detour has enough capacity for steady traffic inflows so that the speeds on the original road ( 0V ) and detour ( 0dV ) are free-flowing speeds. In Chapter 5, the congestion and delay along a detour will be considered when work zone optimization models for time-dependent inflows with a detour are developed. 57 3.5 Threshold Analysis In this section the selection of the best alternatives is considered under different situations. Guidelines for selecting the best alternative for different traffic flows, roads and maintenance characteristics are developed by deriving thresholds among those alternatives. 1* TC , 2* TC , 3* TC and 4*TC are the minimized total costs of Alternatives 2.1, 2.2, 2.3 and 2.4, (or Alternatives 4.1, 4.2, 4.3 and 4.4) computed with their respective optimized work zone lengths 1*L , 2*L 3*L and 4*L . The threshold between any two alternatives can be obtained by setting their two cost functions equal. For example, Figure 3.4 shows the relation between total cost and detour length. It indicates that Alternative 2.3 is preferable up to a detour length of DLT32 , beyond which Alternative 2.2 is preferable up to DLT21 . To ta l c o st Alt 2.1 Alt 2.2 Alt 2.3 Detour Length, L d DLT32 DLT21 Alt 2.4 Figure 3.4 Total Cost vs. Detour Length 58 Thresholds with respect to the distance AB, setup cost, average maintenance time, and other input parameters, can be obtained similarly to the detour length thresholds. For some variables or alternatives, if the thresholds are not positive or not located within applicable ranges, then no threshold exists. 3.6 Numerical Analysis - Two-Lane Two-Way Highway 3.6.1 Sensitivity Analysis The effects of various parameters on work zone length and the preferable alternatives are examined in this section. The baseline numerical values for each variable in this section are defined in Table 3.1. The optimized solutions for work zone length and total cost are shown in Table 3.2 for various traffic flow combinations. For Alternatives 2.1 and 2.2, when Q1 or Q2 increases, the optimized zone length decreases. However, for Alternative 2.3, the optimized zone length increases slightly with Q1 and decreases with Q2, because increasing zone length decreases the delay cost of Q1 in Eq.(3.15). The optimized zone length ranges from 1.54 to 0.49 km for Alternative 2.1, 2.17 to 0.20 km for Alternative 2.2, 2.3 to 0.74 km for Alternative 2.3, and 5 km for any Alternative 2.4. Table 3.2 shows that the optimized zone length increases with the diverted fraction to the detour from Q1. The combined flow Q1+Q2 ranges from 100 to 2,000 vph. Note that the optimized zone length and minimized total cost are not available when the combined flow exceeds the work zone capacity 1,200 vph. At the baseline values, Alternative 2.4 dominates all others in Table 3.2, as its optimized total cost is the lowest for any flow combination Q1 and Q2. 59 Table 3.1 Inputs for Numerical Example and Sensitivity Analysis for Two-Lane Two-Way Highway Work Zones Variable Description Values H Average headway through work zone area 3 s Kj Jam density along AB and detour 200 veh/lane?km Ld1 Length of first detour segment 0.5 km Ld2 Length of second detour segment 5 km Ld3 Length of third detour segment 0.5 km Lt Entire Distance of Maintained Road from A to B 5 km na Number of accidents per 100 million vehicle hour 40 acc/100mvh Q3 Hourly flow rate in Direction 3 500 veh/hr V Average work zone speed 50 km/hr Vf Free flow speed along AB and detour 80 km/hr v Value of user time 12 $/veh?hr 1z Fixed setup cost 1,000 $/zone z2 Average maintenance cost per lane?kilometer 80,000 $/lane?km 3z Fixed setup time 2 hr/zone z4 Average maintenance time per lane?kilometer 6 hr/lane?km To examine sensitivities to other factors, we fix the traffic flow rates Q1 and Q2 at 400 vehicles per hour (vph) each. Figure 3.5 shows increases in user cost as the zone length increases in Alternatives 2.1, 2.2, and 2.3. However, user cost decreases slightly as the zone length increases in Alternative 2.4 because no vehicle passes through the work zone and the longer zone decreases the moving delay per lane-kilometer. 60 Table 3.2 Optimized work zone lengths and Total Costs for Different Flow Rates Alt.2.1 Alt.2.2 (p=0.3) Alt.2.2 (p=0.6) Alt.2.2 (p=0.9) Alt.2.3 Alt.2.4 Q1+Q2 Q1 Q2 Optim. length Min. total cost Optim. length Min. total cost Optim. length Min. total cost Optim. length Min. total cost Optim. length Min. total cost Optim. length Min. total cost 200 100 100 1.54 81,260 1.69 81,185 1.89 81,101 2.17 81,003 2.30 80,966 5.00 80,461 400 200 200 1.04 81,975 1.16 81,847 1.32 81,709 1.55 81,550 1.66 81,491 5.00 80,727 600 200 400 0.80 82,695 0.88 82,502 0.99 82,316 1.12 82,129 1.17 82,064 5.00 81,023 800 200 600 0.64 83,559 0.72 83,204 0.81 82,897 0.92 82,617 0.96 82,527 5.00 81,353 1000 200 800 0.48 85,162 0.58 84,245 0.67 83,596 0.79 83,085 0.83 82,933 5.00 81,723 1200 200 1000 - - 0.34 88,747 0.51 85,172 0.68 83,659 0.74 83,302 5.00 82,136 600 400 200 0.80 82,693 0.95 82,442 1.16 82,194 1.53 81,908 1.73 81,792 5.00 80,992 800 400 400 0.61 83,846 0.73 83,303 0.89 82,888 1.12 82,512 1.22 82,383 5.00 81,277 1000 400 600 0.43 86,096 0.57 84,520 0.72 83,660 0.91 83,044 1.00 82,860 5.00 81,597 1200 400 800 - - 0.37 87,872 0.57 84,886 0.78 83,595 0.86 83,277 5.00 81,957 1400 400 1000 - - - - 0.28 92,322 0.65 84,444 0.77 83,657 5.00 82,359 800 600 200 0.64 83,556 0.81 83,048 1.05 82,673 1.51 82,275 1.80 82,106 5.00 81,268 1000 600 400 0.43 86,095 0.61 84,301 0.81 83,490 1.12 82,907 1.27 82,715 5.00 81,542 1200 600 600 - - 0.42 86,921 0.64 84,549 0.91 83,487 1.04 83,206 5.00 81,852 1400 600 800 - - - - 0.46 86,882 0.77 84,134 0.90 83,635 5.00 82,200 1600 600 1000 - - - - - - 0.61 85,342 0.80 84,024 5.00 82,592 1000 800 200 0.49 85,159 0.70 83,736 0.97 83,154 1.49 82,652 1.87 82,433 5.00 81,558 1200 800 400 -! - 0.49 85,866 0.74 84,146 1.11 83,315 1.32 83,061 5.00 81,821 1400 800 600 - - 0.20 99,517 0.56 85,675 0.91 83,947 1.08 83,565 5.00 82,119 1600 800 800 - - - - 0.32 91,391 0.76 84,704 0.94 84,006 5.00 82,456 1800 800 1000 - - - - - - 0.57 86,401 0.84 84,406 5.00 82,836 1200 1000 200 - - 0.60 84,658 0.90 83,649 1.48 83,041 1.95 82,777 5.00 81,865 1400 1000 400 - - 0.33 90,098 0.68 84,891 1.11 83,737 1.38 83,423 5.00 82,115 1600 1000 600 - - - - 0.48 87,296 0.91 84,426 1.12 83,942 5.00 82,400 1800 1000 800 - - - - - - 0.75 85,311 0.97 84,394 5.00 82,725 2000 1000 1000 - - - - - - 0.53 87,698 0.87 84,805 5.00 83,093 Table 3.3 compares the delay costs for different directional flows that add up to 1400 vph. For Alternative 2.2 (p=0.6), although the combined flow is the same, the combinations with larger Q2 have shorter optimized zones and higher total costs. This occurs because the queue delay cost on the main road, 22qC , which is the main part of the total delay costs, increases as Q2 increases. 61 0 2000 4000 6000 8000 10000 12000 14000 0.2 0.6 1 1.4 1.8 2.2 2.6 3 3.4 3.8 4.2 4.6 5 Work Zone Length (km) Us er D el ay Co st ($/ la n e. km ) ' User Cost (Alt 2.1) User Cost (Alt 2.2-p=0.3) User Cost (Alt 2.2-p=0.6) User Cost (Alt 2.2-p=0.9) User Cost (Alt 2.3) User Cost (Alt 2.4) Figure 3.5 User Costs versus Various Zone Lengths (Q1=400vph, Q2=400vph) Table 3.3. Comparison of Delay Costs with Different Directional Flows for Alternative 2.2 (p=o.6) C 22U ($/km)Q1+Q2 (vph) Q1 (vph) Q2 (vph) Optimized Length (km) Cost C 22 T ($/km) CM ($/km) C 22q 22vpC 223vC 22 2)p1(vC  Value 92,322 83,546 8,116 542 87 31 1,400 400 1,000 0.28 Percent of Cost 100% 90.49% 8.79% 0.59% 0.09% 0.03% Value 84,891 81,474 2,331 897 157 32 1,400 1,000 400 0.68 Percent of Cost 100% 95.97% 2.75% 1.10% 0.19% 0.04% As the zone length increases, the maintenance costs per kilometer decreases due to fewer setups, but stays the same for all alternatives. Combined with the user cost in Figure 3.5, the zone lengths that minimize total costs are determined by trade-offs between the user and maintenance cost, show in Figure 3.6. The optimized zone lengths for Alternatives 2.1, 2.2 (p=0.3), 2.3, and 2.4 are 0.61 km, 0.73 km, 1.22 km, and 5.00 km, respectively. Faster increases in the user cost of Alternative 2.1 shorten its optimized zone. 62 78000 80000 82000 84000 86000 88000 90000 92000 94000 96000 98000 0.2 0.6 1 1.4 1.8 2.2 2.6 3 3.4 3.8 4.2 4.6 5 Work Zone Length (km) To ta l C o st ($/ la n e. km ) ' Total Cost (Alt 2.1) Total Cost (Alt 2.2-p=0.3) Total Cost (Alt 2.2-p=0.6) Total Cost (Alt 2.2-p=0.9) Total Cost (Alt 2.3) Total Cost (Alt 2.4) Figure 3.6 Total Costs versus Various Work Zone Lengths (Q1=400vph, Q2=400vph) Figures 3.7 and 3.8 show how setup cost z1 and average maintenance time z4 affect the optimized zone length. Figure 3.7 shows that the optimized zone length increases when the setup cost z1 increases for Alternatives 2.1, 2.2, and 2.3, because longer zones imply fewer setups and decreased total cost. In Alternative 2.4, total cost is minimized when zone length is 5 km, regardless of other variables. Then, the optimized zone length of Alternative 2.4 is entirely unaffected by setup cost. Figure 3.8 shows that the optimized zone length decreases when the average maintenance time increases, in order to avoid excessive increases in user delay. The optimized zone length of Alternative 2.4 is also entirely unaffected by average maintenance time. Additional sensitivity of the optimized zone length to setup duration, work zone speed, and other factors is provided in Chen and Schonfeld (2002). 63 0 1 2 3 4 5 6 250 750 1250 1750 2250 2750 3250 3750 4250 4750 Setup Cost ($/zone) O pt im iz ed W o rk Zo n e Le n gt h (km ) '' Alt 2.1 Alt 2.2 (p=0.3) Alt 2.2 (p=0.6) Alt 2.2 (p=0.9) Alt 2.3 Alt 2.4 Figure 3.7 Optimized Zone Length versus Setup Cost z1 (Q1=400vph, Q2=400vph) 0 1 2 3 4 5 6 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 Average Maintenance Time (h/km) O pt im iz ed W o rk Zo n e Le n gt h (km ) '' Alt 2.1 Alt 2.2 (p=0.3) Alt 2.2 (p=0.6) Alt 2.2 (p=0.9) Alt2.3 Alt 2.4 Figure 3.8 Optimized Zone Length versus Average Maintenance Time z4 (Q1=400vph, Q2=400vph) 64 Figure 3.9 shows that the combined capacity of the maintained road and its detour increases as the diverted fraction increases. Here the capacity for Alternative 2.1 is 1200 vph. As the diverted fraction increases, the combined flow discharge increases. The combined capacity is about 1450 vph for Alternative 2.2 (p=0.3) and about 1700 vph for Alternative 2.2 (p=0.6). The capacity of the one lane through the zone in Alternative 2.1 can be also obtained by dividing one hour (3600 seconds) by the headway (3 seconds) through the zone. Starting from Alternative 2.1 as the baseline, the additional capacity in Alternatives 2.2 and 2.3 is contributed by the detour. Higher diverted fractions increase the capacity through the zone. 0 2000 4000 6000 8000 10000 12000 200 400 600 800 1000 1200 1400 1600 1800 2000 Combined Flow (vph) Us er De la y Co st ($/ la n e. km ) ' Alt 2.1 Alt 2.2 (p=0.3) Alt 2.2 (p=0.6) Alt 2.2 (p=0.9) Alt 2.3 Alt 2.4 Figure 3.9 User Delay Costs versus Combined Flows 65 3.6.2 Selection Guidelines Thresholds among alternatives with respect to four variables, namely, detour length (Ld), length of main road between the beginning and end of detour (Lt), setup cost (z1), and average maintenance time per kilometer (z4), are solved numerically and presented below. Figure 3.10 shows the relation between total cost and detour length when Q1 and Q2 are each 200 vph. The detour length threshold is 9.00 km, beyond which Alternative 2.1 becomes preferable to Alternative 2.4. Figure 3.11 shows that there are four detour length thresholds and Alternatives 2.1, 2.2, 2.3, and 2.4 are on the lowest cost envelope when Q1 and Q2 are each 400 and 600 vph. The first threshold occurs at 10 km, beyond which Alternative 2.3 becomes preferable to Alternative 2.4; beyond 11 km Alternative 2.2 (p=0.6) becomes preferable to Alternative 2.3; beyond 12 km Alternative 2.2 (p=0.3) becomes preferable to Alternative 2.2 (p=0.6); beyond 15 km Alternative 2.1 becomes preferable to Alternative 2.2 (p=0.3). Figure 3.12 shows the relation between total cost and detour length when Q1 and Q2 are each 800 and 600 vph. There are three detour length thresholds, 9 km, 12 km, and 14 km, and Alternatives 2.2 (p=0.6 and 0.9), Alternatives 2.3 and 2.4 are on the lowest cost envelope. 66 80000 82000 84000 86000 88000 90000 92000 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 Detour Length (km) To ta l C o st ($/ la n e. km ) ' Total Cost (Alt 2.1) Total Cost (Alt 2.2-p=0.3) Total Cost (Alt 2.2-p=0.6) Total Cost (Alt 2.2-p=0.9) Total Cost (Alt 2.3) Total Cost (Alt 2.4) Figure 3.10 Total Cost versus Detour Length for Various Alternatives (Q1=200vph, Q2=200vph) 80000 84000 88000 92000 96000 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 Detour Length (km) To ta l C o st ($/ la n e. km ) ' Total Cost (Alt 2.1) Total Cost (Alt 2.2-p=0.3) Total Cost (Alt 2.2-p=0.6) Total Cost (Alt 2.2-p=0.9) Total Cost (Alt 2.3) Total Cost (Alt 2.4) Figure 3.11 Total Cost versus Detour Length for Various Alternatives (Q1=400vph, Q2=600vph) 67 82000 86000 90000 94000 98000 102000 106000 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 Detour Length (km) To ta l C o st ($/ la n e. km ) ' Total Cost (Alt 2.1) Total Cost (Alt 2.2-p=0.3) Total Cost (Alt 2.2-p=0.6) Total Cost (Alt 2.2-p=0.9) Total Cost (Alt 2.3) Total Cost (Alt 2.4) Figure 3.12 Total Cost versus Detour Length for Various Alternatives (Q1=800vph, Q2=600vph) Defining circuity as the ratio of detour distance to maintained road distance = Ld / Lt, the circuity thresholds are shown for various traffic flows in Table 3.4. The numbers in Table 3.4 represent the preferred pair of alternatives that determine the threshold. If combined flow does not exceed 1000 vph, Alternatives 2.1 and 2.4 determine most thresholds, as illustrated in Figure 3.10. As combined flow increases, Alternatives 2.2 and 2.3 may determine thresholds and additional detour length thresholds appear. Thus, Alternatives 2.1, 2.2, 2.3, and 2.4 all appear on the lowest cost envelope in Figure 3.11. As combined flow increases, e.g. beyond 1400 vph, Alternative 2.2 (whose diverted fraction is lower) is not preferable anymore, e.g. in Figure 3.12. 68 Table 3.4 Circuity Threshold at Different Flow Rates Circuity threshold Q1+Q2 Q1 Q2 Alt.2.1 & Alt.2.4 Alt.2.1 & Alt.2.2 (p=0.3) Alt.2.1 & Alt.2.2 (p=0.6) Alt.2.2 (p=0.3) & Alt.2.2 (p=0.6) Alt.2.2 (p=0.3) & Alt.2.4 Alt.2.2 (p=0.6) & Alt.2.2 (p=0.9) Alt.2.2 (p=0.6) & Alt.2.3 Alt.2.2 (p=0.6) & Alt.2.4 Alt.2.2 (p=0.9) & Alt.2.3 Alt.2.3 & Alt.2.4 200 100 100 2 - - - - - - - - - 400 200 200 1.8 - - - - - - - - - 600 200 400 1.8 - - - - - - - - - 600 400 200 1.8 - - - - - - - - - 800 200 600 - - 2.2 - - - 2 - - 1.6 800 400 400 - 2 - - 1.8 - - - - - 800 600 200 1.8 - - - - - - - - - 1,000 200 800 - 3.4 - 3 - 2.8 - - 2.6 1.6 1,000 400 600 - 3 - 2.4 - - 2.2 - - 1.8 1,000 600 400 - 2.6 - - 2 - - - - - 1,000 800 200 - 2.2 - - 1.8 - - - - - 1,200 200 1,000 - - - - - - - - 5 1.6 1,200 400 800 - - - - - 3.4 - - 3 1.6 1,200 600 600 - - - 3.6 - - 2.4 - - 1.8 1,200 800 400 - - - 2.6 - - - 1.8 - - 1,200 1,000 200 - - - - 2 - - - - - 1,400 400 1,000 - - - - - - - - - 1.6 1,400 600 800 - - - - - 5 - - 3.4 1.6 1,400 800 600 - - - - - 2.8 - - 2.4 1.8 1,400 1,000 400 - - - - - - - 2.2 - - 1,600 600 1,000 - - - - - - - - - 1.6 1,600 800 800 - - - - - - - - 3.8 1.8 1,600 1,000 600 - - - - - 3.6 - - 2.4 2 1,800 800 1,000 - - - - - - - - - 1.6 1,800 1,000 800 - - - - - - 4 1.8 2,000 1,000 1,000 - - - - - - - 1.6 The thresholds with respect to setup cost, z1, average maintenance time per kilometer, z4, and other factors at different flow rates can be obtained similarly to circuity ratio thresholds. 3.6.3 Optimizing the Diverted Fraction Figures 3.13 and 3.14 show the relation between total cost and the diverted fraction of Q1 at different flow rates for Alternatives 2.1, 2.2, and 2.3. (Alternative 2.4 69 with full diversion in both directions is not included). When the detour length Ld has its baseline value, 6 km, and Q2 is 400 vph, the total costs are lowest as p approaches 1.0, which indicates Alternative 2.3 is preferable for various Q1 flows, as illustrated in Figure 3.13. If the detour length Ld increases to 12 km, and Q2 is 400 vph, the minimized total cost occurs at p=0 (Alternative 2.1, no diversion) for Q1 of 200 and 400 vph; and at the lowest points of p, p=0.2, 0.4 for Q1 of 600 and 800 vph, respectively. These indicate that full diversion is preferable when the detours are short; some or no diversion becomes preferable as detour length increases. The results of Figures 3.13 and 3.13 also can be obtained analytically, by setting to zero the partial derivatives of CT with respect to p and solving for the optimal p value. Q 2 =400 vph Ld=6km 76000 78000 80000 82000 84000 86000 88000 90000 92000 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 p (Diverted Fraction) To ta l C o st ($/ ln ae . km ) ' Q1=200 vph Q1=400 vph Q1=600 vph Q1=800 vph Figure 3.13. Total Cost versus Diverted Fraction (Q2=400vph, Ld=6km) 70 Q 2 =400 vph Ld=12km 80000 82000 84000 86000 88000 90000 92000 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 p (Diverted Fraction) To ta l C o st ($/ ln ae . km ) ' Q1=200 vph Q1=400 vph Q1=600 vph Q1=800 vph Figure 3.14 Total Cost versus Diverted Fraction (Q2=400vph, Ld=12km) 3.6.4 Summary In this section work zone cost models are developed for four alternative zone configurations with and without an alternate route. The optimized zone length and preferred alternative for various combinations of variables are determined with these cost models. When the traffic flows in two directions are steady, Alternative 2.1 has a higher user cost and shorter zone than other alternatives while Alternative 2.4 has a lower user cost and longer zone. As Q1 or Q2 increase, the optimized zone length decreases for Alternatives 2.1 and 2.2. However, for Alternative 2.3, the optimized zone length increases slightly as Q1 increases, and decreases as Q2 increases. The optimized zone length of Alternative 2.4 is unaffected by any other variables In the threshold analysis presented, Alternative 2.4 is the preferred alternative in the baseline condition. As detour length Ld increases beyond its threshold, Alternatives 2.1, 2.2 or 2.3 may become preferable. This occurs because increasing Ld increases the 71 user cost. Therefore, the preferred alternative changes when the total cost of Alternative 2.4 exceeds that of Alternatives 2.1, 2.2, or 2.3. Considering an optimized diverted fraction among Alternatives 2.1, 2.2, and 2.3, full diversion is preferable if the detour is short; partial or no division becomes preferable as detour length increases. 3.7 Numerical Analysis ? Four-Lane Two-Way Highways 3.7.1 Sensitivity Analysis The effects of various parameters on work zone length and the preferable alternatives are examined in this section. The baseline numerical values for each variable are the same as in Table 3.1. The baseline numerical values for additional variables in this section are defined in Table 3.5. Table 3.5 Notation and Baseline Numerical Inputs Analysis for Four-Lane Two-Way Highway Work Zones Variable Description Values co Maximum discharge rate without work zone 2,600vph cw Maximum discharge rate along work zone 1,200vph na Number of accidents per 100 million vehicle hour 40 acc/100mvh Q2 Hourly flow rate in Direction 2 500 veh/hr Q3 Hourly flow rate in Direction 3 500 veh/hr Vw Average work zone speed 50 km/hr va Average accident cost 142,000 $/accident v Value of user time 12 $/veh?hr The optimized solutions for work zone length and total cost are shown in Table 3.6 for various traffic flows Q1, from 100 vph to 2,600 vph. Note that the optimized length and minimized total cost are available even if the remaining Q1 on the main road exceeds the work zone capacity 1,200 vph. For Alternatives 4.1, 4.2 (p=0.3 and 0.6), and 72 4.4, as Q1 increases, the optimized zone length L* decreases. Figure 3.15 shows that for Alternatives 4.1, 4.2(p=0.3), and 4.4, L* decreases sharply as the remaining flow of Q1 in Direction 1 exceeds the work zone capacity, because a queue is then formed and a much shorter zone length L is needed to avoid higher queue delays. Q1 in Alternative 4.2 (p=0.3) is higher when L* decreases because 30% of Q1 has been diverted and the remaining flow is approaching the zone capacity. For Alternatives 4.2 (p=0.9) and 4.3, L* stays almost constant at 5 km because almost all of Q1 has been diverted, and the very slight remaining flow of Q1 on the main road has almost no effect on delays due to the work zone. Therefore, the optimized L* is the entire distance from A to B because it has the lowest maintenance cost and total cost. 0.00 1.00 2.00 3.00 4.00 5.00 6.00 10 0 30 0 50 0 70 0 90 0 1, 10 0 1, 30 0 1, 50 0 1, 70 0 1, 90 0 2, 10 0 2, 30 0 2, 50 0 Q1 (vph) O pt im iz ed Zo n e Le n gt h (km ) ' Alt.4.1 Alt.4.2(p=0.3) Alt.4.2(p=0.6) Alt.4.2(p=0.9) Alt.4.3 Alt.4.4 Figure 3.15 Optimized Zone Length vs. Q1 To examine sensitivities to other factors, we fix the traffic flow rates Q1 at 1,000 vehicles per hour (vph). Figure 3.16 shows increases in user cost as L increases in 73 Alternatives 4.1 and 4.4 because they have only one lane for discharging flow and no detours. A longer L only increases user delay costs. Alternatives 4.2 (p=0.3, 0.6, and 0.9) have their lowest user costs for zone lengths of 0.6 km, 1.0 km, and 2.5 km, respectively, since lower remaining flows on the maintained road justify longer L* values. Alternative 4.3 has the lowest user delay cost and maximum L at 5 km since all of Q1 has been diverted; the only moving delay occurs along the detour and it decreases due to reduced maintenance time per kilometer. Thus, a longer L shortens the maintenance time per kilometer and decreases user delay costs. Table 3.6 Optimized work zone lengths (km) and Minimized Total Costs ($/lane.km) for Various Flow Rates Alt.4.1 Alt.4.2 (p=0.3) Alt.4.2 (p=0.6) Alt.4.2 (p=0.9) Alt.4.3 Alt.4.4 Q1 Optimized length Min. total cost Optimized length Min. total cost Optimized length Min. total cost Optimized length Min. total cost Optimized length Min. total cost Optimized length Min. total cost 100 4.32 80,481 5.00 80,439 5.00 80,392 5.00 80,346 5.00 80,331 1.76 81,242 200 3.07 80,687 3.71 80,648 4.97 80,582 5.00 80,493 5.00 80,465 1.64 81,343 300 2.52 80,846 3.06 80,818 4.13 80,758 5.00 80,642 5.00 80,601 1.54 81,436 400 2.20 80,980 2.68 80,968 3.63 80,921 5.00 80,791 5.00 80,741 1.46 81,522 500 1.98 81,098 2.43 81,103 3.31 81,073 5.00 80,942 5.00 80,883 1.40 81,602 600 1.82 81,203 2.24 81,227 3.07 81,218 5.00 81,094 5.00 81,029 1.34 81,677 700 1.69 81,299 2.10 81,343 2.89 81,357 5.00 81,247 5.00 81,179 1.29 81,747 800 1.59 81,386 1.99 81,451 2.75 81,491 5.00 81,402 5.00 81,333 1.25 81,813 900 1.51 81,467 1.90 81,552 2.64 81,620 5.00 81,559 5.00 81,490 1.21 81,874 1,000 1.45 81,541 1.82 81,647 2.54 81,746 5.00 81,717 5.00 81,652 1.18 81,932 1,100 1.39 81,610 1.76 81,736 2.47 81,867 5.00 81,876 5.00 81,819 1.15 81,985 1,200 1.34 81,674 1.70 81,819 2.40 81,984 5.00 82,038 5.00 81,991 1.13 82,035 1,300 0.39 114,198 1.65 81,896 2.35 82,097 5.00 82,201 5.00 82,169 0.39 114,476 1,400 0.36 150,510 1.61 81,967 2.30 82,206 5.00 82,367 5.00 82,352 0.36 150,921 1,500 0.35 193,334 1.58 82,033 2.27 82,311 4.97 82,534 5.00 82,543 0.35 193,914 1,600 0.34 244,690 1.55 82,092 2.23 82,411 4.94 82,704 5.00 82,740 0.34 245,483 1,700 0.34 307,441 1.52 82,145 2.21 82,506 4.92 82,877 5.00 82,946 0.34 308,501 1,800 0.34 385,866 0.44 101,978 2.19 82,597 4.91 83,052 5.00 83,161 0.34 387,270 1,900 0.34 486,686 0.38 125,530 2.17 82,681 4.91 83,231 5.00 83,385 0.34 488,541 2,000 0.34 621,103 0.36 151,665 2.16 82,760 4.92 83,413 5.00 83,621 0.34 623,570 2,100 0.34 809,276 0.36 180,984 2.15 82,832 4.94 83,598 5.00 83,869 0.34 812,611 2,200 0.34 1,091,527 0.35 214,147 2.14 82,896 4.98 83,788 5.00 84,132 0.341,096,177 2,300 0.33 1,561,935 0.35 251,981 2.14 82,953 5.00 83,981 5.00 84,411 0.331,568,791 2,400 0.33 2,502,739 0.34 295,559 2.15 82,999 5.00 84,180 5.00 84,710 0.332,514,032 2,500 0.33 5,325,141 0.34 346,303 2.15 83,036 5.00 84,385 5.00 85,031 0.335,349,777 2,600 - - 0.34 406,147 - - 5.00 84,596 5.00 85,380 - - 74 As L increases, the maintenance costs per kilometer decreases due to fewer setups but stays the same for all alternatives. Combined with the user cost in Figure 3.16 and accident costs for four alternatives, the zone lengths that minimize total costs are determined by trade-offs among the maintenance, user, and accident costs. If we fix the traffic flow rates Q1 at 1,000 vph, L* is 1.45 km for Alternative 4.1, 1.82 km for Alternative 4.2 (p=0.3), 5.00 km for Alternative 4.3, and 1.18 km for Alternative 4.4, shown in Table 3.6 and Figure 3.17. Faster increases in the user cost of Alternative 4.4 shorten its L*. 0 500 1,000 1,500 2,000 2,500 3,000 3,500 4,000 0.2 0.6 1.0 1.4 1.8 2.2 2.6 3.0 3.4 3.8 4.2 4.6 5.0 Work Zone Length (km) U s er D e la y Co s t ($ /la n e. km ) ' Alt.4.1 Alt.4.2(P=0.3) Alt.4.2(p=0.6) Alt.4.2(p=0.9) Alt.4.3 Alt.4.4 Figure 3.16 User Delay Cost vs. Work Zone Length (Q1=1,000vph, Q2=500vph, Q3=500vph) Figures 3.18 shows the relations between L* and setup cost z1. Thus, L* increases when z1 increases in Alternatives 4.1, 4.2 (p=0.3 and 0.6), and 4.4, because longer zones imply fewer setups and decreased total cost. In this case, the L* of Alternatives 4.2 (p=0.9) and 4.3 are not sensitive to setup cost because L* cannot exceed the full distance of the maintained road from A to B (5 km in this example) even though most theoretical 75 L* values for Alternative 4.2 (p=0.9) exceed 5 km. In Alternative 4.3, total cost is minimized when L =5 km, regardless of other variables. Then, L* of Alternative 4.3 is entirely unaffected by setup cost. 80,000 81,000 82,000 83,000 84,000 85,000 86,000 87,000 0.2 0.6 1.0 1.4 1.8 2.2 2.6 3.0 3.4 3.8 4.2 4.6 5.0 Work Zone Length (km) To ta l C o s t ( $/l a n e . km ) ' Alt.4.1 Alt.4.2(P=0.3) Alt.4.2(p=0.6) Alt.4.2(p=0.9) Alt.4.3 Alt.4.4 Figure 3.17 Total Cost vs. Work Zone Length (Q1=1,000vph, Q2=500vph, Q3=500vph) 0.00 1.00 2.00 3.00 4.00 5.00 6.00 25 0 75 0 1, 25 0 1, 75 0 2, 25 0 2, 75 0 3, 25 0 3, 75 0 4, 25 0 4, 75 0 Setup Cost ($/zone) O pt im iz e d W o rk Zo n e Le n gt h (km ) ' Alt.4.1 Alt.4.2(P=0.3) Alt.4.2(p=0.6) Alt.4.2(p=0.9) Alt.4.3 Alt.4.4 Figure 3.18 Optimized Work Zone Length vs. Setup Cost (Q1=1,000vph, Q2=500vph, Q3=500vph) 76 Additional analysis of the sensitivity of L* to setup duration, z3, and average maintenance time, z4, etc. is provided in Chen and Schonfeld (2001). 3.7.2 Selection Guidelines Thresholds among alternatives with respect to several key variables, namely, traffic flow (Q1), detour length (Ld), length of main road between the beginning and end of detour (Lt), setup cost (z1), and average maintenance time per kilometer (z4), etc. are solved numerically and presented below. Figure 3.19 shows the relation between minimized total cost and Q1. There are three flow thresholds and Alternatives 4.1, 4.2, 4.3 successively define the lowest cost envelope. The first threshold occurs at 800 vph, beyond which Alternative 4.1 becomes preferable to Alternative 4.3; beyond 1,200 vph Alternative 4.2 (p=0.3) becomes preferable to Alternative 4.1; beyond 1700 vph more diversion is preferable, such as Alternative 4.2 (p=0.6). This result can also be obtained from Table 3.6. The sharp increase occurs as Q1 exceeds 1,200 vph in Alternative 4.1 and 1,700 vph in Alternative 4.2 (p=0.3) since the flow in Direction 1 exceeds work zone capacity and queue delays develop. 77 80,000 80,500 81,000 81,500 82,000 82,500 83,000 83,500 84,000 10 0 30 0 50 0 70 0 90 0 1, 10 0 1, 30 0 1, 50 0 1, 70 0 1, 90 0 2, 10 0 2, 30 0 2, 50 0 Q1(vph) M in im iz e d To ta l C o s t ( $/l a n e . km ) ' Alt.4.1 Alt.4.2(P=0.3) Alt.4.2(p=0.6) Alt.4.2(p=0.9) Alt.4.3 Alt.4.4 Figure 3.19 Minimized Total Cost vs. Q1 Figure 3.20 shows the relation between minimized total cost and detour length in three cases: Q1=1,000 vph, 1,500 vph, and 2,000 vph. There is no detour threshold in Figure 3.20; however, when Q1 exceeds the maximum discharge rate along the work zone cw, more diverted flow is preferable. The total costs in Alternatives 4.1 and 4.4, which have no detours, become quite high, as shown in Figures 3.20(b) and 3.20(c), as Q1 exceeds cw because queue delays develop and user delay costs increase sharply. Alternative 4.1 is preferable for Q1=1,000 vph, Alternative 4.2 (p=0.3) is preferable for Q1=1,500 vph and Alternative 4.2 (p=0.6) is preferable for Q1=2,000 vph. Figure 3.20 shows that detour length affects the relative costs but not the rankings of alternatives. The thresholds with respect to other main variables, such as setup cost z1, average maintenance time per kilometer, z4, length of main road between the beginning and end of detour, Lt, etc. can be obtained similarly to traffic flow or setup cost thresholds. 78 (a) 80,000 82,000 84,000 86,000 88,000 90,000 92,000 94,000 96,000 98,000 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 Detour Length (km) M in im iz ed To ta l C o st ($/ la n e. km ) ' Alt.4.1 Alt.4.2(P=0.3) Alt.4.2(p=0.6) Alt.4.2(p=0.9) Alt.4.3 Alt.4.4 (b) 80,000 100,000 120,000 140,000 160,000 180,000 200,000 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 Detour Length (km) M in im iz ed To ta l C o st ($/ la n e. km ) ' Alt.4.1 Alt.4.2(P=0.3) Alt.4.2(p=0.6) Alt.4.2(p=0.9) Alt.4.3 Alt.4.4 (c) 80,000 180,000 280,000 380,000 480,000 580,000 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 Detour Length (km) M in im iz ed To ta l C o st ($/ la n e. km ) ' Alt.4.1 Alt.4.2(P=0.3) Alt.4.2(p=0.6) Alt.4.2(p=0.9) Alt.4.3 Alt.4.4 Figure 3.20 Minimized Total Cost vs. Detour Length (a) Q1=1,000 vph (b) Q1=1,500 vph (c) Q1=2,000 vph 79 3.7.3 Optimizing the Diverted Fraction Figure 3.21 shows the relation between total cost and diverted fraction for different flow rates. When the flow Q1 does not exceed maximum discharge rate along the work zone (1,200 vph) the total cost is lowest at boundary points of p, p=0 and 1.0. If Q1 is between 0 and 800 vph, the minimized total cost occurs at p=1 (Alternative 4.3, diverted all Q1 to detour); if Q1 is between 800 vph and 1,200 vph, the minimized total cost occurs at p=0 (Alternative 4.1, no diversion). If the flow Q1 exceeds the maximum discharge rate along the work zone (1,200 vph), the minimized total costs occur at the lowest points of p, p=0.2, 0.4, and 0.6 when flows Q1 are 1,500, 2,000, and 2,500 vph, respectively. Note that 15,00*(1-0.2)=1,200 and 2,000*(1-0.4)=1,200, which indicate that total cost is minimized if any vehicles beyond 1,200 vph from Q1 are detoured. 80,000 81,000 82,000 83,000 84,000 85,000 86,000 87,000 88,000 89,000 90,000 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 p (Diverted Fraction) To ta l C o st ($/ la n e . km ) Q1= 500 vph Q1=1,000 vph Q1=1,500 vph Q1=2,000 vph Q1=2,500 vph Figure 3.21 Total Cost vs. Diverted Fraction (Detour Length = 6km) 80 3.7.4 Summary In this section work zone cost models are developed for four alternative zone configurations on four-lane roads, with and without an alternate route. The optimized zone length and preferred alternative are determined for various combinations of variables. In the threshold analysis presented, traffic flow Q1 and setup cost z1 affect the rankings of alternatives. For example, in the flow threshold case, beyond the first threshold of 800 vph, Alternative 4.1 becomes preferable to Alternative 4.3; beyond the second threshold of 1,200 vph, Alternative 4.2 (p=0.3) becomes preferable to Alternative 4.1; beyond the third threshold of 1700 vph, Alternative 4.2 (p=0.6) becomes preferable to Alternative 4.2 (p=0.3). Alternative 4.4 might be selected only if an alternate road is unavailable and Q2 is relatively low. 81 Chapter IV Work Zone Optimization for Time-Dependent Inflows According to the previously developed steady-flow models (Sections 3.3 and 3.4), optimized work zone length is quite sensitive to traffic volume. A zone length and its related work duration optimized for one traffic level may be quite sub-optimal if traffic volumes change significantly before the work is completed. Therefore, a different methodology is needed to optimize the total cost under time-dependent inflows. Chien et al. (2002) developed a model to optimize the scheduling of work zone activities associated with traffic control for two-lane two-way highways where one lane at a time is closed. However, their inflows are overly simplified and the ?greedy? search approach used to determine each zone length tends to produce sub-optimal results. Jiang and Adeli (2003) used neural networks and simulated annealing to optimize only one work zone length and starting time for a four-lane freeway, considering factors such as darkness and numbers of lanes closed; however, a multiple-zone project were not considered. Complete scheduling plans for multiple-zone maintenance projects can be optimized with the method presented in this chapter. A methodology is developed here to optimize an entire work zone project under time-dependent inflows. Efficient scheduling and traffic control through work zones may significantly reduce the total cost, including agency cost and user cost. Based on time-dependent inflows, the issues considered in this chapter include: 1. What is the best starting time for the project? 2. Into how many zones should the project be divided? 3. What are the best starting times for each zone? 4. What should be the length for each zone? 82 5. What should be the work duration for each zone? 6. Should the ending time of one work zone be the starting time of next work zone or should there be a work pause between some successive zones, based on the trade-offs among maintenance costs, user costs and idling costs? One work zone plan example for time-dependent inflows is illustrated in Figure 4.1. Time 0 1 32 54 76 98 10 131211 161514 17 201918 24232221 100 500 400 300 200 900 800 700 600 1,000 1,100 350 552 1,152 1002 800 650 600 552 650 852 1,100 845 750 702 600 500 350 900 Fl o w (vp h) D1D2 D3 D4 Di Pause Pause Di+1Dm........................... ........... t s,1 t s,i+1 t s,its,4ts,3ts,2 t s,m t e,i t e,m t e,1 t e,i+1 Figure 4.1 Work Zone Activities under Time-Dependent Inflows A model for optimizing work plans, including zone lengths, work durations, starting times, pausing times (if any), and control cycle times (if two-lane highways) is presented in this chapter. This is done by minimizing total cost, including agency cost (maintenance cost and idling cost) and user cost (user delay cost and accident cost), while taking into account traffic demand variations over time. Two optimization methods, Powell?s (Press et al., 1988) and Simulated Annealing (Kirkpatrick et al., 1983), are adapted for this problem and compared. In this chapter, work zone are optimized for 83 Alternative 2.1 (two-lane highways) and Alternative 4.1 (four-lane highways). Finally, the reliability of the Simulated Annealing algorithm is presented. 4.1 Work Zone Cost Function for Time-Dependent Inflows 4.1.1 Model Formulation ? Two-Lane Two-Way Highways (Alternative 2.1) Schonfeld and Chien (1999) developed a work zone cost function which includes user delay and maintenance cost for two-lane highways. Using deterministic queuing analysis for control cycles that alternate traffic directions past work zones, the queuing delays per cycle (each cycle having two phases, one for each direction of travel) incurred in the work zone are derived as follows: ))(( 21211 tttrQ2 1Y ++= (4.1) ))(( 21122 tttrQ2 1Y ++= (4.2) )( )( 21 21 1 QQ H 3600 QQ H 3600 r t  + = (4.3) )( )( 21 12 2 QQ H 3600 QQ H 3600 r t  + = (4.4) Y1 is delay per cycle in Direction 1 and Y2 is delay per cycle in Direction 2. Note that t1 is the discharge phase for servicing the traffic flow Q1 in Direction 1, while t2 is the discharge phase for servicing Direction 2. The average clearance time r is the work zone length L divided by the average vehicle moving speed V. Then: 84 2 21 2 1 2 1 1 QQ H 3600HV Q H 3600LQ36002 Y )( )(  ?? = (4.5) 2 21 2 2 2 2 2 QQ H 3600HV Q H 3600LQ36002 Y )( )(  ?? = (4.6) Consider work zone i of length Li, which is one of the zones on a maintained road. The number of cycles Ni for zone i is the maintenance duration for zone i divided by the cycle time. Ni can be obtained as: i 2 i 1 i i tt D N + = (4.7) In Eq.(4.7), i1t is the duration of the discharge phase in Direction 1 for work zone i, while i2t is the duration of the discharge phase in Direction 2 for zone i. Di is the total maintenance duration for zone i, which is linear according to the assumption in Eq (3.3): i43i LzzD += (4.8) The total queuing delay cost for work zone i is v tt D)YY(vYNC i 2 i 1 i 21iqi + +== (4.9) where Y is total delay per cycle. Substituting Eqs.(4.1), (4.2), (4.3), (4.4) (4.8) into Eq.(4.9), we obtain: )QQ H 3600(V v)]Q H 3600(Q)Q H 3600(Q[L)Lzz( C 21 2211ii43 qi  ++ = (4.10) The maintenance cost for work zone i, Cmi, is according to the assumption in Eq (3.4): 85 i21mi LzzC += (4.11) Then, the total cost for work zone i, Cti, is )QQ H 3600(V v)]Q H 3600(Q)Q H 3600(Q[L)Lzz( LzzCCC 21 2211ii43 i21qimiti  ++ ++=+= (4.12) where Cti = total cost for work zone i; Cmi = maintenance cost for work zone i; Cqi = user queuing delay cost for zone i. We consider the varying traffic flows in Directions 1 and 2 over one day. A maintenance project for a two-lane two-way road with total length LT in one direction would be maintained by scheduling m work zones over the entire maintenance period. Assume that zone i (i = 1, 2, ?., m) is resurfaced over n duration units (different zones would likely have different n values) and Dij (j =1, 2, ?., n) is a duration unit selected so that in it inflows stay appropriately constant, as shown in Figure 4.2. Then the duration for zone i, denoted Di, is: = = n 1j iji DD (4.13) Fl o w (vp h) Time Di Di2 Dij Din......Di1 ...... Figure 4.2 Duration for Work Zone i with Time-dependent Traffic Inflows 86 Here we assume that Dij is a short duration unit for work zone activities that cannot be further subdivided, such as 0.06 hr. (Because the zone length unit is assumed to be 0.01 km in this study, duration unit = length unit * z4 = 0.01 km * 6 hr/lane.km=0.06 hr.) ij1Q and ij2Q represent the varying traffic flows in Directions 1 and 2 during the period j for zone i. The number of cycles Nij per traffic flow period is the duration of that period Dij divided by the cycle time ( ij1t + ij2t ). Nij can be obtained as: ij 2 ij 1 ij ij tt D N + = (4.14) where ij1t and ij2t are the discharge phases for traffic flows ij1Q in Direction 1 and ij2Q in Direction 2, respectively. Then the user queuing delay cost for zone i can be formulated as: = n j ij ij qi vNYC (4.15) + ?? +  ?? = += n j ij 2 ij 1 ij 2ij 2 ij 1 2 ij 2 2 i ij 2 2ij 2 ij 1 2 ij 1 2 i ij 1 n j ij ij 2 ij 1qi v tt D] )QQ H 3600(HV )Q H 3600(LQ36002 )QQ H 3600(HV )Q H 3600(LQ36002 [ vN)YY(C (4.16) where )QQ H 3600( )QQ H 3600(r t ij 2 ij 1 ij 2 ij 1i ij 1  + = (4.17) )( )( ij 2 ij 1 ij 1 ij 2i ij 2 QQ H 3600 QQ H 3600 r t  + = (4.18) V L r ii = (4.19) 87 Eqs.(4.17) and (4.18) indicate that the one-way traffic control is time-dependent. The phases in Directions 1 and 2 are determined with the time-dependent flows ij1Q and ij 2Q . Substituting Eqs.(4.17), (4.18), (4.19) into Eq.(4.16), we obtain:  + = n j iij ij 2 ij 1 ij 2 ij 2 ij 1 ij 1 qi LD )QQ H 3600(V v)]Q H 3600(Q)Q H 3600(Q[ C (4.20) The moving delay cost of the traffic flows Q1 and Q2 in work zone i, denoted viC , is the cost increment due to the zone. The moving delay for zone i in each period Dij of work zone duration Di is equal to the flow (Q1 + Q2) multiplied by: (1) the period, Dij, (2) the travel time difference over the zone length Li with the work zone, V Li , and without the work zone, 0 i V L , and (3) the value of time, v. Thus: += n j 0 ii ij ijij vi v)V L V L(D)QQ(C 21 (4.21) Idling cost is also considered in work zone activities with time-dependent inflows. This idling cost is equal to idling time multiplied by the average cost of idling time for crews and equipment. Idling time is a pause between two successive work zones, denoted ti = (ts,i ? te,i-1). The idling cost per zone iIC is: idiI tvC = (4.22) where vd is average cost of idling time, ts,i is the starting time for zone i, and te,i-1 is the ending time for zone i-1. Note that ti is 0 for i=1. 88 The accident cost incurred by the traffic passing the work zone can be determined from the number of accidents per 100 million vehicle hours na multiplied by the product of the increasing delay (Cqi/v+Cvi/v) and the average cost per accident va (Chien and Schonfeld, 2001), where Cqi/v is the queuing delay and Cvi/v is the moving delay for work zone i. The accident cost per work zone Cai is formulated as: 8 aaviqi ai 10 vn v )CC( C + = (4.23) The total cost for work zone i, Cti, is 8 aaviqi idviqii21ti 10 vn v )CC( tvCC)Lzz(C ++++++= (4.24) The total cost of the maintenance project for resurfacing road length LT by scheduling m work zones, CPT ($/project), is expressed as: + +++++= = m i 8 aaviqi m i id m i vi m i qi m i i21 m i tiPT 10 vn v )CC( tvCC)Lzz( CC (4.25) The objective function is: = m i tiPT CMinCMin (4.26) subject to T m i i LL = (4.27) The total cost in Eq.(4.25) will be minimized with Powell?s method as well as with the Simulated Annealing algorithm proposed in Section 4.2. Numerical analyses for two-lane highway work zones are presented in Section 4.3. 89 4.1.2 Model Formulation ? Four-Lane Two-Way Highways (Alternative 4.1) Chien and Schonfeld (2001) developed a work zone cost function, which includes the user delay, the accident, and the agency costs, for four-lane two-way highway without considering a detour (Figure 3.2(a)). The user delay cost consists of the queuing delay costs upstream of work zones and the moving delay costs through work zones. The equations of queuing delay and moving delay costs are shown in Section 3.4.2. Consider the varying traffic flows in Directions 1 and 2 over one day. A maintenance project for a four-lane two-way road with total length LT in one direction would be maintained by scheduling m work zones over the entire maintenance period. Assume that zone i (i = 1, 2, ?., m) is resurfaced over n duration units (different zones would likely have different n values) and Dij (j =1, 2, ?., n) is a duration unit selected so that in it inflows stay appropriately constant, as shown in Figure 4.2. Here we consider work zone i of length L, which is one of the zones along the total length LT of a maintained road. Eq.(3.27), which estimates queuing delay cost for steady traffic inflows, cannot be applied directly for time-dependent inflows because it considers only one work zone, whose resulting queue might be dissipated after the zone is completed. In a multiple-zone project under time-dependent inflows, a new zone may begin immediately after the previous zone is completed; however, the queue is unlikely to be dissipated completely before next zone is started. In such a case, queuing delay costs for four-lane highway work zone are computed numerically. Queuing delay costs are illustrated here. If flow ij1Q does not exceed cw, the queuing delay is zero. Figure 4.3 shows the dissipation of queue length along zone duration if flow ij1Q exceeds cw. Assume the 90 queue due to work zone i-1 has not been dissipated completely before zone i begins in Figure 4.3 and there exists queue length qi-1 as the zone i starts. The maximum queue length for zone i (area of A plus qi-1) is: 1-ji,w 1-ji, 1i2w i2 1i1w 1i 11imaxi, )Dc-........(Q)Dc-(Q)Dc-Q(qq +++=  (4.28) The area of A plus qi-1 is equal to the area of B, the number of dissipated vehicles. Figure 4.3 indicates that queue is dissipated completely before the next zone begins so that the work zone i is completed at te,i while there is still a remaining dissipation time trd,i for its zone. Then the queuing delay for work zone i is the area of C. The queuing delay cost for zone i is: v)Cofarea(Cqi = (4.29) Flow (vph) Time (hr) Queue Length c w c0 A B C ij ij 1w D)Qc(  Time (hr) ij 1Q C Di Di1 Di2 DinDij......... ......... ti+1 1iw 1i 1 D)cQ(  2iw 2i 1 D)cQ(  in in 1w D)Qc(  t s,i te,i t rd,i qi-1 Di+1 Figure 4.3 Queuing Delay and Queue Dissipation for Four-Lane Highway Work Zone 91 The moving delay cost of the traffic flows Q1 in work zone i, denoted viC , is the cost increment due to the zone. It is the moving delay ijmt multiplied by the average delay cost v: = = n 1j ij mvi vtC (4.30) where ijmt = moving delay incurred by the approaching traffic flow ij1Q for zone i in each period Dij of work zone duration Di. ijmt is a function of the difference between the travel time on a road with and without a work zone: w ij 1ij ij 1 a i w iij m cQ whenDQ)V L V L(t = (4.31a) w ij 1ijw a i w iij m cQ whenDc)V L V L(t >= (4.31b) where Va = average approaching speed; Vw = average work zone speed. If ij1Q is greater than cw, the variable ij1Q is reduced by cw (the maximum flow allowed to pass through the work zone). Idling cost and accident cost have the same formulations as the Equations (4.22) and (4.23). The idling cost per zone iIC is: idiI tvC = (4.22) The accident cost per work zone Cai is formulated as: 8 aaviqi ai 10 vn v )CC( C + = (4.23) The maintenance cost for work zone i, Cmi, is according to assumption in Eq (3.4): i21mi LzzC += (4.11) 92 The total cost for work zone i, Cti, is: 8 aaviqi idviqii21ti 10 vn v )CC( tvCC)Lzz(C ++++++= (4.32) The total cost for resurfacing road length LT by scheduling m work zones, CPT ($/project), is expressed as: + +++++= = m i 8 aaviqi m i id m i vi m i qi m i i21 m i tiPT 10 vn v )CC( tvCC)Lzz( CC (4.33) The objective function is: = m i tiPT CMinCMin (4.26) subject to T m i i LL = (4.27) The total cost in Eq.(4.33) will be minimized with Powell?s method and with the Simulated Annealing algorithm proposed in Section 4.2. Numerical analyses for four-lane highway work zones are presented in Section 4.4. 93 4.2 Optimization Methods A good optimization method should usually reach a good solution quickly, without excessive memory requirements. Two optimization methods that were deemed suitable for this problem are adapted and compared here. One is a classic direction-set method, called Powell?s Method (Press et al., 1988), and the other is a heuristic Simulated Annealing algorithm (Press et al., 1988, Kirkpatrick et al., 1983). The optimized variables of the total cost function include the work zones lengths Li and starting times ts,i required to complete the project. The zone ending times te,i, the duration of maintenance pauses between two work zones ti, and the time-dependent cycle lengths for discharging directional traffic over different time periods (if two-lane highways) can be uniquely determined from the optimized variables Li and ts,i. 4.2.1 Powell?s Method This method may be applied when derivatives of the objective function are difficult or impossible to specify. The basic concept of Powell?s Method is as follows (Press et al., 1988): Take the unit vectors e1, e2, ?.eN as a set of directions. Using one- dimensional optimization, move along the first direction to the cost function?s minimum, then from there along the second direction to its minimum, and so on, cycling through the whole set of directions as many times as necessary, until the function stops decreasing. The steps of Powell?s Method are as follows: 94 Step 0: Initialize the set of directions ui to basic vectors, ui=ei i=1, ?.., N Repeat the following sequence of steps until cost function stops decreasing. Step 1: Save the starting position as P0. Step 2: For i=1, ?, N, move Pi-1 to the minimum along direction ui and call this point Pi. Step 3: For i=1, ?, N-1, set ui  ui+1. Step 4: Set uN  PN - P0. Step 5: Move PN to the minimum along direction uN and call this point P0 In this study, work zone lengths and starting times are defined as vectors ei because other variables, e.g. zone durations, ending times, can be derived from the relation between zone length and duration, shown in Assumption 3. The solution Pi is equal to (L1, L2,.., Li,?, Lm, ts,1, ts,2,?, ts,i, ?, ts,m), where m is the number of work zones. The sequence of directions for each successive iteration (step 1 to step 5) in searching for the minimized total cost is as follows: (L1)  (L2, ts,2)  ?.  ( Li, ts,i) ?  (Lm, ts,m). ( Li, ts,i) indicates that zone length Li and starting time ts,i are determined simultaneously. Note that ts,1 is the project starting time, given from input data. The procedures from Step 1 to Step 5 are repeated until total cost stops decreasing. 95 4.2.2 Simulated Annealing Algorithm Introduction Simulated annealing (SA) is a stochastic computational technique derived from statistical mechanics for finding near globally optimum solutions to large optimization problems. It was developed by Metropolis (1953) to simulate the annealing process of crystals on a computer. Kirkpatrick et al. (1983) adapted this methodology to an algorithm exploiting the analogy between annealing solids and solving combinatorial optimization problems. The simulated annealing search process attempts to avoid becoming trapped at a local optimum by using a stochastic computational technique to find globally or near globally optimal solutions to combinatorial problems. The original concept of SA from thermodynamics is that liquids freeze and crystallize, or metals cool and anneal. The SA algorithm is illustrated in pseudo-code in Table 4.1. Kirkpatrick et al. generalized an approach by introducing a multi-temperature approach in which the temperature is lowered slowly in stages. The outer loop (begin1 ?..end1) in Table 4.1 indicates that the temperature T is lowered by updating T in each outer loop until T is less than or equal to Tf. The inner loop (begin2 ?..end2) indicates that at each temperature the system repeats searching for a lower energy state until the system reaches equilibrium. A system in thermal equilibrium at temperature T has its energy probabilistically distributed, according to the Boltzmann probability distribution, )/exp(~)( kTEEProb  , where k is Boltzmann?s constant (Metropolis, 1953). At each temperature a neighboring solution S? is chosen at random and the energy change (total cost change), , is computed, where =E(S?)-E(S). E(S?) is the energy (total cost) of the new neighboring solution and E(S) is the energy (total cost) of the previous solution. The 96 new solution is accepted with the probability 1 if 0, and with probability e- /T if >0. Note that the simulated annealing procedure allows occasional ?uphill moves? that have higher energy (total cost) than the current solution in order to avoid getting trapped at a locally optimal solution. These uphill moves are controlled probabilistically by the temperature T and become decreasingly likely toward the end of the process as T decreases (Press et al., 1988). Table 4.1 Simulated Annealing Algorithm Sub Anneal S = Initial solution S0 T = Initial temperature T0 Do while (T > Tf): (begin1) Do while (not yet in equilibrium): (begin2) S? := Some random neighboring solution of S := E(S?) ? E(S) (or := TC(S?) ? TC(S);) Prob := min (1, e- /T) If random(1,0) Prob then S:= S? Loop (end2) Update T Loop (end1) Output best solution End Sub [Wong, 1988, Modified by Chen, 2003] Simulated Annealing Algorithm for Work Zone Optimization The SA algorithm adapted here for work zone optimization is as follows: Step 0. Generate an initial solution. Calculate average flow volume between two peak traffic periods, Q . Given a project starting time, the initial work zone length Li and duration Di can be obtained by using the traffic volume Q for each stage and optimizing for steady traffic inflows using steady-demand model in Chapter 3. Here a stage is the 97 period between two adjacent peak traffic volumes. The stage duration is denoted Ds,l, l=1, 2, ?, as shown in Figure 4.13(b). The number of zones in each stage depends on how many Di can be contained within the stage duration. The solution S=(L1, L2,.., Li,?, Lm, ts,1, ts,2,?, ts,i, ?, ts,m) is the initial solution for work zone lengths and starting times. Set j=1 and k=1, j=1 to Jmax and k=1 to Kmax. Set the values of T0 and Tf . Step 1. Generate a neighboring solution. Randomly generate four numbers: n1, n2, n3, and n4. n1 and n2 are two zones chosen randomly from all work zones in the previous solution. n1 or n2 is equal to 1+int(m*r), where int is a function that takes only the integer part of a real number; r is a uniform random number between 0 and 1. n3 is a binary random number; in it 0 indicates that zone length decreases by one unit in zone n1 and increases by one unit in zone n2 while 1 indicates zone length increases by one unit in zone n1 and decreases by one unit in zone n2. n4 is a binary random number, in which 0 or 1 indicates that an ?increasing event? or ?decreasing event? occurs in the end or in the beginning of zones, respectively. When zone n1 is randomly chosen, i=n1, and that zone length increases or decreases by one unit, from Li to 'iL , while zone n2 will decrease or increase by one unit, from Lj to 'jL , to keep the total project length unchanged. Other zone lengths stay unchanged. The details for ?Increase? (including ?Increase in end? and ?Increase in begin?), ?Decrease? (including ?Decease in end? and ?Decrease in begin?), ?Check last zone?, and ?Delete zone?, are shown from Figures 4.5 to 4.12. The neighboring solution S?=(L1, L2,.., 'iL ,.. 'jL ,.., ts,1, ts,2, ? ' i,st , ?. ' j,st ,? ts,m) is generated after one ?Decrease? event and one ?Increase? event. Compute the objective function value and the difference between the new and previous total costs, TC = TC(S?) ? TC(S). If TC<0, go to Step 3. Otherwise, go to Step 2. 98 Step 2. ( TC>0) Select a random variable )1,0(U . If )T/TCexp()TC(Prob j  < , then go to Step 3. If )T/TCexp()TC(Prob j   , then reject this new solution and go to Step 4. Step 3 ( TC<0 or )TC(Prob  < ) Accept the new solution S? and new total cost TC(S?). Store the new solution and total cost. Step 4 If Tj>Tf and kTf and k=Kmax, then reduce Tj, j=j+1, k=1, and go to Step1. Otherwise, stop. The flow chart of simulated annealing algorithm for work zone optimization is shown in Figure 4.4. The new variables shown in Figures 4.4 to 4.12 are defined as follows: Ds,l: duration of Stage l; Jmax: number of iterations for reducing temperature from T0 to Tf; Kmax: maximum number of iterations for temperature Tj to equilibrium; Lassign: deleted last zone length divided by m-1, which is averagely assigned to the previous m-1 zones; Lavg: average zone length in current solution; Lmin: minimum zone length in current solution; LR: project remaining length; LT: project length; m: number of work zones of a maintained project; Nlimit: maximum number of successful iterations for temperature Tj to equilibrium; Nsucc: cumulative number of successful iterations for temperature Tj to equilibrium; 99 Nr,succ: cumulative number of successful iterations for repeating generating neighbor solution using the same random numbers under temperature Tj; Tf : final temperature; T0: initial temperature; D: duration unit for increasing or decreasing a unit length, D= L*z4; Dr: duration difference between new te, i and old ts, i+1 when new te, i exceeds old ts, i+1; L: length unit for increasing or decreasing, baseline=0.01km; Lr: length difference between length unit and the remaining length of the deleted zone; ti: idle time between zone i and zone i-1; i it : cumulative idle times from zone 1 to zone i; 100 Call Decrease(n2) Call Increase(n1) N succ >Nlimit or k=K nmax No Yes Yes n3=0n3=1 N succ =0 or T=Tf (j=Jmax) Final Solution Reduce T k=k+1 Call Decrease(n1) Call Increase(n2) Generate Random Neighboring Solution Calculate TC Prob=min(1,e- C/Tj)  < Prob TC<0 Update Solution Keep Previous Solution N r,succ = N r,succ + 1 No Yes No Yes k=1 Given Starting Time & Intial Solution Set T0 , Jmax, Kmax j=1 Randomly Choose 1.Two zones, n1, n2 2. Increase or Decrease, n3 No N r,succ >0 N succ = N succ + 1 No Yes Call Checklastzone j=j+1 Figure 4.4 Flow Chart of Simulated Annealing Algorithm for Work Zone Optimization 101 i>1 Li=Li - L Decrease(i) Start No Li<0 Yes Call Decreaseinend(i) Call Decreaseinbegin(i) Decrease(i) End i=1 n4=1n4=0 Call DeleteZoneIsDeleteZone=True Figure 4.5 Decrease Event Call Increaseinend(i) Call Increaseinbegin(i) Increase(i) End i >1i=1 n4=1n4=0 Li=Li+ L Increase(i) Start Li=Li+ Lr IsDeleteZone True False Figure 4.6 Increase Event 102 Increaseinend End ti+1> D No Yes No t e,i=te,i+ D t e,i=te,i+ D D r =t e,i-ts,i+1 i=i+1 ti+1< Dr t e,i=te,i+ Dr D r =t e,i-ts,i+1 i=i+1 Yes Increaseinend Start i=m No Yes Figure 4.7 ?Increaseinend? Event Increaseinbegin End Increaseinbegin Start No Yes No t s,i=ts,i - D t s,i=ts,i - D D r =t e,i-1-ts,i i=i-1 ti< Dr t s,i=ts,i - Dr D r =t e,i-1 - ts,i i=i-1 Yes Call Increaseinend Increaseinbegin Exit Yes No ti> D Dt i i < Figure 4.8 ?Increaseinbegin? Event 103 Decreaseinend Start t e,i=te,i - D Decreaseinend End i=m ti+1=ts,i+1 - te,i No Yes Figure 4.9 ?Decreasinend? Event DecreaseinBegin Start t s,i=ts,i + D No Decreaseinbegin End Yes i=1 CallDecreaseinend Decreaseinbegin Exit Figure 4.10 ?Decreaseinbegin? Event 104 Checklastzone Start Checklastzone End Yes No L assign= L m /(m-1) L m <0.8L min Adjust Solution m=m-1 Yes No L assign=Lm-Lavg L m =L avg L m+1=Lassign m=m+1 L m >1.2LAvg Calculate Update Cost TC2 Keep Previous Solution Calculate Current Cost TC1 TC2= (5.45b) The moving delay cost of the diverted flow ij1pQ from Direction 1, denoted as 42 i,vpC , is: v] V L V L V LL[DpQC n j 0 t 3* d 2d 0 3d1d i ij 1 42 i,vp ++= (5.46) The moving delay cost 42 i,3vC to the original flow on the detour, ij3Q , as affected by the ij1pQ is: 137 = n j 0d 2d 3* d 2d i ij 3 42 i,3v v)V L V L(DQC (5.47) The combined moving delay cost for the maintained road AB and the detour 42 viC can be derived as: 42 i,3v 42 i,vp 42 i),p1(v 42 vi CCCC ++=  (5.48) The idling cost for zone i 42iIC is: id 42 iI tvC = (5.49) The accident cost for zone i, 42iaC , is formulated as: 8 aa 42 vi 42 qi42 ai 10 vn v )CC( C + = (5.50) The maintenance cost for zone i, 42 miC , is i21 Lzz + . Then the total cost for zone i, 42 tiC , is: 8 aa 42 vi 42 qi id 42 vi 42 qii21 42 ti 10 vn v )CC( tvCC)Lzz(C ++++++= (5.51) The total cost for resurfacing road length LT by scheduling m work zones, 42PTC , is expressed as: + +++++= = m i 8 aa 42 vi 42 qi m i id m i 42 vi m i 42 qi m i i21 m i 42 ti 42 PT 10 vn v )CC( tvCC)Lzz( CC (5.52) 138 Alternative 4.3 ? All Q1 traffic through detour, allowing work zone on both lanes in Direction 1 Figure 3.2(c) shows the entire flow ij1Q in Direction 1 being diverted to the alternate route. There is no queuing delay in Direction 1. The possible queuing delay cost of the diverted flow ijQ1 and ij3Q in Direction 3 for zone i, denoted 43, iqdC , is the area of C in Figure 5.1 multiplied by v. v)Cofarea(C 43 i,qd = (5.53) The user delay cost of the diverted flow ijQ1 from Direction 1 along detour due to intersection signal or stop delay, denoted as 43 iint,C , is: v 3600 tNDQC n j int inti ij 1 43 iint, = (5.54) The combined queuing delay cost for the maintained road AB and the detour 43 qiC can be derived as: 43 iint, 43 i,qd 43 qi CCC += (5.55) The moving delay cost of the diverted flow ijQ1 from Direction 1, denoted as 43 i,1vC , is: v] V L V L V LL[DQC n j 0 t 3* d 2d 0 3d1d i ij 1 43 i,1v ++= (5.56) The moving delay cost 43 i,3vC to the original flow on the detour, ij3Q , as affected by the ijQ1 is: = n j 0d 2d 3* d 2d i ij 3 43 i,3v v)V L V L(DQC (5.57) 139 The combined moving delay cost for the maintained road AB and the detour 43 viC can be derived as: 43 i,3v 43 i,1v 43 vi CCC += (5.58) The idling cost for zone i 43 i,idleC is: id 43 i,idle tvC = (5.59) The accident cost for zone i, 43iaC , is formulated as: 8 aa 43 vi 43 qi43 ai 10 vn v )CC( C + = (5.60) The maintenance cost for zone i, 43 miC , is i21 Lzz + . Then the total cost for zone i, 43 tiC , is: 8 aa 43 vi 43 qi id 43 vi 43 qii21 43 ti 10 vn v )CC( tvCC)Lzz(C ++++++= (5.61) The total cost for resurfacing road length LT by scheduling m work zones, 43PTC , is expressed as: + +++++= = m i 8 aa 43 vi 43 qi m i id m i 43 vi m i 43 qi m i i21 m i 43 ti 43 PT 10 vn v )CC( tvCC)Lzz( CC (5.62) Alternative 4.4 ? Crossover of all Q1 traffic into one opposite lane, allowing work on both lanes in Direction 1 Figure 3.2(d) shows that the entire flow ijQ1 in Direction 1 crosses over to one lane in the opposite direction. Both lanes in Direction 1 are closed for a work zone. The 140 flow ij2Q in Direction 2 only uses the remaining lane. The user queuing delay cost of the flow ij1Q in Direction 1 for work zone i, 44 i,1qC , is: v)Cofarea(C 44 i,1q = (5.63) where the area C is the queuing delay of the flow ij1Q , as shown in Figure 4.3. The user queuing delay cost of the flow ij2Q in Direction 2 for work zone i, 44 i,2qC , is: v)Cofarea(C '44 i,2q = (5.64) where the area of C? is the queuing delay of the flow ij2Q . Area C? is determined as area C but with ij2Q substituted for ij1Q . The combined queuing delay cost for the maintained road AB and the detour 44 qiC can be derived as: 44 i,2q 44 i,1q 44 qi CCC += (5.65) The moving delay cost of the traffic flows ij1Q in work zone i, denoted 44 i,1vC , is: w ij 1ij ij 1 a i w i44 i,1v cQ whenvDQ)V L V L(C = (5.66a) w ij 1ijw a i w i44 i,1v cQ whenvDc)V L V L(C >= (5.66b) The moving delay cost of the traffic flows ij2Q in work zone i, denoted 44 i,2vC , is: w ij 2ij ij 2 a i w i44 i,2v cQ whenvDQ)V L V L(C = (5.67a) w ij 2ijw a i w i44 i,2v cQ whenvDc)V L V L(C >= (5.67b) 141 The combined moving delay cost for the maintained road AB and the detour 44 viC can be derived as: 44 i,2v 44 i,1v 44 vi CCC += (5.68) The idling cost for zone i 44 i,idleC is: id 44 i,idle tvC = (5.69) The accident cost for zone i, 44iaC , is formulated as: 8 aa 44 vi 44 qi44 ai 10 vn v )CC( C + = (5.70) The maintenance cost for zone i, 44 miC , is i21 Lzz + . Then the total cost for zone i, 44 tiC , is: 8 aa 44 vi 44 qi id 44 vi 44 qii21 44 ti 10 vn v )CC( tvCC)Lzz(C ++++++= (5.71) The total cost for resurfacing road length LT by scheduling m work zones, 44PTC , is expressed as: + +++++= = m i 8 aa 44 vi 44 qi m i id m i 44 vi m i 44 qi m i i21 m i 44 ti 44 PT 10 vn v )CC( tvCC)Lzz( CC (5.72) 142 5.2 Optimization Methods 5.2.1 Uniform Alternatives and Mixed Alternatives Until now, the same alternative was assumed to be applied in all zones of one project, which is called uniform alternatives here. Numerical examples for uniform alternatives will be analyzed in Sections 5.3 and 5.4 for two-lane highway and four-lane highway work zones based on the Simulated Annealing algorithm developed in Chapter 4, which is called ?SAUA? (Simulated Annealing algorithm for Uniform Alternatives). If the alternatives consider a single detour, i.e. Alternatives 2.2, 2.3, 2,4, 4.2, and 4.3, the SA algorithm is called ?SAUASD? (SAUA with a Single Detour). In this section, we consider the possible advantages of using different alternatives for different zones within a project. Sections 5.1 and its numerical examples indicate that the optimization for uniform alternatives is developed and alternative selection is determined by which alternative (and what diverted fraction if Alternative 2.2 or 4.2 is preferable) yields the lowest total cost. Each project is optimized by a given single alternative, with or without a detour. However, lower minimized total cost for a project may be obtained by mixing several alternatives within a project. A traffic management plan combining different alternatives is shown in Figure 5.2. For example, Alternatives 2.3 and 2.2 might have minimized total cost during the off-peak period and Alternative 2.1 might have minimized total cost during the peak period. An improved Simulated Annealing algorithm is developed here to search through possible mixed alternatives and diverted fractions for all zones within a project in order to minimize total cost. The improved method is called ?SAMASD? (Simulated Annealing 143 algorithm for Mixed Alternatives with a Single Detour). Thus, two traffic management plans are developed with uniform alternatives and with mixed alternatives within a single project. To ta l c o st Alt 2.2 Alt 2.1 Alt 2.3 Time31T 21T Alt 2.4 Time Fl o w Figure 5.2 Traffic Management Plan Combining Different Alternatives 5.2.2 Simulated Annealing Algorithm for Mixed Alternatives with a Single Detour- SAMASD Figure 5.3 shows the improved Simulated Annealing algorithm for integrating mixed alternatives within a project. This SAMASD algorithm is developed by modifying the Simulated Annealing algorithm developed in Section 4.2.2. The SAMASD algorithm is shown as follows: 1. Add new variables Ai, pi, Aopt,i , popt,i in the Step 0 in Section 4.2.2, where Ai: Alternative for zone i, Ai=2.1, 22, 23,and 24, i=1, ?., m; 144 pi: diverted fraction for zone i, pi = 0 - 1, i=1, ?., m; Aopt,i: final optimal Alternative for zone i, Aopt,i=21, 22, 23,and 24, i=1, ?., m; popt,i: final optimal diverted fraction for zone i, popt,i = 0 - 1, i=1, ?., m. The notation for two-lane highway alternatives is applied here. ?21? represents Alternative 2.1. For four-lane highway work zones, 21, 22, 23, and 24 can be substituted for 41, 42, 43, and 44, respectively. Set the initial Aopt,i, =21, popt,i =0, i=1, ?., m for all zones. 2. Add ?Determine alternatives and diverted fraction for n1 and n2? after generating random neighboring solution in Step 1. Test all possible Ai and pi combinations and calculate the total cost. If the total cost for the current combination is lower than for the previous combination, update Aopt,i and popt,i; otherwise, keep the previous solution. This procedure terminates when all possible Ai and pi combinations are tested. Figure 5.4 shows the flow chart for determining alternatives and diverted fractions in SAMASD. 145 Call Decrease(n2) Call Increase(n1) N succ >Nlimit or k=K nmax No Yes Yes n3=0n3=1 N succ =0 or T=Tf (j=Jmax) Final Solution Reduce T k=k+1 Call Decrease(n1) Call Increase(n2) Calculate TC Prob=min(1,e- C/Tj)  < Prob TC<0 Update Solution Keep Previous Solution N r,succ = N r,succ + 1 No Yes No Yes k=1 Given Starting Time & Intial Solution Set T0 , Jmax, Kmax Set A opt,i= 21, popt,i= 0 for all initial zones j=1 Randomly Choose 1.Two zones, n1, n2 2. Increase or Decrease, n3 No N r,succ >0 N succ = N succ + 1 No Yes Call Checklastzone j=j+1 Generate Random Neighboring Solution Determine Alternatives and p for Zones n1, n2 Figure 5.3 SAMASD Algorithm 146 i=0 i=11 Yes l=0 l=11 A n2=24 p n2=1 Yes A n1=24 p n1=1 No p n1 = i /10 A n1=21 p n1= 0 pn1= 1 A n1=23An1=22 0 < p n1<1 No p n2 = l /10 A n2=21 p n2= 0 pn2= 1 A n2=23An2=22 0 < p n2<1 TC cur =TC Calculate New Total Cost TC' TC'= (6.9b) The moving delay costs for ij1pkQ and ij1Q)k1(p  along the detour are considered separately. The moving delay cost of the diverted flow ij1pkQ from Direction 1, denoted as 82 i,vpkC , is: v] V L V L V L V LL[DpkQC n j 0 AB 3* FD,d FD 3* CF,d CF 0 DBAC i ij 1 82 i,vpk +++= (6.10) where ACL , DBL , and CDL are the lengths of segments AC, DB, and CD along the detour and ABL is the length of AB along the main road. 3* CF,dV is the detour speed affected by ij 1pQ along CF. 3* FD,dV is the detour speed affected by ij1Q)rqrprpk( + along FD. The moving delay cost of the diverted flow ij1Q)k1(p  from Direction 1, denoted as 82 i),k1(vpC  , is: v] V L V L V LL[DQ)k1(pC n j 0 AE 3* CF,d CF 0 FEAC i ij 1 82 i),k1(vp ++= (6.11) where FEL and CFL are the lengths of segments FE and CF along the detour and AEL is the length of AE along the main road. 172 The moving delay cost of the diverted flow ij1Q)qp1(r  from Direction 1, denoted as 82 i),qp1(vrC  , is: v] V L V L V LL[DQ)qp1(rC n j 0 EB 3* FD,d FD 0 DBEF i ij 1 82 i),qp1(vr ++= (6.12) where EFL is the length of segment EF along the detour and EBL is the length of EB along the main road. The moving delay cost of the diverted flow ij1qQ from Direction 1, denoted as 82 i,vqC , is: v] V L V L V LL[DqQC n j 0 AB 5* GH,d GH 0 HBAG i ij 1 82 i,vq ++= (6.13) where AGL and HBL are the lengths of segments AG and HB along the detour. 5* GH,dV is the detour speed affected by ij1qQ along GH in Direction 5. The moving delay cost of the original flow on the detour along CD, ij3Q , as affected by the ij1pQ and ij1Q)qp1(r  , denoted as 82 i,3vC , is: += n j 0d CD 3* FD,d FD 3* CF,d CF i ij 3 82 i,3v v)V L V L V L(DQC (6.14) The moving delay cost of the original flow on the detour along GH, ij5Q , as affected by the ij1qQ , denoted as 82 i,5vC , is: = n j 0d GH 5* GH,d GH i ij 5 82 i,5v v)V L V L(DQC (6.15) The combined moving delay cost for the maintained road AE and the detour 42 viC can be derived as: 173 82 i,5v 82 i,3v 82 i,vq 82 i),qp1(vr 82 i),k1(vp 82 i,vpk 82 i),p1(v 82 vi CCCCCCCC ++++++=  (6.16) 3. Idling Cost The idling cost for zone i 82iIC is: id 82 iI tvC = (6.17) 4. Accident Cost The accident cost for zone i, 82iaC , is formulated as: 8 aa 82 vi 82 qi82 ai 10 vn v )CC( C + = (6.18) 5. Maintenance Cost The maintenance cost for zone i, 82 miC , is i21 Lzz + . Then the total cost for zone i, 82 tiC , is: 8 aa 82 vi 82 qi id 82 vi 82 qii21 82 ti 10 vn v )CC( tvCC)Lzz(C ++++++= (6.19) 6. Total Cost The total cost for resurfacing road length LT by scheduling m work zones, 82PTC , is expressed as: + +++++= = m i 8 aa 82 vi 82 qi m i id m i 82 vi m i 82 qi m i i21 m i 82 ti 82 PT 10 vn v )CC( tvCC)Lzz( CC (6.20) The total cost in Eq.(6.20) will be minimized with the Simulated Annealing algorithms, including SAUAMD and SAMAMD. The SAUAMD (Simulated Annealing algorithm for Uniform Alternatives with Multiple Detour paths) follows the same 174 procedures as SAUASD but its cost function is replaced by Eq.(6.20) for multiple detour paths. SAMAMD is derived below. 6.2.3 Simulated Annealing Algorithm for Mixed Alternatives with Multiple Detour Paths - SAMAMD The optimization with SAUAMD and the threshold analysis for selecting alternatives in this case study will be presented in Section 6.4. Moreover, in order to further reduce total cost by considering mixed alternatives with different configurations in successive zones, an improved search method, SAMAMD (Simulated Annealing algorithm for Mixed Alternatives with Multiple Detour paths), is developed here for selecting alternatives in successive zones, where the diverted fractions, p and k, for each zone are optimized. The concept of this search method for multiple detour paths is similar to the SAMASD method shown in Section 5.2 but the new diverted fraction k along the additional detour is added and optimized. This search method can be obtained by modifying Figures 5.3 and 5.4. The SAMAMD algorithm is as follows: 1. Add new variables ki and kopt,i in Step 0 in Section 4.2.2 (the variables Ai, pi, Aopt,i, popt,i have been added in Section 5.2.2), where ki: diverted fraction of pQ1 along F  D  B for zone i, ki = 0 - 1, i=1, ?., m; kopt,i: final optimal diverted fraction of pQ1 along F  D  B for zone i, kopt,i = 0 - 1, i=1, ?., m. 175 The notation used for eight-lane highway alternatives is applied here. ?81? represents Alternative 8.1. For other multiple-lane highway work zones, Alternatives 8.1, 8.2, and 8.3 can be replaced. Set the initial Aopt,i, =81, popt,i =0, kopt,i =0, i=1, ?., m, for all zones. 2. Modify Figure 5.4. Test possible Ai, pi, and ki combinations and calculate the total cost for the current combination. If the total cost for the current combination is lower than for the previous combination, update Aopt,i, popt,i, and kopt,i; otherwise, keep the previous solution and mixed alternatives. This procedure terminates when all possible Ai, pi, and ki combinations are tested. Figure 6.2 shows the flow chart for determining alternatives and diverted fractions in SAMAMD. 176 i=0 l=0 p n1 = i /10 A n1=81 p n1= 0 pn1= 1 A n1=83An1=82 0 < p n1<1 p n2 = l /10 A n2=81 p n2= 0 pn2= 1 A n2=83An2=82 0 < p n2<1 TC cur =TC TC'