Symmetric Quadratic Traveling Salesman Problem with Reload Costs: Applications & Solution Approaches

Michael Hanzlovic

Research output: ThesisMaster's Thesis

6 Downloads (Pure)

Abstract

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.
Translated title of the contributionSymmetrisches quadratisches Traveling Salesman Problem mit Umladekosten: Anwendungen & Lösungsansätze
Original languageEnglish
QualificationDipl.-Ing.
Awarding Institution
  • Montanuniversität
Supervisors/Advisors
  • Brand, Clemens, Supervisor (internal)
  • Staněk, Rostislav, Co-Supervisor (internal)
Award date28 Jun 2024
DOIs
Publication statusPublished - 2024

Bibliographical note

no embargo

Keywords

  • SQTSP
  • Reload Costs
  • Linearization
  • ILP
  • Subtour Elimination Constraint

Cite this