The Probabilistic Traveling Salesman Problem, introduced in 1985 by Jaillet, is one of the fundamental stochastic versions of the Traveling Salesman Problem: After the tour is chosen, each vertex is deleted with given probability 1-p. The eliminated vertices are bypassed which leads to shorter tours. The aim is to minimize the expected tour length. The resulting Mixed Integer Program is difficult, because the objective function is a high-degree polynomial in the binary edge variables. Linearisations lead to a large number of variables. We show that for large p, the model can be well approximated by a quadratic model. This quadratic model can be linearised to a small linear model which leads to good primal solutions and strong lower bounds up to 80 probabilistic nodes. We explain the approach and present numerical results.
Citation
Institute of Transport Logistics TU Dortmund June 2015