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 journalArticle

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.

Original languageEnglish (US)
JournalIISE Transactions
DOIs
StateAccepted/In press - Jan 1 2019

    Fingerprint

Keywords

  • combinatorial optimization
  • integer programming
  • Transportation

ASJC Scopus subject areas

  • Industrial and Manufacturing Engineering

Cite this