TY - THES

T1 - Symmetric Quadratic Traveling Salesman Problem with Reload Costs

T2 - Applications & Solution Approaches

AU - Hanzlovic, Michael

N1 - no embargo

PY - 2024

Y1 - 2024

N2 - This thesis delves into the intricate world of the Symmetric Quadratic Traveling Salesman Problem (SQTSP), particularly focusing on instances where reload costs are incurred when switching between two types of edges during the traversal. Such a scenario is not only realistic in various practical applications, like logistics and route planning, but also poses unique challenges to traditional solution methods. The primary objective of this research is to rigorously test and evaluate the effectiveness of existing Integer Linear Programming (ILP) linearizations, various Subtour Elimination Constraints (SEC), and heuristics, as documented in the literature, when applied to the SQTSP that models the reload cost component. In addition to the evaluative study, this thesis contributes by the development of a novel heuristic specifically designed for this unique variant of the SQTSP. This new heuristic is tailored to effectively handle the complexities introduced by the reload costs, aiming to optimize the traversal sequence in a manner that balances the traditional optimization goals of the SQTSP with the specific cost considerations. The findings unveil a nuanced interdependence between graph composition and solver complexity, particularly under the influence of the balance of flagged to unflagged edges and the relative magnitude of reload costs. Notably, solver times manifest a bell-shaped curve akin to a normal distribution when related to the percentage of flagged edges, peaking as this percentage nears a 50/50 equilibrium. Concurrently, solver times respond to an increase in reload costs relative to average edge weights in an exponential fashion, highlighting the intricate, non-linear dynamics at play. The exploration and findings presented in this thesis not only contribute to the theoretical advancement in the field of operations research but also have implications for practical applications. By extending the existing knowledge on SQTSP and introducing new methodologies for addressing the complexities of reload costs, this research provides valuable insights for both academics and practitioners in the field of optimization and logistics. In essence, this thesis navigates through the theoretical and practical landscapes of the SQTSP with reload costs, offering a comprehensive analysis of existing methods and pioneering a new approach to address the nuanced challenges of this problem.

AB - This thesis delves into the intricate world of the Symmetric Quadratic Traveling Salesman Problem (SQTSP), particularly focusing on instances where reload costs are incurred when switching between two types of edges during the traversal. Such a scenario is not only realistic in various practical applications, like logistics and route planning, but also poses unique challenges to traditional solution methods. The primary objective of this research is to rigorously test and evaluate the effectiveness of existing Integer Linear Programming (ILP) linearizations, various Subtour Elimination Constraints (SEC), and heuristics, as documented in the literature, when applied to the SQTSP that models the reload cost component. In addition to the evaluative study, this thesis contributes by the development of a novel heuristic specifically designed for this unique variant of the SQTSP. This new heuristic is tailored to effectively handle the complexities introduced by the reload costs, aiming to optimize the traversal sequence in a manner that balances the traditional optimization goals of the SQTSP with the specific cost considerations. The findings unveil a nuanced interdependence between graph composition and solver complexity, particularly under the influence of the balance of flagged to unflagged edges and the relative magnitude of reload costs. Notably, solver times manifest a bell-shaped curve akin to a normal distribution when related to the percentage of flagged edges, peaking as this percentage nears a 50/50 equilibrium. Concurrently, solver times respond to an increase in reload costs relative to average edge weights in an exponential fashion, highlighting the intricate, non-linear dynamics at play. The exploration and findings presented in this thesis not only contribute to the theoretical advancement in the field of operations research but also have implications for practical applications. By extending the existing knowledge on SQTSP and introducing new methodologies for addressing the complexities of reload costs, this research provides valuable insights for both academics and practitioners in the field of optimization and logistics. In essence, this thesis navigates through the theoretical and practical landscapes of the SQTSP with reload costs, offering a comprehensive analysis of existing methods and pioneering a new approach to address the nuanced challenges of this problem.

KW - SQTSP

KW - Reload Costs

KW - Linearization

KW - ILP

KW - Subtour Elimination Constraint

KW - SQTSP

KW - Umladekosten

KW - Linearisierung

KW - ILP

KW - Subtour Eliminierungs-Ungleichung

U2 - 10.34901/mul.pub.2024.123

DO - 10.34901/mul.pub.2024.123

M3 - Master's Thesis

ER -