摘要
对时变旅行商问题进行描述,提出处理一般跨时段的新方法,并建立数学模型.在求解方法上构造动态搜索优化算法ds-k-opt(k=2,2.5,3)求解该问题.通过实验仿真,大部分动态搜索优化算法解质量优于动态规划启发式算法,且求解规模更大.动态搜索优化算法解随k值增大而更优,算法运行时间也随之增加.
In this paper,the time varying traveling salesman problem(TDTSP) was formulated by dealing with general time periods crossing,and novel dynamic search optimization algorithms ds-k-opt(k=2,2.5,3) were developed to solve it.Through the simulation,the dynamic search optimization algorithms can solve larger size problem compared with dynamic programming heuristics.As for the solution quality,most solutions of dynamic search optimization algorithms are better than those of dynamic programming heuristics.The solution of the dynamic search optimization algorithm becomes better with the increase of k value,while the computation time becomes longer with it.
出处
《系统工程学报》
CSCD
北大核心
2010年第5期585-591,共7页
Journal of Systems Engineering
基金
国家自然科学基金重点资助项目(70631001)
国家自然科学基金资助项目(71001005)
国家973资助项目(2006CB705500)
国家科技部博士后基金资助项目(20090460196)
中央高校基本科研业务费专项资金资助项目(2009JBM050)
关键词
时变旅行商问题
跨时段
动态搜索优化算法
动态规划启发式
time varying traveling salesman problem(TDTSP)
time periods crossing
dynamic search optimization algorithms
dynamic programming heuristics