旅行商问题

古香居士

回复 10# zw_9999
6 q! i3 `4 _- _  \2 C: Y6 Q+ {( K% f

    呵呵呵呵呵呵呵呵

guchenmail

回复一下，赚赚体力，不懂，啊啊啊啊啊啊

黯淡勋爵

还没有开始着手~~~~~~~~~~~~~~~~~~还没有开始着手~~~~~~~~~~~~~~~~~~还没有开始着手~~~~~~~~~~~~~~~~~~还没有开始着手~~~~~~~~~~~~~~~~~~

April-qing

很复杂 ，很难

dirk

回复 1# 蒋伟华
2 P2 U7 f% W; ]" k/ ^0 p
% R  q* P7 z. u0 j* |& b% s
: v6 Z8 v5 S  `( G/ t$ c    B题目的理解

本帖来自:数学中国 作者: chuanheyuanyuan 日期: 3 天前 13:19 您是本帖第322个浏览者

7 `0 f9 `1 L; Q7 Y$ I# H- R

1、第一问是求几何距离。 + J  ~4 I% m3 m+ ^/ M) S; {' r" J  w$ B5 E" z2、第二问在第一问的基础上考虑交通工具的选择，在每个城市停留三天主要可能是考虑到旅行战线会拉到567月份，粤东，福建，浙江，海南等地会有台风等恶劣天气无法乘坐飞机。可以放在模型可行性复杂性分析里" g6 k- l# Y' a 9 n+ O) Z. f0 I+ x' g, p7 @' l9 c3 L- |+ s8 X& V  Z: S( p 第一次参加数学建模。。。昨天晚上才开始决定准备。。。之前不知建模为何物。。。个人浅薄的理解。。。。待与牛人探讨。。。轻拍

dirk

回复 15# dirk

5 u, [2 o8 M$ a4 ~8 r* H
6 B2 C1 G3 {5 [8 H$ X    henhao

langlegend

牛人说：这题也太难了吧！！！！！！！！！！！！

wangdao_1

旅行商问题（Traveling Saleman Problem，TSP）又译为旅行推销员问题、货郎担问题，简称为TSP问题，是最基本的路线问题，该问题是在寻求单一旅行者由起点出发，通过所有给定的需求点之后，最后再回到原点的最小路径成本。最早的旅行商问题的数学规划是由Dantzig（1959）等人提出。
　　TSP问题在物流中的描述是对应一个物流配送公司，欲将n个客户的订货沿最短路线全部送到。如何确定最短路线。
　　TSP问题最简单的求解方法是枚举法。它的解是**的、多局部极值的、趋于无穷大的复杂解的空间，搜索空间是n个点的所有排列的集合，大小为（n-1）。可以形象地把解空间看成是一个无穷大的丘陵地带，各山峰或山谷的高度即是问题的极值。求解TSP，则是在此不能穷尽的丘陵地带中攀登以达到山顶或谷底的过程。
( j- F" M( ?) v4 W2 ][编辑本段]旅行商问题的历史
' N9 i; E3 N+ m6 S7 g  N' f　　旅行商问题字面上的理解是：有一个推销员，要到n个城市推销商品，他要找出一个包含所有n个城市的具有最短路程的环路。
; N) z& H- D+ H( p: o% m; h7 n' [  W　　TSP的历史很久，最早的描述是1759年欧拉研究的骑士周游问题，即对于国际象棋棋盘中的64个方格，走访64个方格一次且仅一次，并且最终返回到起始点。
7 k" p" E2 t+ H4 H5 Z; ]　　TSP由美国RAND公司于1948年引入，该公司的声誉以及线性规划这一新方法的出现使得TSP成为一个知名且流行的问题。
1 s1 F( k+ ~5 x4 N& l  S. w0 |0 L$ d[编辑本段]旅行商问题的解法
　　旅行推销员的问题，我们称之为巡行（Tour），此种问题属于NP-Complete的问题，所以旅行商问题大多集中在启发式解法。Bodin（1983）等人将旅行推销员问题的启发式解法分成三种：
　　1、途程建构法（Tour Construction Procedures）
　　从距离矩阵中产生一个近似最佳解的途径，有以下几种解法：
# N, \9 G' `* D: j' j$ s　　1）最近邻点法（Nearest Neighbor Procedure）：一开始以寻找离场站最近的需求点为起始路线的第一个顾客，此后寻找离最后加入路线的顾客最近的需求点，直到最后。
. _1 S' u+ y4 h  d2 R9 }　　2）节省法（Clark and Wright Saving）：以服务每一个节点为起始解，根据三角不等式两边之和大于第三边之性质，其起始状况为每服务一个顾客后便回场站，而后计算路线间合并节省量，将节省量以降序排序而依次合并路线，直到最后。
1 J1 ?+ _, }' }1 b0 W+ ]　　3）插入法（Insertion procedures）：如最近插入法、最省插入法、随意插入法、最远插入法、最大角度插入法等。
2 }) O" B4 y. F　　2、途程改善法（Tour Improvement Procedure）
! V3 J; E2 Z9 i　　先给定一个可行途程，然后进行改善，一直到不能改善为止。有以下几种解法：
* ]; p4 C% c9 h$ g% z1 k/ l% w　　1）K-Opt(2/3 Opt)：把尚未加入路径的K条节线暂时取代目前路径中K条节线，并计算其成本（或距离），如果成本降低（距离减少），则取代之，直到无法改善为止，K通常为2或3。
, e, R0 b7 h+ s/ v% R　　2）Or-Opt：在相同路径上相邻的需求点，将之和本身或其它路径交换且仍保持路径方向性，并计算其成本（或距离），如果成本降低（距离减少），则取代之，直到无法改善为止。
　　3、合成启发法（Composite Procedure）
; k) Y. X  V4 S4 C1 _6 l8 t　　先由途程建构法产生起始途程，然后再使用途程改善法去寻求最佳解，又称为两段解法（two phase method）。有以下几种解法：
　　1）起始解求解+2-Opt：以途程建构法建立一个起始的解，再用2-Opt的方式改善途程，直到不能改善为止。
　　2）起始解求解+3-Opt：以途程建构法建立一个起始的解，再用3-Opt的方式改善途程，直到不能改善为止。

