基于旅行商回路模型对全国5A级景点的规划

朱桂玲 刘静颐 郑锦龙

一、引言

旅游正在成为全球经济发展的重要动力之一，它加速国际资金流转，创造高效率消费行为模式等［1］。随着经济的快速发展，越来越多的人积极参与旅游活动。所以，为旅游者到全国201个5A级景点参观提供旅游规划是非常有必要的。

二、问题提出

假设一旅游爱好者想游遍全国201个5A级景点，请设计合适的方法，使游客在最短的时间内游尽可能多的景点，并通过建立数学模型解决下面问题:以该游客的常住地在西安市为例，规划旅游线路，试确定游遍201个5A级景区至少需要几年?给出每一次旅游的具体行程。具体的行车线路和行车时间等相关信息可以从2015年全国研究生数学建模竞赛F题中获得。

三、名词、符号说明及基本假设

3.1 名词和符号说明

w表示每条路线总的行驶路程;cji表示:若xij=1，则表示从i景点去j景点，否则xij=0;rij表示从i景点去j景点之间的距离;tij表示从i景点去j景点之间所需要的时间;tij表示游客在i景点的最佳逗留时间。

3.2 模型的基本假设

(1)假设旅游爱好者每年外出旅游时间不超过30天，每年外出旅游的次数不超过4次，每次旅游的时间不超过15天;

(2)每一种旅游路线均从常住城市出发然后回到常住城市;

(3)假设汽车速度恒定，路程与旅途所用的时间成正比。

四、模型的建立与求解

首先，本文通过层次聚类法，根据2015年全国研究生数学建模竞赛F题附件3给出的数据，以陕西西安为中心，对其他各省按距离由近及远进行聚类，并借助R软件得到各省的层次聚类分析图(略)。通过层次聚类分析图，我们可将31个省份分为华北、东北、华东、华中、华南、西南和西北共7组(表4-1)。

表4-131 个省距离西安分组表(单位:公里)

按照表4-1的分组情况，首先下文给出了求解最佳路径的一般方法，然后将各组内的标号数带进去，得出在各组内每次出行的最佳路径。最后为了下面表达方便，本文又将各组内的所有景点进行了编号。

4.1 最佳旅游路线模型的基本思想

把每个景点看作图中的一个节点，每两个景点之间的公路看作对应图中节点间的边，各条公路看作对应边上的权，则所有景点之间的公路网就转化为加权网络图G，游客游遍所有景点的最佳旅游线路问题就转化为在给定的加权网络图中，寻找从给定点出发，行遍所有顶点再回到原点，使得总权最小，此即最佳旅行商回路问题［2］。

4.2 数学规划模型与求解

首先确定决策变量，用xij表示游客从景点i到景点j，引入0-1变量。令

然后把行走路程作为目标函数，约束条件为每个景点只经过一次，可建立如下模型:

对此模型的求解，可利用MATLAB［3］对其编程求解，求解得到权和最小的每次出行的具体旅游路线。

首先给第一组至第七组的景点进行了编号，其次借助画图软件画出从第一组至第七组之间各组内的所有景点的大致地里位置分布图，为了更好区分景点，对每个省内的景点都用同一种颜色进行了标记。

图4-2 第一组5A级景点地理位置分布图

注:图4-2中的1，2，….25代表第一组5A级景点的编号，利用同样的编号规则，对第二、三、四、五、六、七组所有5A景点进行编号。同样用画图软件可画出第二、三、四、五、六、七组所有5A景点的地理位置分布图就不一一列举。

其次，本文借助MATLAB软件编程，将每一次路线的景点数带入(4-2-1)式，得出了每一次外出旅游的最佳路线如下文所示:

第一组:陕西-甘肃-宁夏-新疆-青海-重庆

路线1:陕西西安-4-2-宁夏银川-14-11-13-12-新疆乌鲁木齐-18-24-陕西西安-6-陕西西安(时间=1+1+1+2.5+3+1+1.5+3.5+0.5=15 天);

路线2:陕西西安-新疆乌鲁木齐-23-21-17-19-20-25-22-陕西西安(时间 =3.5+1+6.5+3.5=14.5 天);

