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

Mehmet Başdere, Karen Smilowitz*, Sanjay Mehrotra

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish (US)
Pages (from-to)603-616
Number of pages14
JournalIISE Transactions
Issue number6
StatePublished - Jun 2 2020


  • Transportation
  • combinatorial optimization
  • integer programming

ASJC Scopus subject areas

  • Industrial and Manufacturing Engineering


Dive into the research topics of 'A study of the lock-free tour problem and path-based reformulations'. Together they form a unique fingerprint.

Cite this