wangdao_1

旅行商问题（Traveling Saleman Problem，TSP）又译为旅行推销员问题、货郎担问题，简称为TSP问题，是最基本的路线问题，该问题是在寻求单一旅行者由起点出发，通过所有给定的需求点之后，最后再回到原点的最小路径成本。最早的旅行商问题的数学规划是由Dantzig（1959）等人提出。
; L8 d( J8 U/ t( A3 i7 t　　TSP问题在物流中的描述是对应一个物流配送公司，欲将n个客户的订货沿最短路线全部送到。如何确定最短路线。
* g$ ?! n3 u( e) F. e　　TSP问题最简单的求解方法是枚举法。它的解是**的、多局部极值的、趋于无穷大的复杂解的空间，搜索空间是n个点的所有排列的集合，大小为（n-1）。可以形象地把解空间看成是一个无穷大的丘陵地带，各山峰或山谷的高度即是问题的极值。求解TSP，则是在此不能穷尽的丘陵地带中攀登以达到山顶或谷底的过程。
" d1 P  H" d# h6 ^[编辑本段]旅行商问题的历史
# J- N/ y2 j7 @7 U9 a, l# q　　旅行商问题字面上的理解是：有一个推销员，要到n个城市推销商品，他要找出一个包含所有n个城市的具有最短路程的环路。
　　TSP的历史很久，最早的描述是1759年欧拉研究的骑士周游问题，即对于国际象棋棋盘中的64个方格，走访64个方格一次且仅一次，并且最终返回到起始点。
$ n6 m( [+ t9 @4 [! k. [5 p　　TSP由美国RAND公司于1948年引入，该公司的声誉以及线性规划这一新方法的出现使得TSP成为一个知名且流行的问题。
! f8 u( B* @' I8 Q7 R1 C[编辑本段]旅行商问题的解法
　　旅行推销员的问题，我们称之为巡行（Tour），此种问题属于NP-Complete的问题，所以旅行商问题大多集中在启发式解法。Bodin（1983）等人将旅行推销员问题的启发式解法分成三种：
9 e5 b& E1 D: H" A; g/ Y　　1、途程建构法（Tour Construction Procedures）
　　从距离矩阵中产生一个近似最佳解的途径，有以下几种解法：
　　1）最近邻点法（Nearest Neighbor Procedure）：一开始以寻找离场站最近的需求点为起始路线的第一个顾客，此后寻找离最后加入路线的顾客最近的需求点，直到最后。
* ^; i- @" v$ U) B　　2）节省法（Clark and Wright Saving）：以服务每一个节点为起始解，根据三角不等式两边之和大于第三边之性质，其起始状况为每服务一个顾客后便回场站，而后计算路线间合并节省量，将节省量以降序排序而依次合并路线，直到最后。
2 q% t! p- v3 f! s　　3）插入法（Insertion procedures）：如最近插入法、最省插入法、随意插入法、最远插入法、最大角度插入法等。
　　2、途程改善法（Tour Improvement Procedure）
　　先给定一个可行途程，然后进行改善，一直到不能改善为止。有以下几种解法：
　　1）K-Opt(2/3 Opt)：把尚未加入路径的K条节线暂时取代目前路径中K条节线，并计算其成本（或距离），如果成本降低（距离减少），则取代之，直到无法改善为止，K通常为2或3。
　　2）Or-Opt：在相同路径上相邻的需求点，将之和本身或其它路径交换且仍保持路径方向性，并计算其成本（或距离），如果成本降低（距离减少），则取代之，直到无法改善为止。
! y6 {# n7 B+ O- X7 G7 u* W　　3、合成启发法（Composite Procedure）
  b  ]1 w) s3 W　　先由途程建构法产生起始途程，然后再使用途程改善法去寻求最佳解，又称为两段解法（two phase method）。有以下几种解法：
　　1）起始解求解+2-Opt：以途程建构法建立一个起始的解，再用2-Opt的方式改善途程，直到不能改善为止。
　　2）起始解求解+3-Opt：以途程建构法建立一个起始的解，再用3-Opt的方式改善途程，直到不能改善为止。

wangdao_1

............................................................................................