Description:

Northwestern University Transportation Center presents:

"Models and Approaches to Multi-Objective Arc Tour Problems with an Application to Marathon Course Design"

Mehmet Basdere
PhD Candidate, Industrial Engineering & Management Sciences
Northwestern University

ABSTRACT:
Motivated by marathon course design, our study introduces a novel tour finding problem, the Lock-Free Arc Tour Problem (LFATP), which ensures that the resulting tour does not block access to certain critical vertices. The LFATP is formulated as a mixed integer linear program. Structurally, the LFATP yields excessive subtour formation, causing the standard branch-and-cut approach to perform poorly even with valid inequalities derived from locking properties of the LFATP. 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 benefits of using lock elimination inequalities and the value of reformulations for more general tour finding problems with visit requirements and length restrictions. To solve LFATP in a multi-objective environment, we develop a new Interactive Weight Region-Based Approach (IWRA) that iteratively reaches a most preferred solution of the corresponding linear or integer program after exploring a few nondominated solutions. Practical insights from the Bank of America Chicago Marathon are presented along with extensions of reformulations for various types of objective functions.

 
SPEAKER BIO:
Mehmet Basdere is a Ph.D. student in the Department of Industrial Engineering and Management Sciences at Northwestern University. He received his bachelor’s and master’s degree in industrial engineering from Bogazici University, Turkey. His research interests include continuous and discrete optimization, multi-objective decision making and disjunctive programming with applications to logistics, routing, scheduling and wireless sensor network problems. During his PhD studies, Mehmet received Arthur P. Hurter Award, awarded to the most successful first-year graduate students at Northwestern University IEMS Department, Nemhauser Best Student Paper Award, awarded to the most successful graduate student paper at Northwestern University IEMS Department, and Dissertation Year Fellowship, awarded by Northwestern University Transportation Center to fund the most successful dissertation projects.