A metaheuristic framework for stochastic combinatorial optimization problems based on GPGPU with a case study on the probabilistic traveling salesman problem with deadlines

In this work we propose a general metaheuristic framework for solving stochastic combinatorial optimization problems based on general-purpose computing on graphics processing units (GPGPU). This framework is applied to the probabilistic traveling salesman problem with deadlines (PTSPD) as a case study. Computational studies reveal significant improvements over state-of-the-art methods for the PTSPD. Additionally, our results reveal the huge potential of the proposed framework and sampling-based methods for stochastic combinatorial optimization problems.

► General metaheuristic framework for solving stochastic combinatorial optimization problems based on GPGPU.
► Low level parallelism on the sample level.
► Case-study on the probabilistic traveling salesman problem.
► Significant improvements over state-of-the-art methods.