全球专业中文经管百科,由121,994位网友共同编写而成,共计436,015个条目

旅行商問題

用手机看条目

出自 MBA智库百科(https://wiki.mbalib.com/)

(重定向自TSP问题)

旅行商問題(Traveling Saleman Problem,TSP)

目錄

什麼是旅行商問題

  旅行商問題(Traveling Saleman Problem,TSP)是VRP的特例,由於Gaery[1]已證明TSP問題是NP難題,因此,VRP也屬於NP難題。

  旅行商問題(TSP)又譯為旅行推銷員問題、貨郎擔問題,簡稱為TSP問題,是最基本的路線問題,該問題是在尋求單一旅行者由起點出發,通過所有給定的需求點之後,最後再回到原點的最小路徑成本。最早的旅行商問題的數學規劃是由Dantzig(1959)等人提出[2]

  TSP問題在物流中的描述是對應一個物流配送公司,欲將n個客戶的訂貨沿最短路線全部送到。如何確定最短路線。

  TSP問題最簡單的求解方法是枚舉法。它的解是多維的、多局部極值的、趨於無窮大的複雜解的空間,搜索空間是n個點的所有排列的集合,大小為(n-1)。可以形象地把解空間看成是一個無窮大的丘陵地帶,各山峰或山谷的高度即是問題的極值。求解TSP,則是在此不能窮盡的丘陵地帶中攀登以達到山頂或谷底的過程。

旅行商問題的歷史

  旅行商問題字面上的理解是:有一個推銷員,要到n個城市推銷商品,他要找出一個包含所有n個城市的具有最短路程的環路。

  TSP的歷史很久,最早的描述是1759年歐拉研究的騎士周游問題,即對於國際象棋棋盤中的64個方格,走訪64個方格一次且僅一次,並且最終返回到起始點。

  TSP由美國RAND公司於1948年引入,該公司的聲譽以及線性規劃這一新方法的出現使得TSP成為一個知名且流行的問題。

旅行商問題的解法[2]

  旅行推銷員的問題,我們稱之為巡行(Tour),此種問題屬於NP-Complete的問題,所以旅行商問題大多集中在啟髮式解法。Bodin(1983)等人將旅行推銷員問題的啟髮式解法分成三種:

  1、途程建構法Tour Construction Procedures

  從距離矩陣中產生一個近似最佳解的途徑,有以下幾種解法:

  1)最近鄰點法(Nearest Neighbor Procedure):一開始以尋找離場站最近的需求點為起始路線的第一個顧客,此後尋找離最後加入路線的顧客最近的需求點,直到最後。

  2)節省法(Clark and Wright Saving):以服務每一個節點為起始解,根據三角不等式兩邊之和大於第三邊之性質,其起始狀況為每服務一個顧客後便回場站,而後計算路線間合併節省量,將節省量以降序排序而依次合併路線,直到最後。

  3)插入法(Insertion procedures):如最近插入法、最省插入法、隨意插入法、最遠插入法、最大角度插入法等。

  2、途程改善法Tour Improvement Procedure

  先給定一個可行途程,然後進行改善,一直到不能改善為止。有以下幾種解法:

  1)K-Opt(2/3 Opt):把尚未加入路徑的K條節線暫時取代目前路徑中K條節線,並計算其成本(或距離),如果成本降低(距離減少),則取代之,直到無法改善為止,K通常為2或3。

  2)Or-Opt:在相同路徑上相鄰的需求點,將之和本身或其它路徑交換且仍保持路徑方向性,並計算其成本(或距離),如果成本降低(距離減少),則取代之,直到無法改善為止。

  3、合成啟發法Composite Procedure

  先由途程建構法產生起始途程,然後再使用途程改善法去尋求最佳解,又稱為兩段解法(two phase method)。有以下幾種解法:

  1)起始解求解+2-Opt:以途程建構法建立一個起始的解,再用2-Opt的方式改善途程,直到不能改善為止。

  2)起始解求解+3-Opt:以途程建構法建立一個起始的解,再用3-Opt的方式改善途程,直到不能改善為止。

參考文獻

  1. 祝崇俊,劉民,吳澄.供應鏈車輛路徑問題的研究進展及前景[J].電腦集成製造系統-CMS.2001,7(11):1-6
  2. 2.0 2.1 鄧宇佑(碩士).求解醫院運輸部門運輸中心個數最佳化之研究(D).成功大學工業管理研究所碩士論文,1991年
本條目對我有幫助50
MBA智库APP

扫一扫,下载MBA智库APP

分享到:
  如果您認為本條目還有待完善,需要補充新內容或修改錯誤內容,請編輯條目投訴舉報

本条目由以下用户参与贡献

Zfj3000,Vulture,Dan,KAER.

評論(共0條)

提示:評論內容為網友針對條目"旅行商問題"展開的討論,與本站觀點立場無關。

發表評論請文明上網,理性發言並遵守有關規定。

打开APP

以上内容根据网友推荐自动排序生成

官方社群
下载APP

闽公网安备 35020302032707号