Diversified local search strategy under scatter search framework for the probabilistic traveling salesman problem |
| |
Authors: | Yu-Hsin Liu |
| |
Institution: | Department of Civil Engineering, National Chi Nan University, No. 1, University Road, Puli, Nantou Hsien 54561, Taiwan, ROC |
| |
Abstract: | This paper focuses on introducing a concept of diversified local search strategy under the scatter search framework for the probabilistic traveling salesman problem (PTSP). Different combinations of three commonly used local search methods in the PTSP, i.e., 1-shift, 2-opt, and 3-opt, were used to investigate its effects. A set of numerical experiments were conducted to test the validity of the proposed strategy based on randomly generated test instances. The numerical results and the permutation test showed that the diversified local search strategy, especially by combining 1-shift and 2-opt algorithms, can most effectively solve the homogeneous and heterogeneous PTSP in most of the tested instances in comparison with the single local search strategy under scatter search framework. |
| |
Keywords: | Metaheuristics Diversified local search Scatter search Probabilistic traveling salesman problem Permutation test |
本文献已被 ScienceDirect 等数据库收录! |
|