Runtime reduction techniques for the probabilistic traveling salesman problem with deadlines

The probabilistic traveling salesman problem with deadlines (PTSPD) is an extension of the well-known probabilistic traveling salesman problem in which, in addition to stochastic presence, customers must also be visited before a known deadline. For realistically sized instances. the problem is impossible to solve exactly, and local-search methods struggle due to the time required to evaluate the objective function. Because computing the deadline violations is the most time consuming part of the objective. we focus on developing approximations for the computation of deadline violations. These approximations can be imbedded in a variety of local-search methods, and we perform experiments comparing their performance using a I-shift neighborhood. These computational experiments show that the approximation methods lead to significant runtime improvements without loss in quality. (C) 2008 Elsevier Ltd. All rights reserved.