臺大學術期刊資料庫NTU Journal Database

多旅行銷售員問題的多連接樹鬆弛法

A Connected M-tree Relaxation for M-travelling Salesmen Problems

黃崇興(Chung-Hsing Huang)

國立臺灣大學管理學院(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.

關鍵詞

程式與 AI 助手可以改用資料介面(JSON、MCP),查詢比讀頁面快。給程式與 AI 代理的存取說明