旅行商问题

什么是旅游商困难

旅游商困难（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的方式改观途程，直到不能改观为止。

参考文献

↑ 祝崇俊,刘民,吴澄.供给链中车辆路径困难的研究进度及前景[J].计算机集成制造系统－CMS.2001,7(11):1-6

↑ ^2.02.1 邓宇佑(硕士).求解医院运输部门运输中心个数最佳化之研究(D).成功大学工业治理研究所硕士论文，1991年