Applicability of Genetic and Ant Algorithms in Highway Alignment and Rail Transit Station Location Optimization

Applicability of Genetic and Ant Algorithms in Highway Alignment and Rail Transit Station Location Optimization

Sutapa Samanta (Maryland State Highway Administration, USA) and Manoj K. Jha (Morgan State University, USA)
DOI: 10.4018/joris.2012010102
OnDemand PDF Download:
$30.00
List Price: $37.50

Abstract

The emergence of artificial intelligence (AI)-based optimization heuristics like genetic and ant algorithms is useful in solving many complex transportation location optimization problems. The suitability of such algorithms depends on the nature of the problem to be solved. This study examines the suitability of genetic and ant algorithms in two distinct and complex transportation problems: (1) highway alignment optimization and (2) rail transit station location optimization. A comparative study of the two algorithms is presented in terms of the quality of results. In addition, Ant algorithms (AAs) have been modified to search in a global space for both problems, a significant departure from traditional AA application in local search problems. It is observed that for the two optimization problems both algorithms give almost similar solutions. However, the ant algorithm has the inherent limitation of being effective only in discrete search problems. When applied to continuous search spaces ant algorithm requires the space to be sufficiently discretized. On the other hand, genetic algorithms can be applied to both discrete and continues spaces with reasonable confidence. The application of AA in global search seems promising and opens up the possibility of its application in other complex optimization problems.
Article Preview

Introduction

In recent years, artificial intelligence (AI)-based optimization heuristics have been extensively applied to solve many transportation location optimization problems. These heuristics (such as, Genetic Algorithm (GA), Ant Algorithm (AA), Tabu Search, Simulated Annealing, and Artificial Neural Network) have established their applicability by having been applied in many complex real-life problems. Their application turns out to be more appropriate than the classical optimization tools at times. Not only that the quality of solutions for any problem determines the efficiency and the applicability of an algorithm, the computation time plays an important role too. When the study area for an optimal search for a real-life problem becomes large and complex with a number of parameters involved, the AI heuristics become particularly useful. The advantage of these modern tools over the classical tools is their flexibility towards the complexity of the problems. The mechanism of the algorithms can be so designed (or customized according to the nature of the problem) such that they lead to the optimal solution faster than the traditional way.

Typically, a black-box approach has been applied in employing many AI-based heuristics to solve transportation location optimization problems. A clear guidance is not available to the user community regarding the relative effectiveness of such heuristics in different problem domains. In this paper, the effectiveness of genetic and ant algorithms are critically evaluated in two relatively complex transportation location optimization problems, which are: (1) the highway alignment optimization (HAO) problem; and (2) the rail transit station location optimization (SLO) problem. In HAO an optimal highway alignment has to be obtained between two given points by minimizing the total cost of the alignment (Jong & Schonfeld, 2003, 2004). The SLO problem is to find the number and spacing of intermediate stations along a given rail transit line, provided the start and end point and the alignment of the transit line are given (Jha & Oluokun, 2004).

GA is an evolutionary optimization algorithm, which is based on natural selection and natural genetics. It generates improved solutions based on the historical data over the search generations (Goldberg, 1989). Since GA conducts a more exhaustive search, the computation time becomes an issue at times. The computation becomes very extensive for GA when a large database (generally obtained from a Geographic Information System) is attached to the problem requiring numerous spatial computations (Jha & Schonfeld, 2004). AA is an optimization algorithm based on swarm intelligence, which is the collective behavior of a group of ants (Jha, 2001, 2002a) looking for the shortest route to reach to the destination. AA works on the principle of self organization, stigmergy and autocatalysis (Bonabeau et al., 1999) and generally depends on the local information. Therefore, basically it is considered a local search algorithm. AA seems to require lesser computation than GA considering the mechanisms of both the algorithms based on which they reach to the optimal or near-optimal solutions.

Upon reviewing the literature (Jong & Schonfeld, 2003, 2004; Kim et al., 2005; Jha et al., 2006), we find that GA has been extensively applied to solve the highway alignment optimization (HAO) problem. However, its integration with a GIS significantly reduces its computational efficiency (Jha & Schonfeld, 2001). The recent success of AA in many optimization problems (for example, Huang & Bo, 2005) has encouraged us to apply it to the HAO problem, in the quest of a more efficient heuristics employable to real-world problems.

Complete Article List

Search this Journal:
Reset
Open Access Articles: Forthcoming
Volume 9: 4 Issues (2018): 1 Released, 3 Forthcoming
Volume 8: 4 Issues (2017)
Volume 7: 4 Issues (2016)
Volume 6: 4 Issues (2015)
Volume 5: 4 Issues (2014)
Volume 4: 4 Issues (2013)
Volume 3: 4 Issues (2012)
Volume 2: 4 Issues (2011)
Volume 1: 4 Issues (2010)
View Complete Journal Contents Listing