Multi-Color Traveling Salesman Problem

J. J. Salazar Gonzalez, R. Wolfler-Calvo

In this talk we investigate a new challenging variant of the classical Travelling Salesman Problem where the set of nodes is divided into clusters and a different color is associated with each cluster. The goal is to find a Minimum Cost Hamiltonian Cycle satisfying different separation constraints between nodes with the same color. It generalizes a previous problem studied in the literature as Black-and-White Traveling Salesman Problem, and finds applications in Overnight Security Service. We present a new effective mathematical formulation for the problem. Since it involves an exponential number of constraints we devise separations procedures to be used within a Branch-and-Cut framework. Promising preliminary results are obtained on a set of random instances.

Keywords: Traveling Salesman Problem, Integer Programming, Branch and Cut

GT20 Transportation
November 8, 2023  10:10 AM
HC1: Canónigos Room 1

M. Calvo González, J. A. Mesa López-Colmenar, F. Perea Rojas-Marcos

S. Vivó Sánchez, F. Perea Rojas-Marcos

T. Corberán Fabra, I. Plana Andani, J. M. Sanchis Llopis