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