Artificial Intelligence in Highway Location and Alignment Optimization

The following sections are included:

• About the Authors
• Contents

The following sections are included:

• Background
• Highway Alignment Optimization Problems
• Organization of the Monograph

This chapter investigates major cost items that should be considered in highway location selection and alignment development. Such an investigation is essential since these are criteria that are most commonly considered in evaluating highway alignment alternatives…

Artificial intelligence (AI) is a field of study that synthesizes and analyzes computational agents that act intelligently (Polle and Mackworth, 2017). AI, however, is normally characterized as computer applications in engineering fields that show features similar to intelligence of living creatures, such as evolution, collaborative behavior, processing of natural language, dealing with spatial structures, logical reasoning with fuzzy concepts, and learning (Transport Research Board (TRB), 2012). Therefore, heuristic and metaheuristic methods, designed for solving complex problems through a process of learning and discovery, are considered as a core field of AI in engineering. Several AI methods have been applied in highway location and alignment optimization problems. These include (i) Genetic Algorithms (GAs), (ii) Swam Intelligence (SW), and (iii) Simulated Annealing (SA). This chapter discusses computer applications or models that used those AI methods to solve highway location and alignment optimization problems.

PART II further discusses the genetic algorithms (GAs)-based highway alignment optimization (HAO) model developed by the University of Maryland research team with its core concept, structure, mathematical formulation, and effective constraint handling techniques to improve its computation efficiency. Chapter 4 demonstrates how horizontal and vertical alignments of a highway are represented with GAs. Methods to generate and evaluate highway alignments with custom GA operators are also discussed in this chapter. Chapter 5 discusses HAO model formulation; a basic model structure and various cost functions associated with the model objective function and constraints are demonstrated. Methods for handling infeasible solutions of evolutional algorithms like GAs are discussed in Chapter 6. Finally, effective constraint handling methods customized for the GAs-based HAO model are discussed in Chapters 7 and 8. All notations used in PART II can be found in Appendix A.

The following sections are included:

• Representation of Highway Alignments with GAs
• Modeling Horizontal Alignments
  • Horizontal Alignment Generation Procedure
• Modeling Vertical Alignments
• Modeling Highway Endpoints
  • Determination of Highway Endpoints
  • Highway Endpoint Determination Procedure
  • GA Operators for Endpoint Generation
• Modeling Highway Structures
  • Small Highway Bridges for Grade Separation
  • Structures for Highway Junction Points with Existing Roads

The following sections are included:

• Objective Function
• Constraints
• Integrating GAs and Geographic Information System
• Highway Cost Formulation
  • Highway Agency Cost
  • User Cost
  • Penalty and Environmental Costs
  • Life-cycle Cost

Evolutionary algorithms (EAs), which constitute a subfield of artificial intelligence (AI), have been developed for solving many complex constraint optimization problems. GAs are one of the most popularly used evolutionary algorithms that have many successful applications to complex optimization problems (e.g., project scheduling optimization (Wang and Schonfeld. 2007), space structures optimization (Adeli and Cheng, 1993), and steel structures optimization (Sarma and Adeli, 2000)). If GAs are applied to solve the complex problems, the method of handling infeasible solutions (generated from the algorithms) is very important to the effectiveness of the solution search process. This problem arises because solution search techniques used in GAs (such as reproduction, mutation, and recombination) are normally “blind” to the constraints, and thus it is possible for the GAs to generate a solution which does not satisfy the requirements of the problems (Michalewicz and Michalewicz, 1995)…

This chapter describes an effective constraint handling method (called feasible gate (FG)) developed for improving computation efficiency of the alignment optimization process. The method mainly aims to realistically represent complex geographical (spatial) constraints for the alignment optimization as well as to control solution alignments violating those constraints. A research motivation of the FG method is discussed in Section 7.1, and its methodologies applied for horizontal and vertical alignments are presented in Sections 7.2 and 7.3, respectively. Two example studies presented in Section 7.4 demonstrate the capability of the proposed method. Finally, Section 7.5 summarizes this chapter.

Another efficient solution search algorithm (prescreening and repairing (P&R)), which is also developed for enhancing the computation efficiency and solution quality of the highway alignment optimization (HAO)model, is introduced in this chapter. The key idea of this method is to repair (before the detailed evaluation) any candidate alignment whose violations of applicable constraints (here mainly design constraints) can be fixed with reasonable modifications, but discard that alignment (by using a penalty method) and avoid the detailed evaluation procedure if its violations of constraints are too severe to repair. This chapter starts with Section 8.1, a research motivation of the P&R method learned from the HAO model application to a real highway project. In Section 8.2 the methodology of the P&R method is described. Two examples of the HAO model application to an actual highway project (called Brookeville Bypass) are tested in Section 8.3 to demonstrate the capability of the method. Finally, Section 8.4 summarizes the results.

