摘要
时间依赖型旅行商问题(TDTSP)是旅行商问题(TSP)的延伸.在该问题中,任意两节点间的旅行时间(成本)不仅取决于节点间的距离,还依赖于一天中具体时段或节点在哈密顿圈中所处的具体位置.对基于节点所处哈密顿圈中具体位置的TDTSP问题建立相应的数学模型,并提出求解该问题的动态搜索算法.通过实验仿真,验证了动态搜索算法优于目前在邻域搜索领域求解该问题最有效的动态规划启发式算法.
Time dependent traveling salesman problem （TDTSP） is an extension of the traveling salesman problem （TSP）, in which the travel time or cost between two nodes depends on not only the distance between the nodes, but also the time of clay or the node position in the Hamilton cycle. In this paper, we formulate the model for the TDTSP based on the node position in the Hamilton cycle, and develop the novel dynasearch algorithms to solve it. Simulation shows that the dynasearch algorithms are superior to the most effective dynamic programming heuristics in local search area.
出处
《控制与决策》
EI
CSCD
北大核心
2009年第2期274-278,共5页
Control and Decision
基金
国家社科基金项目(07BJY038)
教育部新世纪优秀人才支持计划项目(NCET-04-0886)
关键词
时间依赖型旅行商问题
哈密顿圈
动态搜索算法
动态规划启发式
Time dependent traveling salesman problem
Hamilton cycle
Dynasearch algorithms
Dynamic programming heuristics
