Metaheuristic methods for the obstacle neutralization problem

---

Tezin Türü: Yüksek Lisans

Tezin Yürütüldüğü Kurum: Marmara Üniversitesi, Mühendislik Fakültesi, Bilgisayar Mühendisliği Bölümü, Türkiye

Tezin Onay Tarihi: 2016

Tezin Dili: İngilizce

Öğrenci: RAMAZAN ALGIN

Danışman: Ali Fuat Alkaya

Açık Arşiv Koleksiyonu: AVESİS Açık Erişim Koleksiyonu

Özet:

Within the scope of this thesis both theoretical and computational research have been conducted for developing new solution methods for Obstacle Neutralization Problem (ONP) which is actually a military navy scenario and it is inspired from a real problem. In this thesis, we develop metaheuristics for the ONP which is a path planning problem where the aim is to safely and swiftly traverse an agent from a given start point to a target point through a plan of potential mine or threat discs in the plane. A neutralization capability is given to the agent. He can neutralize the threats without exceeding the given neutralization limit. To solve the ONP, ant system, ant colony system, migrating birds optimization, genetic algorithm and simulated annealing algorithms are developed and customized. In addition to these metaheuristics SCIP solver is used to find exact solution. ONP is modeled with ZIMPL language to become ready for SCIP solver. We provide computational experiments both on real-world and synthetic data to empirically assess their performance. The results of the metaheuristics are compared with exact solutions on small and moderate instances. The comparison results present that our algorithms find near-optimal solutions in reasonable execution times. For larger instances SCIP is not applicable because of high run time complexity, therefore, metaheuristics developed for ONP are suitable for larger instances. When the agent neutralizes a threat, neutralization cost of this threat is added to the total cost.