In Part III we further develop the GA-based HAO model, discussed in PART II, to extend its capabilities to optimize highway alignments within an existing road network. For that, the highway location selection and alignment optimization problem is reformulated as a bi-level programming problem to reflect changes in traffic flow patterns over the network due to its improvement with various highway alignment alternatives. The upper-level of the bi-level problem is formulated as the alignment optimization problem, and (2) the lower-level problem is defined as an equilibrium traffic assignment problem…

The highway location selection and alignment optimization problem defined in Chapter 1 is somewhat similar to the network design problem (NDP) which deals with the optimal decisions on the improvement of an existing highway network in response to a growing demand for travel (Gao et al., 2005). Roughly, the NDP can be classified into two different forms: discrete and continuous versions. The discrete version of the problem, known as DNDP, finds optimal (new) highways added to an existing road network among a set of predefined possible new highways while its continuous version, known as CNDP, determines the optimal capacity expansion of existing highways in the network. In whichever form, the objective of the NDP is usually to minimize total system travel cost while accounting for the route choice behaviors of network users. Note that models developed for the CNDP are not reviewed in this monograph since they are only distantly related to our problem (which considers the addition of a new highway to an existing network).

A new highway addition to an existing road network may be considered to improve the performance of that road network. Such a supply action increases capacity of the road network, and highway users may thus save travel time and vehicle operation costs. However, finding the new highway alternative that best improves the existing road network is a very complex problem since many factors affect it. Changes in network traffic flow patterns from the new highway addition, various costs associated with highway construction, as well as design specifications, safety, environmental impacts, and political issues affect the project. In addition, profiles and impacts of the new highway may depend significantly on how and where it is connected to the existing road network. Many previous studies (e.g., Steenbrink, 1974; Trietsch, 1987a, 1987b; Jong et al., 2000; Chen and Yang, 2004; Gao et al., 2005; Lee et al., 2009; Kang et al., 2012) have proposed various mathematical methods for solving highway network design and route optimization problems. Although some methods perform well in certain aspects, all are limited in the factors that they consider. We find no previous model that jointly evaluates traffic and environmental impacts of the new highway as well as optimizes highway location, construction cost, and horizontal and vertical profiles. This study integrates all these factors in optimizing highway alignments.

Chapter 11 presents an example study to demonstrate the performance of the bi-level HAO method. Figure 11.1 shows the land-use of the study area in which construction of a new highway is being considered for relieving the congestion in the existing highway system. A desktop PC (Pentium 4 CPU 3.2 GHz with 2GB RAM) is used for executing the bi-level alignment optimization model, and about six hours are taken to complete 300 generations of search. Land-use information and existing traffic condition of the study area are briefly described in the next.

The following sections are included:

• Project Description
• Data and Application Procedure
  • Horizontal Map Digitization
  • Vertical Map Digitization
  • Tradeoffs in Map Representation for Environmental Issues
  • Description of Model Inputs and Outputs
• Optimization Results
  • Optimized Alignments with Different Numbers of PI’s
  • Goodness Test
• Sensitivity of Optimized Alignments to Other Major Input Parameters
  • Sensitivity to the Model’s Objective Function
  • Sensitivity to Design Speed
  • Sensitivity to Elevation Resolution
  • Sensitivity to Cross-section Spacing

The following sections are included:

• Project Description
• Projection Preparation
  • Spatial Data
  • Project Segmentation
  • Geometric Design Specification
• Optimization Results

The following sections are included:

• Project Description
  • Overview of the ICC Study
  • Description of HAO Model Application to ICC Project
• Input Data Preparation
  • Road Network
  • Traffic Information
  • GIS Map Preparation
  • Important Input Parameters
• Optimization Results
  • Determination of Traffic Reassignments
  • Optimized Alignments
  • Goodness Test

This chapter indicates that many additional developments, enhancements, and new applications remain to be pursued by interested researchers. Thus, various exciting developments in highway location and alignment optimization and related research fields may be expected in the coming years.

The following sections are included:

• Appendix A: Notation Used in the Monograph
• Appendix B: Traffic Inputs to the HAO Model for the ICC Case Study

The following sections are included:

• References
• Index