用动态搜索算法求解时间依赖型旅行商问题

摘要：

为解决基于时段的时间依赖型旅行商问题(time-dependent traveling salesman problem,TDTSP),提出处 理跨时段的方法,并建立了相应的数学模型.用动态搜索算法ds-k-opt(k=2,2.5,3)分别求解该问题.仿真算例表明,动态搜索算法中部分ds-2.5-opt解和绝大部分ds-3-opt解优于动态规划启发式算法,且能求解更大规模的TDTSP问题.动态搜索算法的解随k的增大而更优,但运算时间也更长.

关键词：旅行商问题、动态搜索算法、动态规划启发式

所属期刊栏目：43

分类号：F253.04(物资经济)

资助基金：国家社会科学基金07BJY038;教育部跨世纪优秀人才培养计划NCET-04-0886;四川省教育厅资助项目20058025

在线出版日期：2008-06-24（万方平台首次上网日期，不代表论文的发表时间）

页数：共7页

页码：187-193