上海交通大学学报

上海交通大学学报（自然版）

• 自动化技术、计算机技术 • 上一篇    下一篇

基于阈值深度优先策略求解非对称旅行商问题的混合分枝定界算法

朱奕,杨根科,潘常春   

  1. (上海交通大学 电子信息与电气工程学院， 上海 200240)
  • 收稿日期:2007-10-21 修回日期:1900-01-01 出版日期:2008-10-28 发布日期:2008-10-28
  • 通讯作者: 杨根科

Threshold Constraint Based DepthFirstSearch for BranchBound Algorithm Solving Asymmetric Traveling Salesman Problems

ZHU Yi, YANG Gen-ke, PAN Chang-chun   

  1. (School of Electronic, Information and Electrical Engineering,
    Shanghai Jiaotong University, Shanghai 200240, China)
  • Received:2007-10-21 Revised:1900-01-01 Online:2008-10-28 Published:2008-10-28
  • Contact: YANG Gen-ke

摘要： 针对非对称旅行商问题(ATSP)模型计算难问题，提出了一种基于深度和广度方向混合搜索的启发式策略的分枝定界算法.该算法采取有阈值的深度优先加广度加权随机搜索的策略确定分枝节点，通过求解附加弧段约束的分配问题确定下界，通过消除子环的修补算法确定上界，从而有效综合了确定性方法的准确性和启发式方法的快速性.将此算法应用于求解经典TSPLIB库中的全部ATSP问题和热轧调度的仿真研究，表现出了较高的效率和可行性.

关键词: 非对称旅行商问题, 分枝定界, 阈值, 修补算法, 调度

Abstract: An integration approach based on heuristic strategies and branchbound algorithm was proposed for solving asymmetric traveling salesman problem. In this method, associated with each node of the branchdecision tree, a parametric solution of the relaxed assignment problem and a feasible solution obtained by patching algorithm are used to tighten the lower and upper bound. A hueristic strategy that conbines the threshold constraint based depthfirstsearch and weighted random breadthsearch is adopted to seek the optimal solution. Therefore, a feasible solution that is very close to the optimal solution can be found in comparatively short time. The computational results on data in the TSPLIB and a hot strip scheduling simulation show the efficiency of the proposed algorithm.

中图分类号: