A memetic algorithm for the probabilistic traveling salesman problem

The probabilistic traveling salesman problem (PTSP) is an important theoretica and practical topic in the study of stochastic network problems. It provides researchers with a modeling framework for exploring the stochastic effects in routing problems. This paper focuses on developing a memetic algorithm (MA) by incorporating the nearest neighbor algorithm to generate initial solutions, 1-shift and/or 2-opt exchanges for local search and edge recombination (ER) crossover to efficiently and effectively solve the PTSP. In addition, a mixed local search strategy by randomly selecting two different local search methods (i.e., 1-shift and 2-opt exchanges) is introduced to further enhance the effectiveness of the proposed MA for solving the PTSP. A set of numerical experiments based on both heterogeneous and homogeneous PTSP instances were conducted to test the validity of the proposed MA. The numerical results showed that the newly proposed MA enhanced the performance in terms of objective function value and/or computation time in most of the tested cases as compared to existing methods tested in previous studies. Moreover, the results indicated that incorporating mixed local search strategy into the MA can significantly increase the solution quality. These findings show the potential of the proposed MA in effectively and efficiently solving the large-scale PTSP.