动态搜索算法求解时间依赖型旅行商问题研究
来源期刊:控制与决策2009年第2期
论文作者:李妍峰 李军 赵达
文章页码:274 - 278
关键词:时间依赖型旅行商问题;哈密顿圈;动态搜索算法;动态规划启发式;
摘 要:时间依赖型旅行商问题(TDTSP)是旅行商问题(TSP)的延伸.在该问题中,任意两节点间的旅行时间(成本)不仅取决于节点间的距离,还依赖于一天中具体时段或节点在哈密顿圈中所处的具体位置.对基于节点所处哈密顿圈中具体位置的TDTSP问题建立相应的数学模型,并提出求解该问题的动态搜索算法.通过实验仿真,验证了动态搜索算法优于目前在邻域搜索领域求解该问题最有效的动态规划启发式算法.
李妍峰1,2,李军1,赵达1
1. 西南交通大学经济管理学院2. 四川师范大学商学院
摘 要:时间依赖型旅行商问题(TDTSP)是旅行商问题(TSP)的延伸.在该问题中,任意两节点间的旅行时间(成本)不仅取决于节点间的距离,还依赖于一天中具体时段或节点在哈密顿圈中所处的具体位置.对基于节点所处哈密顿圈中具体位置的TDTSP问题建立相应的数学模型,并提出求解该问题的动态搜索算法.通过实验仿真,验证了动态搜索算法优于目前在邻域搜索领域求解该问题最有效的动态规划启发式算法.
关键词:时间依赖型旅行商问题;哈密顿圈;动态搜索算法;动态规划启发式;