Ordered Median Traveling Salesman Problem

ABSTRACT This paper introduces a novel combinatorial optimization problem with ordering constraints, termed the Ordered Median Traveling Salesman Problem (OMTSP). The OMTSP integrates key elements from both the classic Traveling Salesman Problem (TSP) and the Ordered Median Location Problem. Specifically, the objective is to identify a tour that minimizes a weighted sum of the sorted arc lengths within the tour. This flexible framework enables the modeling of a wide range of combinatorial optimization problems related to the traditional TSP, like the bottleneck TSP, the balanced TSP, or other TSP variants in which fairness measures are applied to the arcs of the tour. In this work, we present new mathematical formulations for the OMTSP across different variable spaces, which are solved using a branch‐and‐cut approach. Leveraging several newly derived structural properties, we enhance these formulations through advanced preprocessing strategies, variable bounding and variable fixing techniques, as well as through the introduction of new valid inequalities. A comprehensive computational study is conducted to evaluate the effectiveness of the proposed formulations and their associated improvements.