An improved heuristic for the probabilistic traveling salesman problem with deadlines based on GPGPU

Stochastic combinatorial optimization problems have received increasing attention in recent years. These problems can be used to obtain more realistic models for real world applications. The drawback is that stochastic combinatorial optimization problems are usually much harder to solve than their non-stochastic counterparts and therefore efficient heuristics for these problems are of great importance. In this paper we focus on the Probabilistic Traveling Salesman Problem with Deadlines, a well-known stochastic vehicle routing problem. This problem can be efficiently solved using a heuristic based on general-purpose computing on graphics processing units. We show how such a heuristic can be further improved to allow a more efficient utilization of the graphics processing unit. We extensively discuss our results and point out how our techniques can be generalized for solving other stochastic combinatorial optimization problems.