旅行商问题数学建模

数学建模遗传算法例题数学建模中，遗传算法是一种基于进化思想的优化算法，可以应用于复杂的优化问题中。

本文将介绍一些遗传算法的例题，帮助读者更好地理解遗传算法的应用。

例题一：背包问题有一个体积为V的背包和n个物品，第i个物品的体积为vi，价值为wi。

求这个背包最多能装多少价值的物品。

遗传算法的解决步骤：1. 初始化种群：随机生成一定数量的个体作为初始种群。

2. 适应度函数：将每个个体代入适应度函数，计算其适应度值。

3. 选择：根据每个个体的适应度值，选择一定数量的个体进入下一代。

4. 交叉：对被选中的个体进行交叉操作，生成新的个体。

5. 变异：对新的个体进行变异操作，引入新的基因。

6. 重复以上步骤，直到符合终止条件。

在背包问题中，适应度函数可以定义为：背包中物品的总价值。

交叉操作可以选择单点交叉或多点交叉，变异操作可以选择随机变异或非随机变异。

例题二：旅行商问题有n个城市，旅行商需要依次经过这些城市，每个城市之间的距离已知。

求旅行商经过所有城市的最短路径。

遗传算法的解决步骤：1. 初始化种群：随机生成一定数量的个体作为初始种群，每个个体代表一种旅行路线。

2. 适应度函数：将每个个体代入适应度函数，计算其适应度值。

3. 选择：根据每个个体的适应度值，选择一定数量的个体进入下一代。

4. 交叉：对被选中的个体进行交叉操作，生成新的个体。

5. 变异：对新的个体进行变异操作，引入新的基因。

6. 重复以上步骤，直到符合终止条件。

在旅行商问题中，适应度函数可以定义为：旅行商经过所有城市的总距离。

交叉操作可以选择顺序交叉或部分映射交叉，变异操作可以选择交换或反转基因序列。

总结：遗传算法是一种强大的优化算法，可以应用于多种复杂的优化问题中。

在数学建模中，遗传算法的应用也越来越广泛。

本文介绍了背包问题和旅行商问题的遗传算法解决步骤，希望对读者有所帮助。

