Computational & Technology Resources
an online resource for computational,
engineering & technology publications
Civil-Comp Proceedings
ISSN 1759-3433
CCP: 76
Edited by: B.H.V. Topping and Z. Bittnar
Paper 73

Genetic Algorithms Based Optimization of Three-Dimensional Alignments for Highways

M. Yamasaki+, T. Hongo+, K. Hiyane*, J. Iio* and T. Yatabe*

+Japan Highway Public Corporation, Tokyo, Japan
*Mitsubishi Research Institute Inc., Tokyo, Japan

Full Bibliographic Reference for this paper
M. Yamasaki, T. Hongo, K. Hiyane, J. Iio, T. Yatabe, "Genetic Algorithms Based Optimization of Three-Dimensional Alignments for Highways", in B.H.V. Topping, Z. Bittnar, (Editors), "Proceedings of the Third International Conference on Engineering Computational Technology", Civil-Comp Press, Stirlingshire, UK, Paper 73, 2002. doi:10.4203/ccp.76.73
Keywords: genetic algorithms, road design, horizontal and vertical alignments, optimization, highway, earthwork cost.

A new highway design approach is proposed that optimaze horizontal and vertical alignments simultaneously based on Genetic Algorithms (GAs). A new alignment model suitable for optimization problem is devised that enables to solve a large-scale problem. Qualitative evaluation of construction cost is calculated from detailed digital terrain data. The alignments should satisfy tens of constraints and preferable conditions defined as Japanese highway standards for running safty. We developped the GAs based optimization system called `OHPASS' - Optimal Highway Path Automatic Search System.

Road designer used to design manually with or without road CADs. There is no guarantee to obtain optimal alignments from the point of view of construction cost and safety of alignments because only several alignments can be compared. Recent study on highway design optimization models (HDOM) proved effectiveness of using computer and GIS [2,3]. They indicated eleven conditions for a good HDOM. We have also tried to apply to highway alignment optimization problem [1]. Our system also satisfys above eleven conditions. Futhermore, we made several realistic enhancements.

The horizontal alignments consist of straight line, circular arc and clothoid, and the vertical alignments consist of straight line and parabola in the Japanese highway standard. We developped a new alignment model that consists of only position, direction, and grade of passing points. Other parameters such as curvatures and clothoid parameters are automatically determined by mathmatical constraint and designer's given preference. Using this model, road alignments of 10-20 km length can be represented by less than a hundred parameters.

The evaluation function of alignments includes construction cost of tunnel, bridge and earthwork, and running safety from smoothness of alignments. The most costly caclucation is earthwork cost. Japan Highway Public Corporation prepares minute digital terrain maps at the planning phase. For each alignment, cutting and filling volumn of earth is calculated from cross sections generated at intervals of 20m. We developped a fast calculation technique so that 700 cross-sections of 14km length can be obtained in only 15 milliseconds.

For running safety, we consider detaild constraints defined by Japanese highway standards, and preferable conditions given by expert road designers. Various kinds of inaccessible areas are also considered.

We formulate highway alignment optimization problem as a Genetic Algorithms optimization. We adopt the stady-state genetic algorithms with real number genomes. Crossover operator is implemented as partial exchange of two alignments, and mutation operator as local modification of an alignment.

Comparison verification was carried out with the actual past design. We select the Trans-Chubu Highway as a case study because Japan Highway recently decided to make detailed digital terrain map suitable for our purpose. The target area has 14.7km length and 600m width along with planned center line. The area is mountainous that earthwork cost is very sensitive.

Consequently, construction cost was able to be cut down significantly by 28%. We could obtain horizontal and vertical alignments fully satisfying constraints and preferable conditions, whereas the past actual design couldn't escape from violation of some preferable conditions.

It took only 63 hours for the 100 times calculation time of 200 generations that included evaluation of ten million alignments. Compared with conventional CAD design, it took at least hours for design and evaluation per alignment. Our proposed method will reduce design time dramatically.

M.Yamasaki, "Optimal Vertical Alignment Design By Digital Terrain and Genetic Algorithms", Journal of Infrastructure Planning and Management, Japan Society of Civil Engineers, Vol.18, No.1, pp.139-148, 2001 (in Japanese).
M.K. Jha, C. McCall, and P. Schonfeld: "Using GIS, Genetic Algorithms, and Visualization in Highway Development", Computer-Aided Civil and Infrastructure Engineering, Vol.16, No.6, pp.399-414, 2001. doi:10.1111/0885-9507.00242
P.G. Gipps and K.Q. Gu: "Some Experimental with Geospatial Imagery and Route Optimization", Transportation Research Record 1690, No.99-0202, pp.143-152, 1999. doi:10.3141/1690-17

purchase the full-text of this paper (price £20)

go to the previous paper
go to the next paper
return to the table of contents
return to the book description