最佳旅游路线设计
摘要
本论文主要考虑通过合理的假设将问题简化为图论问题，使用floyed算法得到任意两点间的最短路径后，带入各景点间的距离、时间、门票等信息后，视为0-1线性规划模型用lingo进行求解。
问题一给出了一个月的时间要求，同时需要考虑到最少的花费和前往最多的景点两个规划目标，是一个0-1多目标的线性规划问题。
我们通过将其中一个规划目标：“最多的景点”划入约束条件，将多目标问题变成“在前往N（N>=12)个景点的条件下，最少花费”的0-1线性单目标规划问题。
使用lingo后求出结果如下：乌鲁木齐—哈密—库尔勒—楼兰—阿克苏—千佛洞—天鹅湖—
每个区块
0-1线性
以求得
可使用lingo
达
力。
1
2．如果他们打算今、明两年暑假完成对新疆的旅游，请你们为他们设计合适的旅游路线，使在新疆境内的交通费用尽量地节省。
3．如果华东某高校的少数民族研究所组织对新疆文化考察，考察分三组进行，用于交通的时间和前两种情况相同，但考察时间是旅游观光时间的四倍，请你们为他们设计合适的考察路线，以便尽早完成考察任务。
4．新疆自治区旅游部门为迎接“五一旅游黄金周”（考虑到远途旅游，自治区内游程延长为十二天）准备为自治区外的游客组织多条旅游路线以分散游客，提高接待的质量。
在假设参加你们设计的各条路线的游客人数与整条路线的接待能力成比例的条件下，请你们为新疆自治区旅游部门设计合适的、准备向游客推介的全部旅游路线。
下图是新疆主要景点分布图，各旅游点之间的路程、每个景点的最佳逗留时间等信息可以登陆
新疆旅游网对题。
你也可以目做进一步的完善。
二、问题的分析
由简单的分析可以得出，问题的实质都是要求得出一条满足某一约束条件的旅游路线。
我们将景区进行编号，并通过网络查找到各个景点之间的距离，我们就可以将实际地图简化为赋权无向图，所以问题就变成了图论问题。
另外我们还需补充路费、最佳逗留时间以及门票费用等其他信息。
问题一的目标是找到一条能在一个月内实现的最佳旅游路线，要求花费最少，景点最多，这是一个多目标线性规划问题。
我们可以使用floyd 算法求得各个顶点（景区）之间的最短路径，然后我们以花费最少为规划目标，将“景点最多”这一目标放入限制条件中，要求走过的景点数为N （N>=12)。
然后再建立时间、景点路线为要求的约束条件，将多目标规划问题转变成单目标0-1规划问题。
使用lingo 求解可得最佳旅游路线。
我们很等。
则，线性规 然即1.2.3.4.5.6.m 1m 总的交通费用
2m 总的门票费用
i c 第i 个景点的门票费用
w 每条路线总的行驶路程
ij c 若ij c =1，则表示从i 景点去j 景点，否则ij c =0
ij r 表示i 景点与j 景点之间的距离
t表示从i景点到j景点多需的时间
ij
t表示游客在i景点的最佳逗留时间
i
五、模型的建立与求解
问题一
基于分析，我们首先在网上收集各旅游景点之间的路程、门票、最佳逗留时间、汽车的行驶速度以及住宿费用，具体数据见表1，并据此对地图进行了简化，如下图所示:
我们加上了王先生夫妇特别向往的景点天池和达坂城。
对于很靠近旅游景区的景点，我们把它划分到一个景区，只考虑各景点的最佳逗留时间的和。
我们需要根据以上数据规划出一条路线让王先生夫妇能够在一个月内用最少的花费走过最多的景点，这是一个典型的优化问题。
从上面的加权图中我明年
可以使用FLOYD算法求出任意两个景点之间的最短路径，然后将其做成一个完备
图。
由于该0-1规划中存在两个目标，即花费最少和最多的景点，我们可以将景
点数设置为一定的情况下单独考虑花费最少这一目标函数，将多目标规划变为单
目标规划。
然后不断改变设定的景点数，就不同景点数情况下的花费经过综合对
比求出最佳路线。
旅途中总的消费除吃饭外主要考虑交通费用m1和门票费用m2
则得到目标函数：
约束条件如下：
约束1：时间约束，游玩所有景点最佳路线的时间不能超过一个月，即300个小时。
此时间包括路上交通所消耗的时间和景点逗留时间，路上消耗的时间为
2121
11ij ij i j c t ==⨯∑∑，景点逗留的总时间为()2121
1112ij i j i j c t t ==⨯⨯+∑∑，由此可得 约束2：我们假设王先生夫妇游玩的景点数为n ，一共有21个景点，为保证数量，我们规定n=12，13。
19，由假设可知，所选路线为1个环形，因此
约束3：所有经过的景点相连成为一个圈。
则，对于每个景点，最多只有一条边进入，同样只允许最多一条边出来。
并且只要有一条边进去就有一条边出来，因此1,,1,2,...,19ij jk
c c i j =≤=∑∑
妇推荐景点数为13的旅游路线：1-4-5-19-15-14-13-11-6-12-7-8-2-1总费用为2916.2元
问题二：
据分析，我们需将所有景点分为2组，保证游完每条线路的时间不超过一个月，且每组的时间尽量相等，即均衡度尽量小。
按照实际地理情况，我们将所有景点按南北疆分为如下2组：
线性规划模型如下：
对上述分组如下调整
遗址—楼兰—库尔勒—乌鲁木齐，交通费用为2797.8元。
问题三：
据分析，首先根据问题一中求得的各景点间的最短路径，画出以乌鲁木齐为起点的树状图如下
由题意考察团分三组进行，且考察对象为所有景点，即所有景点都必需包括在内，则要把所有景点分成3组。
分组过程中需尽量遵守以下4个原则：1.长枝与短枝组合搭配。
2.同枝的点尽量不分开。
3.相邻干枝的点分在一组。
4.尽量使各组的停留时间相等。
按以上4个原则，可将所有景点按如下所示分为6个区，分组情况如下所示：第一种分组（严格按分组原则分）
该分法的均衡度较差，因此我们对分组进行调整，将将⑥中的4景点调整到
路途中时间为13482/85=138.61h，158.6/7=19.87天，若平均分给4个组，则每组19.87/4=4.95>4,所以分4组不可行。
因此分5组.
六、模型的分析与优化
本文通过合理的假设和数据的补充，将原问题简化为图论的0-1规划问题进行解答，简单易懂，与现实的贴合度高。
@ole('D:/新疆.xls')=xij;
enddata
min=0.4*@sum(link(i,j):rij(i,j)*xij(i,j))+0.5*@sum(link(i,j):xij(i,j) *(tickets(i)+tickets(j)));
@SUM(link(i,j):xij(i,j))=n;
@sum(link(i,j):(xij(i,j)*tij(i,j)))+0.5*@sum(link(i,j):xij(i,j)*(ti(i )+ti(j)))<480;
@for(cities(i):@sum(cities(j):xij(i,j))<=1);
@for(cities(j):@sum(cities(i):xij(i,j))<=1);
@for(cities(j):(@sum(cities(i):xij(i,j))-@sum(cities(k):xij(j,k)))=0)
;
@sum(cities(i):xij(i,1))=1;
@sum(cities(j):xij(1,j))=1;
@for(link(i,j):(xij(i,j)*xij(j,i))=0); @for(link:@bin(xij));
end。