Research Outputs

Permanent URI for this communityhttps://hdl.handle.net/20.500.14288/2

Browse

Filters

20161

Advanced Search

Filter by

Settings

Department: search.filters.department.Department of MathematicsSubject: search.filters.subject.Industrial engineering

Search Results

Now showing 1 - 1 of 1
  • Placeholder
    PublicationMetadata only
    Performance evaluation of an exact method for the obstacle neutralization problem
    (IEOM Society, 2016) Alkaya, Ali Fuat; Algin, Ramazan; Oz, Dindar; Aksakalli, Vural; Department of Mathematics; Ceyhan, Elvan; Faculty Member; Department of Mathematics; College of Sciences; N/A
    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.