• 作者： 許蒞彥
• 作者服務機構： 國立中山大學企業管理研究所
• 中文摘要： 旅行推銷員問題是一典型的組合最佳化問題，由於此問題應用在實際生活中的情形處處可見，因而使得這方面的研究益發受人重視。然而由於旅行推銷員問題本身的特性，使得在途徑長度的精確性以及計算時間方面往往無法同時顧及，尤其在處理較大問題的時候，迄今尚無一種方法能保證在求得近似最佳解的時候，同時能讓其計算時間能降至最低，而為人接受。 本文的研究即針對了這方面的問題，在仍然能獲得一不錯的精確度的同時，計算時間的減少方面，卻做了一相當大的突破。文中，我們首先利用了圓環插柿入法在計算時間如何減少的觀念，針對其現存的缺點稍加修正之後，再從而發展出我們的新方法－凸緣法，亦即利用凸緣(Convex Hull)的特性及限制，使得在處理問題的時候，除了可獲致極佳的精確度之外，同時將計算時間減至最低。從經濟上的觀點來看，花費在計算機上的成本，也因而得以大量的降低了。
• 英文摘要： This paper is intended to introduce a new heuristic approach－The Multiple Convex Hulls Method(MCHM)－for solving the Traveling Salesman Problem (TSP). The Multiple Convex Hulls Method is theresearch result evolved through a study of the Circular Insertion Method. The purpose for conducting aresearch on MCHM was aimed to strengthen the weakness of the Circular Insertion Method, and, lay thefoundation for a step-by-step application procedure. The heart of the MCHM is to connect nodes to construct as many convex hulls as possible, startingwith the farthest node. It is well known that in a two-dimensional space, the optimal tour of nodes fallingon the boundary of a convex hull will follow the order in which they appear in the hull. Thus, for any typeof node distribution, the MCHM would actually help identify the largest convex hull, which encircles allremaining nodes, and the second largest convex hull, which encircles all nodes except those falling on thefirst and the second hulls, the third－－－－, until the very last one, which might be a hull or a line or just onenode. The so identified convex hulls as well as nodes on each hull are to replace previous rings as well asthe number of nodes in each ring. Consequently, the geometrical characteristics of node distribution be-come the prime factor in determing the number of hulls, as well as nodes on each hull. It might be thisdynamic characteristic that led to our research findings, which showed the MCHM being more capable ofcoping with problems of any unique type of node distribution than the Farthest Insertion Method.
• 中文關鍵字： --
• 英文關鍵字： --