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
Scheduled
GT20 Transportation
November 8, 2023 10:10 AM
HC1: Canónigos Room 1