学文网一、引言
随着人们生活水平的提高，旅游已经成为人们生活中的重要活动，某省外旅游爱好者打算十一自驾游山东，笔者推荐了山东济南、青岛、淄博、泰安、威海、日照、蓬莱、曲阜8个特色旅游城市城市，他打算游览完这8个城市，请设计一条合适的旅游线路，使得他的交通费用最少。旅游线路优化问题一个复杂的系统问题，而***论中的方法则给我们提供了解决这一问题的新思路。该问题属于旅行商问题，我们考虑运用改良圈算法来解决此问题。
二、问题分析
该本经给出了8个城市，经过查询，我们得到了各个城市间的里程，要求设计一条最优路线，要使得交通费最少，即油耗最少，那么旅游里程数应该最少。我们假设出发地为济南，经过每个城市后在回到济南，这属于旅行商问题（TSP），最简易的解决方法是通过穷举寻找最短路径，但算法复杂度一般取决于项点个数，这样将导致随着顶点的增大，复杂度成指数形式增长，该方法几乎不可能实现，目前还没有解决TSP问题的有效算法。目前的解法主要有遗传算法、最小生成树、模拟退火、蚁群法、局部搜索、神经网络等陋”等。由于数据较少，我们考虑运用改良圈算法解决。
三、模型准备
（一）TSP问题的基本理论。
恰好包含每个顶点的圈称为Hamilton圈。
某旅行商欲往n个城市推销货物，从某个城市出发，沿途经过各个城市一次后返回出发城市，要确定一条行走的路线，使得总路径最短。这个问题称为旅行商问题（TSP）。用***论的术语说，就是在一个赋权完全***中，找出一个有最小权的Hamilton 圈，即最优圈。改良圈算法是求一个H圈，然后适当修改以得到具有较小权的另一个H圈。设初始圈。
C《VV…VV。
（1）对于1？茳i？茳j？茳n构造新的Hamilton圈：
C《VV…VVVV…VVV…VV
它是由C中删去的边和添加边和而得到的。若
W（VV）W（VV）？茳W（VV）W（VV），则以C代替C，C即为C的改良圈。
（2）转（1），直至无法改进，停止。
（二） 基本假设。
（1）假设出发地位济南，且自驾车走高速（数据均为高速路），不会出现堵车绕路；
（2）假定现在油价7.5元/升，每升油能供汽车行驶16km；
（3）忽略高速路收费情况及在各大城市景区间的驾车情况，只考虑城市到城市的距离。
（三）符号说明。
符号 含义
i，j，k（1Ci，j，kC8） 旅游的8个城市
A（i） 第i个城市
D（i，j） 城市与城市间的里程数
F （i，j） 距第个城市最近的城市是第个城市
从第i个城市和第j个城市之间走过
没有走过
目标函数为 Min
四、建立模型
下面为8个城市之间的里程数据：
济南 济南
青岛 390 青岛
淄博 110 280 淄博
泰安 80 381 140 泰安
威海 549 280 439 512 威海
日照 365 188 280 292 412 日照
蓬莱 421 207 311 490 151 333 蓬莱
曲阜 150 307 210 70 630 289 550 曲阜
临接矩阵：
建立模型如下：
（1）以济南为起点，找一条路再次回到济南，构成一条回路；
（2）将济南开始到达的第一个城市用离济南最近的城市替换；
（3）从第二个城市开始，不断按照2）的做法进行替换，直到回路将整个回路替换，找到最短线路；
五、模型求解
利用lingo，代码如下：
sets：
stops/1，2，3，4，5，6，7，8/：A；
link（stops，stops）：d，f；
endsets
data：
d =0 390 110 80 549 365 421 150
390 0 280 381 280 188 207 307
110 280 0 140 439 280 311 210
80 381 140 0 512 292 490 70
549 280 439 512 0 412 151 630
365 188 280 292 412 0 333 289
421 207 311 490 151 333 0 550
150 307 210 70 630 289 550 0；
enddata
n = @size（stops）；
min = @sum（link： d * f）；
@for（stops（k）：
@sum（stops（i）|i #ne# k： f（ i，k）） = 1；
@sum（stops（j）|j #ne# k： f（ k， j））= 1；
A（j） >= A（k） + f（k， j） - （n - 2） * （1 - f（ k， j）） + （n - 3） * f（j，k））；）；
@for（link： @bin（f））；
@for（stops（k）|k #GT# 1：
A（k）
A（k） >= 1 + （n - 2） * f（k， 1））；
End
运行程序，运行结果略，根据结果，我们得到的线路为：1-4-8-6-2-5-7-3-1。
即：济南-泰安-曲阜-日照-青岛-威海-蓬莱-淄博-济南，总路程1479km。所以耗油为1479km/（16km/L） =92.4375L，花费金额为92.4375*7.5=693.28元。
六、模型的优缺点及推广
该旅游路线的设计模型，我们对其进行了适当的假设，从而将其转化为***论上的TSP问题求解，用lingo求解，大大简化了计算过程。但当数据较复杂时，改良圈算法得到的不一定是最优解，为了得到更高的精确度，可以选择不同的初始圈，重复进行几次算法，以求得较精确的结果。该模型我们忽略多种情况，现实中也可能出现各种状况，所以模型还是有一定的局限性，但是算法却具有一定的推广性，可以将其推广到其他背景的线路设计问题上去。
（备注：中国海洋大学SRDP项目：山东旅游线路优化算法研究）
参考文献：
[1]Reinhard Diestel.***论【M】.北京：高等教育出版社，2013.1
[2]孙惠泉.***论及其应用[M].北京：科学出版社，2004.9.
[3]肖位枢.***论及其算法[M].北京：航空工业出版社，1993.7.
[4]谢金星，薛毅.优化建模与LINGO/LINGO软件[M].北京：清华大学出版社，2005.4.