Optimal interdiction of a ground convoy

Dong Hwan Oh, R. Kevin Wood, Young Hoon Lee

Research output: Contribution to journalArticlepeer-review

3 Citations (Scopus)


This paper explores the convoy quickest-path interdiction problem (CQPI). In this problem, an interdictor or attacker uses limited offensive resources to attack components of a road network (i.e., road segments or intersections) to maximally delay a ground convoy transiting between specified origin and destination nodes in the network. The convoy’s commander, or defender, routes the convoy on a quickest path, which determines a convoy’s instantaneous speed by the convoy’s length, network characteristics (e.g., topology, speed limits), and by doctrine. After defining this new convoy quickest-path (CQP) problem, we develop an A* search algorithm for its solution. Finally, assuming a binary interdiction model in which an interdicted network component becomes impassable, we note the CQPI is NP-hard and show how to solve instances using a decomposition algorithm that solves CQP subproblems to evaluate tentative interdiction plans.

Original languageEnglish
Pages (from-to)5-17
Number of pages13
JournalMilitary Operations Research
Issue number2
Publication statusPublished - 2018

Bibliographical note

Publisher Copyright:
© 2018 Military Operations Research Society. All rights reserved.

All Science Journal Classification (ASJC) codes

  • Civil and Structural Engineering
  • Mechanical Engineering
  • Management Science and Operations Research


Dive into the research topics of 'Optimal interdiction of a ground convoy'. Together they form a unique fingerprint.

Cite this