旅行售货员(TSP)，Hamilton回路的lingo程序方法一model:sets:city / 1..6/: u;! 定义6个城市;link( city, city):dist, ! 距离矩阵;x; !决策变量;endsetsn = @size( city);data: !距离矩阵;dist =0 2 100 4 100 22 0 8 100 4 100100 8 0 5 8 74 1005 06 100100 4 8 6 0 42 100 7 100 4 0 ;!这里可改为你要解决的问题的数据;enddata!目标函数;min = @sum( link: dist * x);@FOR( city( K):!进入城市K;@sum( city( I)| I #ne# K: x( I, K)) = 1;!离开城市K;@sum( city( J)| J #ne# K: x( K, J)) = 1;);!保证不出现子圈;@for(city(I)|I #gt# 1:@for( city( J)| J#gt#1 #and# I #ne# J:u(I)-u(J)+n*x(I,J)<=n-1););!限制u的范围以加速模型的求解，保证所加限制并不排除掉TSP问题的最优解;@for(city(I) : u(I)<=n-1 );@for( link: @bin( x));!定义X为0\1变量;end部分结果有：Global optimal solution found.Objective value: 26.00000Objective bound: 26.00000Infeasibilities: 0.000000Extended solver steps: 0Total solver iterations: 179V ariable V alue Reduced CostN 6.000000 0.000000U( 1) 5.000000 0.000000U( 2) 0.000000 0.000000U( 3) 3.000000 0.000000U( 4) 5.000000 0.000000U( 5) 1.000000 0.000000U( 6) 2.000000 0.000000注意，这里有两个u(1)=U(4)=5说明：（1）红色部分语句1）保证不会有某一边来回的情况假如有某(i,j)来回，则x(i,j)=x(j,i)=1,对这两个x(i,j)=x(j,i)=1分别用一次上述for语句，得到：u(i)-u(j)+n*x(i,j)<=n-1u(j)-u(i)+n*x(j,i)<=n-1将这两个不等式两边相加，则得到矛盾2n<=2(n-1)2）保证不出现子圈假如有某个子圈i->j->k->i产生，那么一定同时会有一个不包含起点1的子圈产生，所以不妨设子圈i->j->k->i不包含起点1，则有x(i,j)=x(j,k)=x(k,i)=1,但x(j,i)=x(k,j)=x(i,k)=0,对上述3个x(i,j)=x(j,k)=x(k,i)=1分别用三次上面的for语句得到：u(i)-u(j)+n*x(i,j)<=n-1u(j)-u(k)+n*x(j,k)<=n-1u(k)-u(i)+n*x(k,i)<=n-1将三个不等式相加，得到矛盾3n<=3(n-1)，所以可不能产生子圈。

资料范本本资料为word版本，可以直接编辑和打印，感谢您的下载旅行商问题数学建模地点：__________________时间：__________________说明：本资料适用于约定双方经过谈判，协商而共同承认，共同遵守的责任与义务，仅供参考，文档可直接下载或修改，不需要的部分可直接删除，使用时请详细阅读内容黄石理工学院数学建模大型作业2011—2012 学年第1学期目录一．摘要二．旅行问题问题描述符号说明模型设计建模求解模型分析三．建模过程及心得体会四．参考文件一．摘要本文是一个围绕旅行商问题和背包问题这两个经典问题的论文。

问题一，是一个依赖与每个城市去一次且仅去一次的路线确定问题，问题二类似于问题一。

问题三是一个依赖于可背重量限制的背包问题。

关键词：HAMILTON回路 LINGO 最优旅行路线 0-1模型二．旅行问题问题描述某人要在假期内从城市A出发，乘火车或飞机到城市B,C,D,E,F旅游购物。

他计划走遍这些城市各一次且仅一次，最后返回城市A。

已知城市间的路费数据见附表1，请你设计一条旅行路线使得他的总路费最少。

如果临行他因故只能去4个城市，该怎样修订旅行路线？在城市间旅游时他计划购买照相机，衣服，书籍，摄像机，渔具，白酒，食品，而受航空行李重量的限制以及个人体力所限，所买物品的总重量不能超过15kg，各种物品的价格见附表2.请你为他决策买哪些物品，使所买物品价值最大。

附表1：附表2模型设计首先给出一个定义：设v1,v2,......,vn是图G中的n个顶点，若有一条从某一顶点v1出发，经过各节点一次且仅一次，最后返回出发点v1的回路，则称此回路为HAMILTON回路。

问题1.分析：这个优化问题的目标是使旅行的总费用最少，要做的决策是如何设定旅行路线，决策受的约束条件：每个城市都必须去，但仅能去一次。

按题目所给，将决定变量，目标函数和约束条件用数学符号及式子表示出来，就可得一下模型。

走遍全中国方案的研究摘要本文通过对走遍中国各省会城市、直辖市和港澳台的最优路径选择问题进行分析，发现这是一个十分典型的旅行商问题（Traveling Salseman Problem ），即寻找一条遍历n 个城市（在本文中为34个城市）的最短路径。

我们搜索了这34个城市的经纬度和部分列车、航班时刻表等各方面信息，综合省钱、省时、方便等因素，进一步深入并细化，从而得到判断各订票方案的准则。

针对问题一，我们利用欧几里得平面知识，由公式0002901800290A B x R A y R ππ+⎧=⋅⎪⎪⎨-⎪=⎪⎩将该34个城市的经纬度转化为平面直角坐标，从而将其简化成二维平面问题。

目前，解旅行商问题（tsp 问题）的方法有许多种，本文采用了较为先进的遗传算法。

遗传算法是目前解决组合优化问题最有效的工具之一，本文介绍了遗传算法的基本原理，讨论了遗传算法中的有关遗传算子设计等方面的技术。

由于该算法在搜索空间中同时考虑了许多点，这样就减少了收敛于局部极小的可能，也增加了处理的并行性。

同时，我们利用MATLAB 软件编辑了相关程序，计算出了遍历该34个城市的最短路径，其路径长度为14661km 。

对于问题二，在只考虑旅行路线最经济的前提下，结合第一问得出的最优路径，我们收集了这34个城市的列车和航班时刻表等信息，从而找出最经济的订票方案，并得其花费为11426元。

针对问题三，在综合考虑省时、省钱、方便等诸多因素的前提下制定订票方案的评价准则，我们运用了层次分析法对其进行研究。

根据对旅行过程中省时，省钱及方便的偏重程度，我们相应地给出了判断矩阵111571513731⎡⎤⎢⎥⎢⎥⎢⎥=⎢⎥⎢⎥⎢⎥⎢⎥⎣⎦A ，然后对其进行一致性检验，发现其不一致程度在容许范围内。

因此我们利用其最大特征根max λ对应的特征向量w 作为比较因素的权向量，并得到以下评价表达式：12120.0740.2830.643*(0.8330.167)C x x x x =+++。

3 旅行商问题3.1 旅行商问题概述3.1.1 旅行商问题的定义和数学模型① 定义旅行商问题(Traveling Salesman Problem ，简记TSP)是组合数学中一个古老而又困难的问题，它易于描述但至今尚未彻底解决，现己归入所谓的NP 完全问题类，经典提法为：有一货物推销员要去若干个城市推销货物，从城市1出发，经其余各城市一次，然后回到城市1，问选择怎样的行走路线，才能使总行程最短（各城市间距离为己知）。

该问题在图论的意义下就是所谓的最小Hamilton 圈问题，由于在许多领域中都有着广泛的应用，因而寻找其实际而有效的算法就显得颇为重要了。

遗憾的是，计算复杂性理论给予我们的结论却是，这种可能性尚属未知。

若设城市数目为n 时，那么组合路径数则为(n-1)!。

很显然，当城市数目不多时要找到最短距离的路线并不难，但随着城市数目的不断增大，组合路线数将呈指数级数规律急剧增长，以至达到无法计算的地步，这就是所谓的“组合爆炸问题”。

假设现在城市的数目增为20个，组合路径数则为(20-1)! ，如此庞大的组合数目，若计算机以每秒检索1000万条路线的速度计算，也需要花上386年的时间。

尽管现在计算机的计算速度大大提高，而且已有一些指数级的算法可精确地求解旅行商问题，但随着它们在大规模问题上的组合爆炸，人们退而求其次，转向寻找近似算法或启发式算法，经过几十年的努力，取得了一定的进展。

② 数学模型设(,)G V E =为赋权图，{1,2,}V n ="为顶点集，E 为边集，各顶点间距离为ij c ，已知(0,,,)ij ij c c i j V >=+∞∈，并设则旅行商问题的数学模型可写成如下的线性规划形式：ij ij i jMinZ c x ≠=∑1,(,)0,ij i j x ⎧=⎨⎩边在最优路线上其它,1,1,.1,{0,1},ij j i ij i jij i j S ij x i V x j V s t x K K V x i j V ≠≠∈⎧=∈⎪⎪=∈⎪⎨⎪≤−⊂⎪⎪∈∈⎩∑∑∑这里，K 为V 的所有非空子集，K 为集合K 中所含图G 的顶点个数。

多旅行商问题研究综述一、问题定义与数学模型多旅行商问题（Multiple Traveling Salesman Problem，MTSP）是旅行商问题（Traveling Salesman Problem，TSP）的扩展，是组合优化领域中的经典问题之一。

在MTSP中，有多个旅行商需要遍历各自的销售区域，并在有限的时间内完成各自的旅程。

每个旅行商的旅程起点和终点固定，且每个旅行商的路径不能交叉，也不能重复。

MTSP的目标是在满足约束条件下，最小化所有旅行商行走的总距离。

数学模型通常采用整数规划或图论表示。

对于一个具有n个顶点的完全图，每个顶点代表一个城市或客户，边代表城市之间的道路。

MTSP可以转化为在图中寻找n个哈密尔顿回路（Hamiltonian Cycle）的问题。

由于图论表示方法具有一定的局限性，近年来研究者们提出了更复杂的数学模型，如超图、混合图等。

二、求解方法与算法设计MTSP是一个NP-hard问题，求解非常困难。

因此，研究者们提出了许多近似算法和启发式方法。

这些方法大致可以分为两类：基于贪婪策略的方法和基于元启发式的方法。

1. 基于贪婪策略的方法：这类方法通常采用局部搜索策略，从当前解出发，通过不断地进行局部搜索和改进来寻找最优解。

代表性的方法包括：最小生成树法、分支定界法、回溯法等。

2. 基于元启发式的方法：这类方法采用一些启发式策略来指导搜索过程，如遗传算法、模拟退火、粒子群优化等。

这些方法能够在较短的时间内找到可接受的解，但并不能保证找到全局最优解。

此外，近年来还出现了一些新的求解方法，如深度学习、强化学习等人工智能算法也被应用于MTSP的求解。

这些方法通常需要大量的数据和计算资源，但可以处理更大规模和更复杂的MTSP问题。

三、特定场景下的多旅行商问题随着应用领域的不断扩展，MTSP已经应用于许多特定场景中，如供应链管理、物流配送、城市规划等。

在这些场景中，MTSP需要考虑更多的实际因素和约束条件，如车辆路径限制、时间窗限制等。

运用建模方法求解与旅游有关的数学问题近年，我国旅游事业蓬勃发展，从而以旅游为背景的各类数学问题应运而生．本文以近几年来的部分中考试题为例，分析与旅游有关的数学问题的建模类型．一、用方程( 或方程组) 建模的旅游问题例1为吸引市民组团去风景区旅游，观光旅行社推出了如下收费标准:如果人数不超过15人，人均旅游费用500元，如果人数超过15人，每增加1人，人均旅游费用降低10元，但人均旅游费用不得低于320 元，某单位员工去风景区旅游，共支付给旅行社旅游费用10500元，请问该单位这次共有多少员工去风景区旅游?解设人数为x，则x［500-10( x-15) ］= 10500，解得x1 = 30，x2 = 35．因为人均旅游费用不得低320元，所以x = 30( 人) ．答: ( 略．)例2 2010 年国庆长假期间，某旅行社接待“世博一日游” 的游客和“世博三日游” 的旅客旅客共1600人，收取旅游费129万元，其中一日游每人收费150元，三日游每人收1200元，该旅行社接待的一日游和三日游的游客各是多少人?解设一日游的游客为x人，三日游的游客为y人，可列方程组: x + y = 1600，150x + 1200y = 1290000．解得x = 600(人) ，y = 1000(人) ．答: (略)注用方程(或方程组)建模的数学问题，解题的关键是抓住题中的相等关系，从而建立方程或方程组解决问题．现实生活中还有其他很多类似问题，例如: 储蓄利息、打折促销、工程问题、行程问题、浓度配比问题等，都可以用方程或方程组模型来求解二、用不等式( 或不等式组) 建模的旅游问题例3某旅社某天有空10间，当天接待了一个旅游团，当每个房间住3人时，有一个房间住宿的情况是不空也不满，若旅游团的人数为偶数，求旅游团有多少人?解设旅游团有x 人，有一个房间不空也不满，则9间是满的，9 × 3 人外，还有x- 9 ×3 人．不空也不满人数就是大于0小于3 ，∴0＜x-27＜3 ，∴27＜x＜30．∵x 是偶数，∴x = 28．即旅游团有28 人．注用不等式或不等式组建模的数学问题，解决问题的关键是抓住题中数量之间的不等关系，列出不等式或不等式组建立模型．现实生活中还有其他很多类似问题，例如: 人员分配、“最大”“最小” 问题、价格范围等，通常用不等式或不等式组的模型来求解．三、用函数建模的旅游问题例4 暑假期间，小明和父母一起开车到距家200千米的景点旅游．出发前，汽车油箱内储油45升; 当行驶150千米时，发现油箱剩余油量为30升．(1) 已知油箱内余油y( 升) 是行驶路程x(千米)的一次函数，求y与x的函数关系式;(2) 当油箱中余油量少于3升时，汽车将自动报警．如果往返途中不加油，他们能否在汽车报警前回到家?请说明理由．解(1) 依题意，设y = 45-kx由已知，得k = 45-30150= 0.1．∴y = 45-0. 1 x．(2)由3 = 45- 0.1 x，解得x = 420( 千米) ．即在报警前可以用的42 升油最多可以行使420千米，往返才400 千米，可以在报警前回家．例5 某单位计划10月份组织员工到A地旅游，人数估计在10 ~25 人之间．甲、乙两家旅行社的服务质量相同，且报价均为200元．该单位上门联系时，甲社表示可给予每位游客七五折优惠; 乙社表示可先免去一位游客的旅游费用，其余游客八折优惠．设该单位去A 地的旅游人数为x，若选择甲社，则所需总费用为y1 元; 若选择乙社，则所需总费用为y2元．(1 ) 分别求出y1、y2与x的函数关系式;(2) 在同一平面直角坐标系中，画出上述两个函数的图象;(3 ) 求出两条直线的交点坐标，并说明它的实际意义．解(1 ) y1 = 200x × 75 % = 150x;y2= 200( x-1 ) × 80% = 160x-160．(2) 过(0，0)，(4，600) 画直线y1;过(1，0)，(8，1120)画直线y2 (图略) ．(3 ) 由图象可知，当人数x = 16时，选择甲、乙两家旅行社所需总费用相同．注用函数建模的数学问题，解题的关键是找出题中数量之间的函数关系，确定函数关系式，再根据函数的性质以及函数图像的性质来求解．现实生活中还有很多类似问题，如: 最佳方案、最小成本、用料造价等，都可以用函数模型来求解．四、与概率组合有关的旅游问题6 某旅游团计划在3天内旅游3个景点A、B、C，每天只能浏览其中的1个景点．如果采取抽签的方法决定浏览顺序，那么(1) 共有几种不同的安排方案?(2) 第1天浏览景点A，第2天浏览景点B，第3天浏览景点C 的概率是多少?(3) 第1天浏览景点A 的概率是多少?解(1) 6种，第一天有三个选择，第二天两个选择，第三天没有选择;(2) 100%，因为第三天没有选择;(3 ) 1 /3 ．例7 某旅游团要从8个风景点中选2个作为当天的旅游地，求分别满足下列条件的选法的种数:(1) 甲乙风景点中至少选一个;(2) 甲乙风景点中至多选一个;(3) 甲乙两个风景点中必须选一个，而且只能选一个．除上述外，还有一些旅游路线的设计和测量、航海方位、工程定位等问题，也可以建立相应的数学模型求解，在此就不一一列举．初中数学新课程标准对数学建模提出了明确的要求，教材采用“问题情境———建立模型———解释、应用与拓展” 的模式展开，通过对问题的探究、学习，让学生真正体验到数学来源于生活，用于生活的过程．。

走遍全中国——基于蚂蚁算法的解决方案摘要：本文是解决一个旅行商问题（TSP ），这里我们基于蚂蚁算法，对“走遍全国”这一具体问题建立了相应的TSP 数学模型，并且基于Matlab 软件编写了相应的程序，从而找出“走遍全中国”中34个城市的最短路。

对于第一问：由已知的地理位置（经纬度）设计并计算出了最短路旅行方案：哈尔滨—长春—沈阳—上海—杭州—南京—合肥—武汉—长沙—南昌—福州—台北—香港—澳门—广州—海口—南宁—贵州—重庆—成都—昆明—拉萨—乌鲁木齐—西宁—兰州—银川—西安—郑州—济南—天津—北京—石家庄—太原—呼和浩特—哈尔滨。

对于第二、三问：考虑到实际旅行线路的制约，本问基于上问设计的最短线路，对特定两城市之间加以分析，为此本文制定了相应的乘车规则，分别就省钱、省时、方便建立了数学模型。

第四问：本文应用程序运行时间的增长率，来刻画该算法的时间复杂性，即n p ∆=δ，从而通过对比说明了蚂蚁算法的可行性。

第五问：蚂蚁算法当接近最优解时收敛速度快，而开始时收敛速度很慢。

所以想到使蚂蚁算法去和其他一些开始收敛速度快的算法（如粒子群算法）结合，这样使蚂蚁算法得到优化。

关键词：蚂蚁算法 旅行商问题1 问题分析：由于人们在旅游方式、时间安排、经济状况等诸多因素的不同导致了，对于旅游线路的设计与选取变得更加迫切。

对于旅行社而言，不同的线路设计直接影响到旅行社的发展。

而对于旅行者而言，不同的路线使我们更能充分利用现有的经济、时间等来安排自己的旅行路线。

对于模型的建立本文将旅行者分为经济型、省时和方便三方面建立了模型。

在设计最短路问题当中，本文仅从我国省会的地理位置（经纬度）方面加以设计，即不考虑实际当中的铁路、航空里程。

假设旅行者周先生能通过互联网订到从A 市到B 市的火车票（飞机票），那么在对于解决第二问的关键就转变为对第一问结果在现实背景下的“修订”。

本文所采用的算法为ACO 算法，其多样性和正反馈的特点不仅保证了系统的多样性，而且保证了优良性能得到强化，2 符号说明n 城市规模，即城市的数目；n ∆ 城市数目的增量；t某个时刻；t ∆ 乘坐火车时间；δ当城市数n 增大时，运行时间的增长量；p 算法执行的时间增长率；ji x x - 某两城市间距离；η 选取交通工具的距离参数。

数学建模经典问题
数学建模是一种将现实问题转化为数学问题，并通过数学方法求解的过程。

经典的数学建模问题有很多，以下列举几个典型的例子。

1. 集装箱装载问题：如何在给定的集装箱内，最大化货物的装
载量？这个问题可以转化为一个优化问题，通过线性规划等方法求解。

2. 旅行商问题：如何在给定的一组城市中，找到一条遍历所有
城市且总路程最短的路径？这个问题可以通过遗传算法等方法求解。

3. 贪心算法：贪心算法是一种基于贪心策略的算法，它通常用
于优化问题。

比如，假设有一组活动，每个活动都有一个开始时间和结束时间，如何在不发生冲突的情况下，安排尽可能多的活动？这个问题可以通过贪心算法求解。

4. 马踏棋盘问题：如何让一匹马在棋盘上走遍所有格子，且每
个格子只走一次？这个问题可以通过回溯算法求解。

5. 神经网络：神经网络是一种模仿人脑神经元结构和功能的计
算模型。

它可以用于分类、回归、聚类等问题。

这些经典的数学建模问题都有着广泛的应用价值，它们不仅给我们提供了解决实际问题的方法，也为我们深入理解数学方法的应用提供了宝贵的经验和启示。

- 1 -。

以点0表示旅行商的出发城市，称为源点，点1,2,,l 表示m 个旅行商需访问的城市。

MTSP 问题的数学模型可以表示为： 令10ij x ⎧=⎨⎩弧(i,j)在线路上 弧(i,j)不在线路上模型表示如下：0000min 10,1,,10,1,,()01,0,1,,R R ij iji j R ij i R ij j ij ij z d x x j R x i R X x Sx i j R====⎧=⎪⎪⎪==⎪⎪⎨⎪==⎪⎪=∈⎪⎪==⎩∑∑∑∑或 式中：1;ij R m l d =+-为增广费用。

若用(,1,,)ij c i j l =表示旅行商经过对应弧度(,)i j 所花的费用，如时间、距离、花费等，那么给ij c 增加(1)m -行和(1)m -列，每一新的行或列是ij c 的最后一行或列的复制，增广矩阵的其他元素为无穷大，由此构成了增广费用ij d 。

一般MTSP 中，旅行商访问l 个城市必须满足以下2个条件。

条件1：从指定城市出发，对其他所有城市严格访问一次后返回原出发城市。

条件2：一条有效路径严格由m 条非平凡子路径(Nontrivial Subtours)组成。

所谓非平凡子路径是指该路径中除出发城市外，至少访问一个其他城市。

用遗传算法求解MTSP ，可通过附加虚拟城市的方法把MTSP 转化为TSP 。

将另外(1)m -个旅行商理解为(1)m -个虚拟城市，这(1)m -个虚拟城市标号分别为1,2,,1,l l l m +++-，它们与城市0具有相同的坐标(即相同位置)。

在旅行商访问路径中出现的每一个虚拟城市均表示旅行商返回出发城市，从而组成一个回路。

每个回路表示MTSP 中一个旅行商的旅行路径。

需注意的是，为了避免出现平凡子路径，必须假设(1)m -个虚拟城市到原点的距离为00(,0,1,,1),ij c M i j l l m M ==++-为一无穷大的正数（即永远不能达到），到其他各点距离与原点一致，这样遗传算法就不会出现0-0-0的途径。

安徽工程大学数学建模课程设计论文C 最佳旅游路线设计姓名：李阳班级：数学112学号：3110801221指导老师：周金明成绩：完成日期：2013年7月3日q摘要旅行商问题，即TSP问题（Traveling Salesman Problem）是数学领域中著名问题之一。

假设有一个旅行商人要拜访N个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。

路径的选择目标是要求得的路径路程为所有路径之中的最小值。

其实际问题的约束条件复杂，目标函数多样，问题的特殊性使其甚至不具有最优算法。

本文则运用多种方法多角度对这一问题进行了建模及求解。

第一问从传统的图论解法开始，通过无向图的Hamilton回路建模，使用Dijkstra的改进算法将问题转化为单目标的非线性规划函数并得出了单一旅行商的问题。

第二、三问仍从图论入手，基于最小生成树用两种方法共同建立出模型。

第四问的求解跳出传统的算法框架，借用经济学中消费者效用的概念从旅行者的角度出发，先运用模糊数学的层次分析法（AHP）将复杂的满意度的主观评价问题定量分析，得出比较分散的景点选择域。

考虑到游客在消费博弈中的自组织行为和政府规划的管制效应，建立局部反馈的RBF神经网络模型通过迭代对景点选区进行优化。

最后运用Huffman 二叉树对景点进行路性组织，得到适合于不同品味人群的五条路线，同时还分散了游客对环境和资源的压力。

模型的建立过程中从浅入深，虽然还存在很大改进余度，但已逐步摒弃了传统TSP问题中对游客刚性的、理性的、线性的行为假设，还原了社会生活中柔性的、非线性，非理想的行为人模式，具有很强的现实价值和拓展前景。

关键词：TSP问题多目标动态优化最短路径 Hamilton回路最小生成树主观评价层次分析法 RBF神经网络最优二叉树非线性一.问题的重述王先生夫妇是华东某高校的年轻教师，打算暑假中到新疆旅游。

受文学作品的影响，天池、达坂城、吐鲁番、楼兰古城、伊犁都是他们十分向往的地方，新疆的其他地方对他们也有很大的吸引力。

四类基本模型1 优化模型1.1 数学规划模型线性规划、整数线性规划、非线性规划、多目标规划、动态规划。

1.2 微分方程组模型阻滞增长模型、SARS 传播模型。

1.3 图论与网络优化问题最短路径问题、网络最大流问题、最小费用最大流问题、最小生成树问题(MST)、旅行商问题(TSP)、图的着色问题。

1.4 概率模型决策模型、随机存储模型、随机人口模型、报童问题、Markov 链模型。

1.5 组合优化经典问题● 多维背包问题(MKP)背包问题：n 个物品，对物品i ，体积为i w ，背包容量为W 。

如何将尽可能多的物品装入背包。

多维背包问题：n 个物品，对物品i ，价值为i p ，体积为i w ，背包容量为W 。

如何选取物品装入背包，是背包中物品的总价值最大。

多维背包问题在实际中的应用有：资源分配、货物装载和存储分配等问题。

该问题属于NP 难问题。

● 二维指派问题(QAP)工作指派问题：n 个工作可以由n 个工人分别完成。

工人i 完成工作j 的时间为ij d 。

如何安排使总工作时间最小。

二维指派问题（常以机器布局问题为例）：n 台机器要布置在n 个地方，机器i 与k 之间的物流量为ik f ，位置j 与l 之间的距离为jl d ，如何布置使费用最小。

二维指派问题在实际中的应用有：校园建筑物的布局、医院科室的安排、成组技术中加工中心的组成问题等。

●旅行商问题(TSP)旅行商问题：有n个城市，城市i与j之间的距离为d，找一条经过n个城ij市的巡回（每个城市经过且只经过一次，最后回到出发点），使得总路程最小。

●车辆路径问题(VRP)车辆路径问题（也称车辆计划）：已知n个客户的位置坐标和货物需求，在可供使用车辆数量及运载能力条件的约束下，每辆车都从起点出发，完成若干客户点的运送任务后再回到起点，要求以最少的车辆数、最小的车辆总行程完成货物的派送任务。

TSP问题是VRP问题的特例。

●车间作业调度问题(JSP)车间调度问题：存在j个工作和m台机器，每个工作由一系列操作组成，操作的执行次序遵循严格的串行顺序，在特定的时间每个操作需要一台特定的机器完成，每台机器在同一时刻不能同时完成不同的工作，同一时刻同一工作的各个操作不能并发执行。