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

摘要

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