多旅行銷售員問題的多連接樹鬆弛法
A Connected M-tree Relaxation for M-travelling Salesmen Problems
國立臺灣大學管理學院(College of Management, National Taiwan University)
- 類型
- 論文
- 卷期
- 3卷1期
- 出版
- 1992年05月
- 頁碼
- 311–328
- 編號
- NTUEJ00010527
需要全文時,可以向出版單位洽詢,聯絡方式見期刊資訊。
摘要
對於較大型之多旅行銷售員問題,目前合理之求最佳解的方式乃是分支限界法與鬆弛法並用。前者用來取得上限,後者則是用來求取下限。在求單一旅行銷售員問題之最佳解上,Held與Karp兩人曾提出「多一支之擴張最小生成樹」為其鬆弛之基礎模式,得到極佳之效果。由於此種破題之方式不但能保留問題之圖像本質,所產生之下限又相當強;若干研究者乃根據類似之思考方對於多旅行銷售員問題提出「多叢樹模型」、「次數限制擴張生成樹模型」來做為鬆弛法之基本模型。本論文之特點與貢獻在於提出一種比過去之研究在圖形結構更完整,在運算結果更強之新鬆弛模型,稱之為多連接樹鬆弛法,以做為解多旅行銷售員問題時之下限模式。
Abstract
Utilizing branch-and-bound and relaxation techniques to solve large scale m-travelling salesmen problems to optimum needs strong lower bound procedures. Since the landmark 1-tree relaxation model devised by Held and Karp for travelling salesman problems, some relaxation models, such as: m-trees, augmented degree-constrained spanning trees have been developed for the solution of m-travelling salesman problems. This paper presents a new graphical structure, denoted as connected m-tree, to be a more promising relaxation model for m-travelling salesmen problems. Model, algorithm, and computational results are reported.