路线3:陕西西安-甘肃兰州-7-8-9-10-青海-15-16-重庆-23-28-25- 陕西西安(时间 =1+1+3+0.5+1+1.5+1.5+1+3.5+1=15天)

第二组:四川-贵州-云南-西藏

路线4:陕西西安-重庆-27-26-24-四川成都-6-5-7-1-2-4-9-8-10-3 陕西西安(时间 =1+2.5+1+1+8+1=14.5 天);

路线5:陕西西安-云南昆明-19-15-18-17-16-20-贵州贵阳-13-12-11-14—陕西西安(时间 =2+1+4.5+1.5+1+3+1.5=14.5 天);

路线6:陕西西安-西藏拉萨-21-22-陕西西安(时间=4+1+1+4=10天);

第三组:广西-广东-海南

路线7:陕西西安-广东广州-7-9-6-8-14-12-11-10-海南海口-18-19-17-15-16-陕西西安(时间=2.5+1+4+1+1+2.5+3=15天);

路线8:陕西西安-广东广州-5-13-广西南宁-4-1-2-3—陕西西安(时间 =2.5+1+2+1+1+3+2.5=13 天);

第四组:河南-湖南-湖北

路线9:陕西西安-湖南长沙-25-26-24-28-23-27-22-河南郑州6-4-3-9-2-陕西西安(时间=1.5+1+5+1+1+4.5+1=15天);

路线10:陕西西安-河南郑州-1-5-7-8-10-湖北武汉-14-16-19-12-13-17-21- 陕西西安(时间 =1+4.5+1+1+6.5+1=15天);

第五组:山东-安徽-江苏-上海-浙江-江西-福建

路线11:陕西西安-湖北武汉-15-安徽合肥-16-14-12-17-13-10-11-15- 陕西西安(时间 =1+0.5+0.5+1+7+1.5=11.5天);

路线12:陕西西安-江西南昌-52-57-5-54-55-58-53-福建福州-60-61-陕西西安(时间=1.5+1+6+1+1+2+2.5=15天);

路线13:陕西西安-福建福州-62-64-59-66-65-63-浙江杭州-44-51-40-48-43-50-46-41-49-陕西西安(时间=2.5+5+1+1+5.5+2=15);

路线14:陕西西安-浙江杭州-45-42-47-上海-38-37-39-江苏南京-24-35-20-26-30-28—29-19-陕西西安(时=2+2+0.5+1++2+0.5+1+4.5+1.5=15 天);

路线15:陕西西安-江苏南京-23+18+33+27+25+31+21+22+32+34+24-山东济南-8-6-5-4陕西西安(时间=1.5+7.5+1+1+2.5+1.5=15 天);

第六组:辽宁-吉林-黑龙江

路线16:陕西西安-山东济南-2-1-9-7-3-辽宁沈阳-1-3-2-4-(时间 =1.5+3.5+1.5+1+2.5+2.5=12.5 天);

路线17:陕西西安-吉林长春-6-7-8-5-黑龙江哈尔滨-9-11-12-10-13-陕西西安(时间 =3+1+2.5+0.5+1+3+3.5=14.5天);

第七组:北京-天津-河北-山西-内蒙古

路线18:陕西西安-山西太原-19-17-20-18-16-15-河北石家庄 -14-13-10-12-11-陕西西安(时间 =1+1+3.5+0.5+1+6.5+1=14.5 天);

路线19:陕西西安—-天津-8-9-北京-6-7-5-4-3-1-2-内蒙古呼和浩特 -22-21-陕西(时间 =1.5+1+1.5+0.5+1+3.5+0.5+1+1.5+1.5=13.5 天)。

综上所述可知，19条外出旅游路线游完了201个5A级景点共需要9年半。又因本文在模型求解时没有考虑省内景点与景点的距离，因此可大致估算景点与景点之间的时间为1年半，所以问题一最终需要时间至少为11年。(作者单位:云南大学)

［1］教育部学位与研究生教育发展中心.2015全国研究生数学建模竞赛F题［OL］.全国研究生数学建模网站.2015

［2］冯爱芬.最佳旅游线路的设计与算法［J］.

［3］张贤明.MATLAB语言及应用案例［M］.东南大学出版社。2010.