Marathons are long distance running events with many participants, often organized in heavily populated cities. A key component in marathon planning operations is the design of the marathon course to be followed during the race. In addition to the technical requirements regarding length and incline change, marathon courses must satisfy two additional requirements: (i) courses must visit certain neighborhoods in the city and (ii) they must be designed in such a way that access to the facilities that provide critical public service (e.g. hospitals) is not blocked by the tour. Motivated by marathon course design, this study develops models and approaches to solve multiobjective arc tour problems. The underlying tour finding problem, the Lock-Free Arc Tour Problem (LFATP), visits a predetermined set of edges while ensuring that the resulting tour does not block access to certain critical vertices. Apart from these restrictions, marathon course design involves a range of unique objective functions which we are classified under three categories: (i) arc-additive, (ii) sequence-dependent and (iii) time-dependent objective functions. In arc-additive functions, the objective contribution of each arc has a constant coefficient. In sequence-dependent ones, each arc's contribution to the objective depends on the other arcs used in the route and in time-dependent ones, each arc's contribution depends on when that arc is visited. Initial efforts focus on the LFATP with arc-additive objectives as these objectives are relatively less complex compared to sequence- and time-dependent ones. The underlying problem is formulated as a mixed integer linear program. Structurally, the LFATP suffers from excessive subtour formation, especially when the corresponding objective aims to minimize proximity to certain locations in the network, 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. Then, we extend the arc-additive model and its reformulations to handle objectives involving sequence- and time-dependent properties. As marathon course design involves various objectives related to health, safety, performance and experience, LFATP needs to be solved in a multiobjective environment to identify the best course design for race organizers. For this reason, we introduce an Interactive Weight Region-Based approach (IWRA) that reaches a most preferred solution of the decision maker (DM) in multiobjective optimization. IWRA is an iterative approach which iterates between solution generation and comparison phases: At each iteration, IWRA presents a new solution to the DM by using weight diversification, obtained by solving an integer program. The DM's preference information is used to refine the unexplored weight region. We provide finitely converging algorithms solving the weighted sum problem for multiobjective linear programs and multiobjective integer programs. Different from existing approaches, IWRA separates weight generation and solution generation efforts, and provides a systematic weight generation scheme which is capable of exploring the entire weight region. We empirically demonstrate the effectiveness of IWRA under various settings and assumptions through comparisons with related methods from the literature which also ensure identification of optimal decisions. IWRA is also extended to the weighted Tchebycheff problem setting to handle unsupported nondominated solutions. Finally, both tour finding and multiobjective projects are combined to generate a series of course designs for the Bank of America Chicago Marathon which serves the race organizers as a catalog of options. At this stage, we select the underlying LFATP formulation based on the dominant structure of the aggregated objective. The experiments show that significant improvements can be obtained by making relatively small changes to the existing course.

Last modified

• 04/09/2019

Creator

• Mehmet Basdere

DOI

• https://doi.org/10.21985/N2SV1N

Subject

• Industrial Engineering and Management Sciences

Keyword

• multiobjective optimization
• disjunctive programming
• integer programming
• routing
• linear programming

Date created

• 2018-01-01

Resource type

• Dissertation

Rights statement

• In Copyright