期刊
APPLIED MATHEMATICS AND COMPUTATION
卷 216, 期 1, 页码 125-137出版社
ELSEVIER SCIENCE INC
DOI: 10.1016/j.amc.2010.01.021
关键词
Genetic algorithm; Initial solution generator; Probabilistic traveling salesman problem; Permutation test; TSPLIB
资金
- National Science Council of Taiwan [972410-H-260-012, 98-2410-H-260-052, 98-2918-I-260-001]
The probabilistic traveling salesman problem (PTSP) is a topic of theoretical and practical importance in the study of stochastic network problems. It provides researchers with a modeling framework for exploring the stochastic effects in routing problems. This paper proposed three initial solution generators (NN1, NN2, RAN) under a genetic algorithm (GA) framework for solving the PTSP. A set of numerical experiments based on heterogeneous and homogeneous PTSP instances were conducted to test the effectiveness and efficiency of the proposed algorithms. The results from the heterogeneous PTSP show that the average E[tau] values obtained by the three generators under a GA framework are similar to those obtained by the Previous Best, but with an average computation time saving of 50.2%. As for the homogeneous PTSP instances, NN1 is a relatively better generator among the three examined, while RAN consistently performs worse than the other two generators in terms of average E[tau] values. Additionally, as compared to previously reported studies, no one single algorithm consistently outperformed the others across all homogeneous PTSP instances in terms of the best E[tau] values. The fact that no one initial solution generator consistently performs best in terms of the E[tau] value obtained across all instances in heterogeneous cases, and that the performance of each examined algorithm is dependent on the number of nodes (n) and probability (p) for homogeneous cases, suggest the possibility of context- dependent phenomenon. Finally, to obtain valid results, researchers are advised to include at least a certain amount of test instances with the same combination of n and p when conducting PTSP experiments. (C) 2010 Elsevier Inc. All rights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据