Publication:
Performance evaluation of an exact method for the obstacle neutralization problem

Placeholder

Departments

School / College / Institute

Program

KU-Authors

KU Authors

Co-Authors

Alkaya, Ali Fuat
Algin, Ramazan
Oz, Dindar
Aksakalli, Vural

Publication Date

Language

Embargo Status

Journal Title

Journal ISSN

Volume Title

Alternative Title

Abstract

The Obstacle Neutralization Problem (ONP) is an NP-Hard path planning problem wherein an agent needs to swiftly navigate from a given start location to a target location through an arrangement of disc-shaped obstacles on the plane. The agent has a limited neutralization capability in the sense that it can neutralize an obstacle after which it can safely traverse through. A neutralization can only be performed at a cost, which is added to the overall traversal length. The goal is to find the optimal neutralization sequence that minimizes the agent's total traversal length. In this study, we compare the performance of a recently proposed exact algorithm for ONP against a conventional solution obtained via an integer programming formulation. This exact algorithm consists of two phases. In Phase I, an effective and fast algorithm is used to obtain a suboptimal solution. In the Phase II, a k-th shortest path algorithm is used to close any gaps. The integer programming formulation is solved via the popular SCIP solver. We present computational experiments conducted on synthetic problem instances on a discrete plane with varying resolutions. Our results indicate that the exact algorithm provides an almost 10-fold improvement in execution time when compared against the integer programming approach.

Source

Publisher

IEOM Society

Subject

Engineering, Industrial engineering, Management

Citation

Has Part

Source

Proceedings of the International Conference on Industrial Engineering and Operations Management

Book Series Title

Edition

DOI

item.page.datauri

Rights

Copyrights Note

Endorsement

Review

Supplemented By

Referenced By

0

Views

0

Downloads