编辑实验 创建词条
人大经济论坛-经管百科

旅行商问题 发表评论(0) 编辑词条

目录

旅行商问题(Traveling Saleman Problem,TSP)

什么是旅行商问题 编辑本段回目录

  旅行商问题(Traveling Saleman Problem,TSP)是VRP的特例,由于Gaery已证明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年
经管百科已经为您找到更多关于“旅行商问题”的相关信息,点击查看>>

附件列表

→如果您认为本词条还有待完善,请 编辑词条

词条内容仅供参考,如果您需要解决具体问题
(尤其在法律、医学等领域),建议您咨询相关领域专业人士。
0

标签: 旅行商问题 供应链 城市 推销员 插入法 物流 线性规划 美国RAND公司 节省法 车辆路径问题 顾客

收藏到: Favorites  

同义词: 暂无同义词

关于本词条的评论 (共0条)发表评论>>