A study of the lock-free tour problem and path-based reformulations

Mehmet Başdere, Karen Smilowitz and Sanjay Mehrotra

IISE Transactions, 2020, vol. 52, issue 6, 603-616

Abstract: Motivated by marathon course design, this article introduces a novel tour-finding problem, the Lock-Free Tour Problem (LFTP), which ensures that the resulting tour does not block access to certain critical vertices. The LFTP is formulated as a mixed-integer linear program. Structurally, the LFTP yields excessive subtour formation, causing the standard branch-and-cut approach to perform poorly, even with valid inequalities derived from locking properties of the LFTP. For this reason, we introduce path-based reformulations arising from a provably stronger disjunctive program, where disjunctions are obtained by fixing the visit orders in which must-visit edges are visited. In computational tests, the reformulations are shown to yield up to 100 times improvement in solution times. Additional tests demonstrate the value of reformulations for more general tour-finding problems with visit requirements and length restrictions. Finally, practical insights from the Bank of America Chicago Marathon are presented. Supplementary materials are available for this article. We refer the reader to the publisher’s online edition for additional experiments.

Date: 2020
References: Add references at CitEc
Citations:

Downloads: (external link)
http://hdl.handle.net/10.1080/24725854.2019.1662141 (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:uiiexx:v:52:y:2020:i:6:p:603-616

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

DOI: 10.1080/24725854.2019.1662141

Access Statistics for this article

IISE Transactions is currently edited by Jianjun Shi

More articles in IISE Transactions from Taylor & Francis Journals
Bibliographic data for series maintained by Chris Longhurst ().