Exact Algorithms for the (A)symmetric Traveling Salesman Problem with order dependent constraints and objective function


2017 to 2019


This research project studies generalizations of the (A)symmetric Traveling Salesman Problem where the objective functions or the constraints depend from the visit order of the vertices. In the first case a cost term is added to the traditional route cost of the problem: this can be encoded as a linear or nonlinear function of the visit time. In the second case, again the satisfaction of a constraint associated with a vertex or an arc depends on the visit order, e.g., this happens in capacitated versions of the TSP, where the tour is traveled by a vehicle carrying heavy goods to be delivered at nodes, each node has an associated weight capacity. The goal is to strengthen Mixed Integer Programming models by studying exponential-size formulations incorporating subtour elimination constraints and, eventually, problem specific inequalities to be separated via dedicated algorithms. Branch-and-Cut algorithms will be developed and tested on benchmark instances from the literature.



Financed by: Air Force Office of Scientific Research