最佳旅游路线设计方案
作者：吴、张、周
在提出的几个问题中，分别利用了穷举法、图论中Hamilton图的性质，营销员推销路线模型，并尝试对附录表中的数据进行统计，处理之后取舍路线。经过特定的处理之后，问题之间会出现相似的解题模型，最后利用LINGO和逐步搜寻最优的方法得出结果。问题的重述：主办方初步提出的参考路线如下：
一号线：成都→九寨沟、黄龙；
二号线：成都→乐山、峨嵋；
三号线：成都→四姑娘山、丹；
四号线：成都→都江堰、青城XX；
五号线：成都→海螺沟、康定；每条线路中的景点可以全部参观，也可以参观其中之一。不仅如此，一起参观景点的人数越多，每人承担的费用也会越小。
第一问和第三，四，五问中都要求在有限的10天内游览的景点多，并且花费少。但是问题三中有100个代表对五条路线的意愿，问题五中又添加了未来10天之内各个景点的天气情况。在第四问中，仍然有100个代表的意愿，但是前五十个代表先去，后五十个四天之后再去。第二个问题中每一个景点都游玩一次，有充足的时间，要求设计出交通费用最少的路线。
问题的假设：
1.整个旅行过程的乘车方式都为汽车，每天的食宿费一定，都为1001
2.任意两个景点都可以直达，一个景点只游玩一次，在一个景点至少花一天的时间游完，通过大量的常规旅程统计，确定了在各个景点所需的游玩时间。
3.到达景点之间的行车时间都不超过一天，且计入要到达景点的游玩时间内。
4.由于有些景点之间的乘车价钱没有搜集到具体数据，因此我们按0.2元/公里计算。
5.根据所查询的各景点资料得知，丹、康定是包含多个景点的地区，因此这两个景区总的旅行票价是当地有名景点的票价之和。
6.对代表们的旅游意愿赋值，去的为1，不去的为-1，无所谓的为0.若路线中含有他们不愿意去的路线，他们就不参加旅行。
引入参量：i,j………………..分别表示路线中的所有景点(i,j=0…10)_(i,j)…………….表示从景点i到景点j
Pj………………..表示景点j的票价
A(i,j)…………….表示景点i到景点j的距离
Dj………………..表示在景点j的游玩时间
相关数据搜寻结果：
各景点之间路程L(i,j)：(公里)两景点的往返路程相同
问题的分析：
1.由于旅行时间和在各个景点所需游玩时间的，代表们只能游览部分景点，而且最多去八景点。利用穷举法，从出发点开始搜索，距离最短的景点列入路线中，再依次类推的方法搜索其他景点，有根据时间的，搜索出一条路线最短的方案。
2.在一个月的时间内，代表们可以将所有的景点游完，则旅游的路线可以构成一个Hamilton图，所求问题即是使各边权之和最小，符合营销员推销路线模型。
3.100个代表对主办方初步提供的五条线路意愿用1，-1，0赋值之后，根据我们对附表1的处理（100个代表对每条路线的满意度求和；统计出每条路线中一定去的人数），结果的正负成为取舍该路线的决定因素。之后便得到初步的游览景点，将路线2和4淘汰，去掉了3，4，7，8这四个景点，其余6个景点的游览时间小于10天。
参加旅游的人数并非为100个，减掉了一定去2和一定去4路线的人数，剩余的便是参加旅游的人数。
转化之后，此次旅行的费用求解与问题1相似。
4.主办方在此问题中可以设计两条路线，初步的处理方法与3相4
同，只是把前50个人的意愿整体处理，得出他们这条路线包括那些景点，人数计算同上题一样。后50个人以同样的方法解决，主办方安排的这次旅游总花费，有这两个不同路线的旅行花费构成。而每一部分的费用计算同问题1类似。
5.这个问题中由于天气的原因，原来设计的路线会被改动。例如：假设原定路线中，第一天去九寨沟，但是第一天九寨沟一定下雨，主办方就把第一天定为去黄龙（下雨的概率小于等于50%）；如果第二天有两个下雨概率小于等于50%的景点，就选那个离第一天所游景点最近的那个，依次选定后就会形成新的路线。但是新的路线并不是最优化的路线，因此会造成一定的损失费。
新路线的费用计算根据景点的花费水准（票价，路费，食宿费）确定下来，新路线所需费与最优化费用之差就是损失费。
模型的建立：
1.一个人在这次旅行中花费S的最少，可以表明总的花费最少。费用包括三个部分，即景点票价，路费，食宿费。若从i到达j景点并游玩，则需花费_(i,j)(Pj+A(i,j)).
min=_(i,j)(PjA(i,j)0.2)1000
i0j01010
st._(i,j)1
i010
_(i,j)1
j010
U(i)-u(j)+9_(I,j)<=8
2.根据Hamilton图的特点，
Min=_(i,j)(A(i,j)0.2)
j0i01010
st._(i,j)1
i010
_(i,j)1
j010
U(i)-u(j)+11_(I,j)<=10
3.路线中的景点经过重新编号后包括：1九寨沟，2黄龙，3四姑娘山，4丹，5海螺沟，6康定。2路线一定去的人数是12，4路线一定去的人数是14，则参加旅游的人数是100-26=74人。
min=7466_(i,j)(PjA(i,j)0.2)1000
st._(i,j)1
_(i,j)1
U(i)-u(j)+7_(I,j)<=6
4.前50人选择的路线中经过重新编号的景点包括：1四姑娘山，2丹，3海螺沟4康定，去的人数50-7-8-7=28人。
min=2844_(i,j)(PjA(i,j)0.2)1000
st._(i,j)1
_(i,j)1
U(i)-u(j)+5_(I,j)<=4
后50人选择的路线中经过重新编号的景点包括：1九寨沟，2黄龙，3青城山，4都江堰，去的人数50-4-7-7=32人。
min=32_(i,j)(PjA(i,j)0.2)1000
444j0
st._(i,j)1
_(i,j)1
U(i)-u(j)+5_(I,j)<=4
5.路线中的景点如下：1九寨沟，2黄龙，3四姑娘山，4丹，5海螺沟，6康定。
Step1,搜寻出第一天以上景点下雨概率小于等于50%的有：2，4，5，
6.选取其中离成都最近的一个即4（丹）。
Step2,搜寻出第二天没有去过的以上景点下雨概率小于等于50%的有：6康定。
Step3,搜寻出第三天没有去过的以上景点下雨概率最小的有：3四姑娘山和5海螺沟。距离康定较近的是5海螺沟。
Step4,由于在海螺沟游玩2天，搜寻出第五天没有去过的以上景点下雨概率小于等于50%的有：1九寨沟，2黄龙。距海螺沟较近的是3四姑娘山。
Step5，四姑娘山距黄龙较近，且第六天不下雨，所以选2黄龙。则最后一站去1九寨沟。
模型的结果：
1.第一题的路线（总距离为1123.7公里，耗时10天，每个人总费用为1950元）：
成都--都江堰—青城XX—四姑娘山—丹—康定
—海螺沟--峨眉山—乐山—成都
2.第二题的路线（总距离为1972.6公里，耗时13天，每个人总费用为2840元）：
成都—九寨沟—黄龙—都江堰—青城XX—四姑娘山
—丹—康定—海螺沟--峨眉山—乐山—成都
3.第三题的路线（总距离为1684公里，耗时9天，每个人总费用为2072元）：
成都—海螺沟—康定—丹—四姑娘山
--黄龙—九寨沟—成都
4.第四题的路线（可分为两条路线）：
第一条路线（总距离为918公里，耗时6天，每个人总费用为1354元）：
成都—四姑娘山—丹—康定—海螺沟—成都
第二条路线（总距离为1005.2公里，耗时5天，每个人总费用为1241元）：
成都—都江堰—青城XX—黄龙—九寨沟—成都
5.第五题的路线（总距离为1931公里，耗时9天，每个人总费用为2121元，改变路线造成损失49元）：
成都—丹—康定—海螺沟—四姑娘山--黄龙—九寨沟—成都
结果评价：
每一个问题的结果都是在一些特定的假设条件下得出，假设的条件缺少很强的合理性，比如在第三题以及后面的一些路线中出现代表们不愿意去的地点，他们就不参加这次旅行.。在实际情况中，这是不合理的假设，但是由于将问题简化，才提出这样的假设.。而且条件中有去的人越多，每个人所承担的费用越少，这一条件在模型中并没有得到体现。详细的资料搜寻为结果提供了可靠的数据保障，所得每条路线中显示了费用，耗时，和路程。总体上所得结果还是具有很大的参考性。
附件的处理：
一号线112XXXX060XXXX8190XXXXXXXXXXX016XXXX7018-1
二号线-111XXXX010XXXX1100-100
三号线-110XXXX001XXXX1000
四号线0111XXXX0100XXXX0010
五号线0-110XXXX1010-10100
191XXXX021XXXX0220-123XXXXXXX-12700XXX003XXXX0035-113XXXX700XXXX8113XXXX00410-142XXXXXXXXXXX600XXXX7104XXXXXXXXXXX005XXXX4105XXXX015XXXX0580-159XXXX0600
00000-110XXXXXXXXXXXXXXXXXX001XXXX0100XXXX011100-101XXXX001XXXX0100XXXX0XXX00-1
00-100XXXXXXXXXXXXXXXXXX1000-10011
6116XXXX4065-166XXXX069XXXX0171XXXXXXXXXXXXXXXXXXXXXXXXX508XXXX8818XXX5196XXXX199XXXX1001
6一定去的人数
00-111XXXXXXXXXXX010000-110XXXXXXXXXXX000XXXX0100XXXX001000-100XXXX0000-101-10020
00-101XXXX1100-100XXXX0010XXX000-110XXXX001000-100XXXX010XXXX0100XXXX5015
前50个代表意愿处理：后50个代表意愿处理：
一号线二号线三号线四号线五号线5111XXXX1010-100XXXX001XXXX0000-111XXXX000100-101XXXX000XXXX0100XXXX010XXXX0100XXXX011XXXX1001-11
-101XXXX011XXXX0100XXXX0110-100XXXX010XXXX0000-110XXXXXXXXXXXXXXXXXX001XXXX0100
0-110XXXX1010-101XXXX0010-100XXXX001000
520XXXX54105XXXX015XXXX0580-159XXXXXXX-163XXXX165XXXX0670-168XXXX701XXXX7100XXXX730XXXX4107XXXX007XXXX0078-1079-10
800181XXXXXXX-108XXXX087XXXX010900
0101XXXXXXX-100XXXX101XXXX0110XXXX0000-100-10000100-100XXXX100XXXX0101XXXX0000
-100XXXX10000-101XXXX010XXXX0100XXXX0010-1
00-101XXXX0100-110XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX-101XXXXXXXXXXX00XXX00009900
10-1
0-27
0100-518
01-517
1001
01-5
-1-10