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

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.