An Electromagnetism-like Algorithm to Solve Three-dimensional Highway Alignment Problem

Document Type : Article


1 Dept. of Civil Eng., Sharif University of Technology,Tehran, Iran

2 Institute for Transportation Studies and Research, Dept. of Civil Eng., Sharif University of Technology, Tehran, Iran


Road alignment design is an important determinant of the development cost of road networks. On the one side, it affects road construction and maintenance costs, which constitute a significant part of country-wide infrastructure development, management and operation budget each year. On the other side, it affects road user-related costs of travel time and vehicle use, which comprise a significant portion of the total transportation cost. This study adapts the existing Electromagnetism-like meta-heuristic algorithm to solve a three-dimensional highway alignment problem, which explores and finds a good route between two given points on a terrain. It detects the potentials of the given initial routes, which are enhanced and shaped toward better positions by the help of the local and global search. The final good solution is, then, fine-tuned for a better alignment. Several example problems are designed to show the behavior of the algorithm. The results show that the algorithm satisfactorily maneuvers to by-pass obstacles, and build highway structures where necessary. The set of the example problems in this paper may also serve to found a basis for evaluation of the performance of alternative algorithms


Main Subjects

1. Kim, E., Jha, M.K., and Son, B. Improving the
computational eciency of highway alignment optimization
models through a stepwise genetic algorithms
approach", Transportation Research Part B: Methodological,
39(4), pp. 339-360 (2005).
2. Kang, M.-W., Jha, M.K., and Schonfeld, P. Applicability
of highway alignment optimization models",
Transportation Research Part C: Emerging Technologies,
21(1), pp. 257-286 (2012).
3. Jong, J.-C. and Schonfeld, P. An evolutionary model
for simultaneously optimizing three-dimensional highway
alignments", Transportation Research Part B:
Methodological, 37(2), pp. 107-128 (2003).
4. Jha, M.K. and Schonfeld, P. A highway alignment
optimization model using geographic information systems",
Transportation Research Part A: Policy and
Practice, 38(6), pp. 455-481 (2004).
5. Howard, B., Bramnick, Z., and Shaw, J., Optimum
Curvature Principle in Highway Routing, Road Research
Laboratory/UK (1969).
6. Shaw, J.F. and Howard, B.E. Comparison of two
integration methods in transportation routing", Transportation
Research Record, 806, pp. 8-13 (1981).
7. Shaw, J.F. and Howard, B.E. Expressway route
optimization by OCP", Transportation Engineering
Journal, 108(3), pp. 227-243 (1982).
8. Thomson, N. and Sykes, J. Route selection through
a dynamic ice eld using the maximum principle",
Transportation Research Part B: Methodological,
22(5), pp. 339-356 (1988).
9. Wan, F., Introduction to the Calculus of Variations and
its Applications, Boca Raton, Florida, United States
CRC Press (1995).
10. Turner, A.K. and Miles, R.D., The GCARS System: A
Computer-Assisted Method of Regional Route Location,
West Lafayette, Indiana, United States Lafayette, in
Purdue University (1971).
11. Athanassoulis, G. and Calogero, V. Optimal location
of a new highway from A to B-A computer technique
for route planning", PTRC Seminar Proceedings on
Cost Models & Optimization in Highway (1973).
12. Parker, N.A. Rural highway route corridor selection",
Transportation Planning and Technology, 3(4), pp.
247-256 (1977).
3018 A. Mohammadi and H. Poorzahedy/Scientia Iranica, Transactions A: Civil Engineering 25 (2018) 2997{3020
13. Trietsch, D. A family of methods for preliminary
highway alignment", Transportation Science, 21(1),
pp. 17-25 (1987).
14. Trietsch, D. Comprehensive design of highway networks",
Transportation Science, 21(1), pp. 26-35
15. Hogan, J. Experience with OPTLOC optimum location
of highways by computer", PTRC Seminar Proceedings
on Cost Models and Optimization in Highways
(Session L10), London (1973).
16. Nicholson, A.J., Elms, D.G., and Williman, A. A variational
approach to optimal route location", Highway
Engineers, 23, pp. 22-25 (1976).
17. Lee, Y., Tsou, Y.-R., and Liu, H.-L. Optimization
method for highway horizontal alignment design",
Journal of Transportation Engineering, 135(4), pp.
217-224 (2009).
18. Liatsis, P. and Taw k, H. Two-dimensional road
shape optimisation using genetic algorithms", Mathematics
and Computers in Simulation, 51(1), pp. 19-31
19. Jong, J.-C., Optimizing Highway Alignments with Genetic
Algorithms, Research Directed by Dept. of Civil
Engineering, University of Maryland, College Park,
Md. (1998).
20. Jong, J.C., Jha, M.K., and Schonfeld, P. Preliminary
highway design with genetic algorithms and geographic
information systems", Computer Aided Civil and Infrastructure
Engineering, 15(4), pp. 261-271 (2000).
21. Easa, S.M. Selection of roadway grades that minimize
earthwork cost using linear programming", Transportation
Research Part A: General, 22(2), pp. 121-136
22. Huarte, P. OPYGAR: Optimization and automatic
design of highway pro les", Planning and Transport
Research and Computation Seminar Proceedings on
Cost Models and Optimization in Highways (Session
L13), London (1973).
23. Murchland, J. Methods of vertical pro le optimization
for an improvement to an existing road", PTRC
Seminar Proceedings on Cost Models and Optimisation
in Highways (Session L12), London (1973).
24. Goh, C., Chew, E., and Fwa, T. Discrete and
continuous models for computation of optimal vertical
highway alignment", Transportation Research Part B:
Methodological, 22(6), pp. 399-409 (1988).
25. Fwa, T. Highway vertical alignment analysis by
dynamic programming", Transportation Research
Record, 1239 (1989).
26. Revelle, C.A. and Whitlach, E.E., Civil and Environmental
Systems Engineering, Upper Saddle River, New
Jersey, United States Prentice Hall PTR (1996).
27. Chapra, S.C. and Canale, R.P., Numerical Methods for
Engineers, Boston, United States McGraw-Hill (2006).
28. Hare, W., Lucet, Y., and Rahman, F. A mixedinteger
linear programming model to optimize the
vertical alignment considering blocks and side-slopes in
road construction", European Journal of Operational
Research, 241(3), pp. 631-641 (2014).
29. Hare, W., Hossain, S., Lucet, Y., and Rahman, F.
Models and strategies for eciently determining an
optimal vertical alignment of roads", Computers &
Operations Research, 44, pp. 161-173 (2014).
30. Hayman, R.W. Optimization of vertical alignment
for highways through mathematical programming",
Highway Research Record, 306 (1970).
31. Robinson, R. Automatic design of the road vertical
alignment", PTRC Seminar Proceedings on Cost
Models and Optimization in Highways (Session L19),
London (1973).
32. Fwa, T., Chan, W., and Sim, Y. Optimal vertical
alignment analysis for highway design", Journal
of Transportation Engineering, 128(5), pp. 395-402
33. Chew, E., Goh, C., and Fwa, T. Simultaneous
optimization of horizontal and vertical alignments for
highways", Transportation Research Part B: Methodological,
23(5), pp. 315-329 (1989).
34. Mandow, L. and Perez-de-la-Cruz, J.-L. Sindi: an intelligent
assistant for highway design", Expert Systems
with Applications, 27(4), pp. 635-644 (2004).
35. De Smith, M.J. Determination of gradient and curvature
constrained optimal paths", Computer Aided
Civil and Infrastructure Engineering, 21(1), pp. 24-38
36. Jha, M.K., A Geographic Information Systems-Based
Model for Highway Design Optimization, Maryland,
United States University of Maryland at College Park
37. Kim, E., Modeling Intersections and Other Structures
in Highway Alignment Optimization, University of
Maryland, College Park (2001).
38. Tat, C.W. and Tao, F. Using GIS and genetic algorithm
in highway alignment optimization", Intelligent
Transportation Systems. IEEE (2003).
39. Kim, E., Jha, M.K., Lovell, D.J., and Schonfeld, P.
Intersection modeling for highway alignment optimization",
Computer Aided Civil and Infrastructure
Engineering, 19(2), pp. 119-129 (2004).
40. Kim, E., Jha, M.K., and Schonfeld, P. Intersection
construction cost functions for alignment optimization",
Journal of Transportation Engineering, 130(2),
pp. 194-203 (2004).
41. Kim, E., Jha, M.K., Schonfeld, P., and Kim,
H.S. Highway alignment optimization incorporating
bridges and tunnels", Journal of Transportation Engineering,
133(2), pp. 71-81 (2007).
42. Jia, P., Sun, Z., Kato, H., and Hayashi, Y. Incorporating
network impact analysis into road alignment
optimization", Journal of the Eastern Asia Society for
Transportation Studies, 7, pp. 2074-2089 (2007).
A. Mohammadi and H. Poorzahedy/Scientia Iranica, Transactions A: Civil Engineering 25 (2018) 2997{3020 3019
43. Kang, M.W., Schonfeld, P., and Jong, J.C. Highway
alignment optimization through feasible gates", Journal
of Advanced Transportation, 41(2), pp. 115-144
44. Kang, M.W., An Alignment Optimization Model for
a Simple Highway Network, University of Maryland
45. Kang, M.W., Schonfeld, P., and Yang, N. Prescreening
and repairing in a genetic algorithm for highway
alignment optimization", Computer Aided Civil and
Infrastructure Engineering, 24(2), pp. 109-119 (2009).
46. Kang, M.W., Yang, N., Schonfeld, P., and Jha, M.
Bilevel highway route optimization", Transportation
Research Record: Journal of the Transportation Research
Board, 2197(1), pp. 107-117 (2010).
47. Maji, A. and Jha, M.K. A multiobjective analysis of
impacted area of environmentally preserved land and
alignment cost for sustainable highway infrastructure
design", Procedia-Social and Behavioral Sciences, 20,
pp. 966-972 (2011).
48. Jian-xin, C. and Qing, L. Research on cost-oriented
modeling and optimization for highway alignment",
Procedia Engineering, 15, pp. 3931-3935 (2011).
49. Yang, N., Kang, M.W., Schonfeld, P., and Jha, M.K.
Multi-objective highway alignment optimization incorporating
preference information", Transportation
Research Part C: Emerging Technologies, 40, pp. 36-48
50. Mohasel Afshar, A. Design of optimum highway alignment
using gradien based methods", MS Thesis, Dept.
of Civil Engineering, Sharif University of Technology
(In Farsi) (2004).
51. Shengwen, T., Xiucheng, G., and Shengwu, T. Optimizing
highway alignments based on improved particle
swarm optimization and ArcGIS", Transportation and
Development Innovative Best Practices, ASCE (2008).
52. Shafahi, Y. and Bagherian, M. A customized particle
swarm method to solve highway alignment optimization
problem", Computer-Aided Civil and Infrastructure
Engineering, 28(1), pp. 52-67 (2013).
53. Pourzahedi, L. A hybrid meta-heuristic algorithm
for the solution of highway alignment problem", BS
Project Report, Dept. of Civil Engineering, Sharif
University of Technology (In Farsi) (2010).
54. Faghih, S. A hybrid meta-heuristic algorithm to
solve three dimensional highway alignment optimization
problem", MS Thesis, Dept. of Civil Engineering,
Sharif University of Technology (In Farsi) (2012).
55. Jha, M.K., ha, M.K., Schonfeld, P.M., and Jong, J.C.,
Intelligent Road Design, 19, Southampton, Boston,
United States, WIT Press (2006).
56. Kang, M.-W., Shariat, S., and Jha, M.K. New
highway geometric design methods for minimizing
vehicular fuel consumption and improving safety",
Transportation Research Part C: Emerging Technologies,
31, pp. 99-111 (2013).
57. Cheng, J.-C. and Jiang, L.-J. Accuracy comparison of
roadway earthwork computation between 3D and 2D
methods", Procedia-Social and Behavioral Sciences,
96, pp. 1277-1285 (2013).
58. Birbil, S._I. and Fang, S.-C. An electromagnetism-like
mechanism for global optimization", Journal of Global
Optimization, 25(3), pp. 263-282 (2003).
59. Kennedy, J. and Eberhart, R. Particle swarm optimisation",
Proceedings IEEE International Conference
on Neural Networks (1995).
60. Wang, K.J., Adrian, A.M., Chen, K.H., and Wang,
K.M. An improved electromagnetism-like mechanism
algorithm and its application to the prediction of
diabetes mellitus", Journal of Biomedical Informatics,
54, pp. 220-229 (2015).
61.  Ozdag, R. and Karc, A. Probabilistic dynamic distribution
of wireless sensor networks with improved
distribution method based on electromagnetism-like
algorithm", Measurement, 79, pp. 66-76 (2016).
62. Jolai, F., Tavakkoli-Moghaddam, R., Golmohammadi,
A., and Javadi, B. An electromagnetism-like algorithm
for cell formation and layout problem", Expert
Systems with Applications, 39(2), pp. 2172-2182
63. Kuo, C.L., Chu, C.H., Li, Y., Li, X., and Gao, L.
Electromagnetism-like algorithms for optimized tool
path planning in 5-axis
ank machining", Computers
& Industrial Engineering, 84, pp. 70-78 (2015).
64. Naderi, B., Tavakkoli-Moghaddam, R. and Khalili,
M. Electromagnetism-like mechanism and simulated
annealing algorithms for
owshop scheduling problems
minimizing the total weighted tardiness and
makespan", Knowledge-Based Systems, 23(2), pp. 77-
85 (2010).
65. Feng, Y., Yao-Nan, W., and Shu-Ning, W. Inverse
kinematic solution for robot manipulator based on
electromagnetism-like and modi ed DFP algorithms",
Acta Automatica Sinica, 37(1), pp. 74-82 (2011).
66. Yurtkuran, A. and Emel, E. Ecient constraint handling
in electromagnetism-like algorithm for traveling
salesman problem with time windows", The Scienti c
World Journal, 2014, pp. 1-12 (2014).
67. Beheshti, A.K., Hejazi, S., and Mirmohammadi, S. A
hybrid metaheuristic algorithm for the vehicle routing
problem with delivery time cost", International Journal
of Applied, 4(3), pp. 49-64 (2014).
68. Yurtkuran, A. and Emel, E. A new hybrid
electromagnetism-like algorithm for capacitated vehicle
routing problems", Expert Systems with Applications,
37(4), pp. 3427-3433 (2010).
69. Kratica, J. An electromagnetism-like metaheuristic
for the uncapacitated multiple allocation p-hub median
problem", Computers & Industrial Engineering, 66(4),
pp. 1015-1024 (2013).
70. Fathian, M., Jouzdani, J., Heydari, M., and Makui,
A. Location and transportation planning in supply
3020 A. Mohammadi and H. Poorzahedy/Scientia Iranica, Transactions A: Civil Engineering 25 (2018) 2997{3020
chains under uncertainty and congestion by using an
improved electromagnetism-like algorithm", Journal
of Intelligent Manufacturing, 29(7), pp. 1447-1464
71. Lee, C.-H. and Lee, Y.-C. Nonlinear systems design
by a novel fuzzy neural system via hybridization
of electromagnetism-like mechanism and particle
swarm optimisation algorithms", Information Sciences,
186(1), pp. 59-72 (2012).