Solving the shortest path interdiction problem via reinforcement learning

Dian Huang, Zhaofang Mao, Kan Fang and Lin Chen

International Journal of Production Research, 2023, vol. 61, issue 1, 31-48

Abstract: This paper addresses the shortest path interdiction problem, in which the leader aims to maximise the length of the shortest path that the follower can traverse subject to a limited interdiction budget. To solve this problem, we propose a reinforcement learning framework and use the pointer network to handle the situation of variable output sizes. To evaluate the performance of our proposed reinforcement learning model, we conduct extensive computational experiments on a set of instances that are generated from two different network topologies, i.e. the grid networks and the random graphs. To train the pointer network, we consider three different baselines, i.e. the exponential, critical, and rollout baselines, among which the rollout baseline policy achieves the best computational results, and thus is used as the default baseline during our computational experiments. Moreover, when the size of instances increases, we find that solving the equivalent single-level mixed integer program of the problem could be quite time-consuming, while our proposed reinforcement learning approach can still obtain solutions with good performance effectively for both the grid networks and the random graphs.

Date: 2023
References: Add references at CitEc
Citations:

Downloads: (external link)
http://hdl.handle.net/10.1080/00207543.2021.2002962 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:taf:tprsxx:v:61:y:2023:i:1:p:31-48

Ordering information: This journal article can be ordered from
http://www.tandfonline.com/pricing/journal/TPRS20

DOI: 10.1080/00207543.2021.2002962

Access Statistics for this article

International Journal of Production Research is currently edited by Professor A. Dolgui

More articles in International Journal of Production Research from Taylor & Francis Journals
Bibliographic data for series maintained by Chris Longhurst ().