Metaheuristic based solution approaches for the obstacle neutralization problem

ALKAYA A. F., Algin R.

EXPERT SYSTEMS WITH APPLICATIONS, cilt.42, sa.3, ss.1094-1105, 2015 (SCI-Expanded) identifier

  • Yayın Türü: Makale / Tam Makale
  • Cilt numarası: 42 Sayı: 3
  • Basım Tarihi: 2015
  • Doi Numarası: 10.1016/j.eswa.2014.09.027
  • Dergi Adı: EXPERT SYSTEMS WITH APPLICATIONS
  • Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Sayfa Sayıları: ss.1094-1105
  • Anahtar Kelimeler: Path planning, Obstacle neutralization problem, Optimization, Metaheuristics, OPTIMIZATION, ALGORITHM, PERFORMANCE, AIRCRAFT
  • Marmara Üniversitesi Adresli: Evet

Özet

The problem of finding shortest path under certain constraints is NP-Complete except for some trivial variants. In this study, we develop metaheuristics for the obstacle neutralization problem (ONP) which is a path planning problem where the goal is to safely and swiftly navigate an agent from a given source location to a destination through an arrangement of potential mine or threat discs in the plane. To solve the ONP, ant system, genetic algorithm, simulated annealing and migrating birds optimization algorithms are developed and customized. We provide computational experiments both on real-world and synthetic data to empirically assess their performance. The results of the algorithms are compared with exact solutions on small instances. The comparison results present that our algorithms finds near-optimal solutions in reasonable execution times. Furthermore, the results show that the proposed versions of the aforementioned algorithms can be applicable to similar problems. (C) 2014 Elsevier Ltd. All rights reserved.