最佳旅游路线设计方案作者：吴渊、张文艳、周子晗摘要：主办方为参加会议的代表安排了旅游，初步设想了五条线路，但是由于代表们的日程不同；还有后面出现的代表们的旅游意向；各景点的天气状况；在这些条件的影响下，需要主办方根据不同的情况设计出不同的旅行路线。

而且要求设计出的路线花钱少，游览的景点多。

在提出的几个问题中，分别利用了穷举法、图论中Hamilton图的性质，营销员推销路线模型，并尝试对附录表中的数据进行统计，处理之后取舍路线。

经过特定的处理之后，问题之间会出现相似的解题模型，最后利用LINGO和逐步搜寻最优的方法得出结果。

问题的重述：主办方初步提出的参考路线如下：一号线：成都→九寨沟、黄龙；二号线：成都→乐山、峨嵋；三号线：成都→四姑娘山、丹巴；四号线：成都→都江堰、青城山；五号线：成都→海螺沟、康定；每条线路中的景点可以全部参观，也可以参观其中之一。

不仅如此，一起参观景点的人数越多，每人承担的费用也会越小。

第一问和第三，四，五问中都要求在有限的10天内游览的景点多，并且花费少。

但是问题三中有100个代表对五条路线的意愿限制，问题五中又添加了未来10天之内各个景点的天气情况。

在第四问中，仍然有100个代表的意愿限制，但是前五十个代表先去，后五十个四天之后再去。

第二个问题中每一个景点都游玩一次，有充足的时间，要求设计出交通费用最少的路线。

问题的假设：1. 整个旅行过程的乘车方式都为汽车，每天的食宿费一定，都为100元。

2. 任意两个景点都可以直达，一个景点只游玩一次，在一个景点至少花一天的时间游完，通过大量的常规旅游行程统计，确定了在各个景点所需的游玩时间。

3. 到达景点之间的行车时间都不超过一天，且计入要到达景点的游玩时间内。

4. 由于有些景点之间的乘车价钱没有搜集到具体数据，因此我们按0.2元/公里计算。

5. 根据所查询的各景点资料得知，丹巴、康定是包含多个景点的地区，因此这两个景区总的旅行票价是当地有名景点的票价之和。

6. 对代表们的旅游意愿赋值，去的为1，不去的为-1，无所谓的为0.若路线中含有他们不愿意去的路线，他们就不参加旅行。

引入参量：i , j………………..分别表示路线中的所有景点(i,j =0…10) X(i , j)…………….表示从景点i到景点jP j………………..表示景点j的票价A(i , j)…………….表示景点i到景点j的距离D j………………..表示在景点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相同，只是把前50个人的意愿整体处理，得出他们这条路线包括那些景点，人数计算同上题一样。

后50个人以同样的方法解决，主办方安排的这次旅游总花费，有这两个不同路线的旅行花费构成。

而每一部分的费用计算同问题1类似。

5. 这个问题中由于天气的原因，原来设计的路线会被改动。

例如：假设原定路线中，第一天去九寨沟，但是第一天九寨沟一定下雨，主办方就把第一天定为去黄龙（下雨的概率小于等于50%）；如果第二天有两个下雨概率小于等于50%的景点，就选那个离第一天所游景点最近的那个，依次选定后就会形成新的路线。

但是新的路线并不是最优化的路线，因此会造成一定的损失费。

新路线的费用计算根据景点的花费水准（票价，路费，食宿费）确定下来，新路线所需费与最优化费用之差就是损失费。

模型的建立：1.一个人在这次旅行中花费S的最少，可以表明总的花费最少。

费用包括三个部分，即景点票价，路费，食宿费。

若从i到达j景点并游玩，则需花费x(i , j)*(Pj+A(i , j) ).min=101000x(,)*((,)*0.2)1000i j i j Pj A i j==++∑∑st.100(,)1ix i j==∑100(,)1jx i j==∑U(i)-u(j)+9x(I,j)<=82. 根据Hamilton图的特点，Min=101000(,)*((,)*0.2)j i X i j A i j==∑∑st.100(,)1ix i j==∑100(,)1jx i j==∑U(i)-u(j)+11x(I,j)<=103. 路线中的景点经过重新编号后包括：1九寨沟，2黄龙，3四姑娘山，4丹巴，5海螺沟，6康定。

2路线一定去的人数是12，4路线一定去的人数是14，则参加旅游的人数是100-26=74人。

min=746600x(,)*((,)*0.2)1000i j i j Pj A i j==++∑∑st.60(,)1ix i j==∑60(,)1jx i j==∑U(i)-u(j)+7x(I,j)<=64. 前50人选择的路线中经过重新编号的景点包括：1四姑娘山，2丹巴，3海螺沟4康定，去的人数50-7-8-7=28人。

min=284400x(,)*((,)*0.2)1000i j i j Pj A i j==++∑∑st.40(,)1ix i j==∑40(,)1jx i j==∑U(i)-u(j)+5x(I,j)<=4后50人选择的路线中经过重新编号的景点包括：1九寨沟，2黄龙，3青城山，4都江堰，去的人数50-4-7-7=32人。

min=324400x(,)*((,)*0.2)1000i j i j Pj A i j==++∑∑st.40(,)1ix i j==∑40(,)1jx i j==∑U(i)-u(j)+5x(I,j)<=45.路线中的景点如下：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元）：成都--都江堰—青城山—四姑娘山—丹巴—康定—海螺沟--峨眉山—乐山—成都2. 第二题的路线（总距离为1972.6公里，耗时13天，每个人总费用为2840元）：成都—九寨沟—黄龙—都江堰—青城山—四姑娘山—丹巴—康定—海螺沟--峨眉山—乐山—成都3. 第三题的路线（总距离为1684公里，耗时9天，每个人总费用为2072元）：成都—海螺沟—康定—丹巴—四姑娘山--黄龙—九寨沟—成都4. 第四题的路线（可分为两条路线）：第一条路线（总距离为918公里，耗时6天，每个人总费用为1354元）：成都—四姑娘山—丹巴—康定—海螺沟—成都第二条路线（总距离为1005.2公里，耗时5天，每个人总费用为1241元）：成都—都江堰—青城山—黄龙—九寨沟—成都5. 第五题的路线（总距离为1931公里，耗时9天，每个人总费用为2121元，改变路线造成损失49元）：成都—丹巴—康定—海螺沟—四姑娘山--黄龙—九寨沟—成都结果评价：每一个问题的结果都是在一些特定的假设条件下得出，假设的条件缺少很强的合理性，比如在第三题以及后面的一些路线中出现代表们不愿意去的地点，他们就不参加这次旅行.。

在实际情况中，这是不合理的假设，但是由于将问题简化，才提出这样的假设.。

而且条件中有去的人越多，每个人所承担的费用越少，这一条件在模型中并没有得到体现。

详细的资料搜寻为结果提供了可靠的数据保障，所得每条路线中显示了费用，耗时，和路程。

总体上所得结果还是具有很大的参考性。

附件的处理：一号线二号线三号线四号线五号线11-1-100201-11-130-101-14000-1050-11-1060000070010081-10-10900000100000111001-1012-110-1113-11000140000-11500100160-1001170001018-1000019-1-1000 2000000 21000-1-1 220-1-100 2300-100 2401001 2500000 260-100-1 2700100 2800010 29100-10 3000000 3101001 32000-1-1 3300-1-10 3400000 35-1-1000 36-110-11 3700000 381-1100 3911000 4000000 410-1010 42-100-10 4300110 44-1-1000 450-1-101 4600100 47100-10 4801-10-1 4910010 50-10001 511-1100 520001-1 53000-10 5410100 550-1000 560100-1 5700010 580-1000 5910001 6000-1016110000620-11-10630101064010-1065-1000-16600010670-1-10-1680010069000007010001710000072-1-10-1073000007410-101750-10007600011770000078-10-10079-100018001000810-10008210-100830000-184-10010850001-18600100870000088100018910000900000-19100-10092100009300-1-1094000-1095101-109600000970-100098100109900-100100101-1-16-100-50一定去的人数2012151415前50个代表意愿处理：后50个代表意愿处理：一号线二号线三号线四号线五号线511-1100 1-1-100520001-1 01-11-153000-10 0-101-15410100 000-10550-1000 0-11-10560100-1 000005700010 00100580-1000 1-10-105910001 000006000-101 000016110000 001-10620-11-10 -110-116301010 -1100064010-10 0000-165- 1000-1 001006600010 0-1001670-1-10-1 000106800100 -100006900000 -1-10007010001 000007100000 000-1-172-1-10-10 0-1-1007300000 00-1007410-101 01001750-1000 000007600011 0-100-17700000 0010078-10-100 0001079-1 0001 100-108001000 00000810-1000 010018210-100 000-1-1830000-1 00-1-1084-10010 00000850001-1 -1-10008600100 -110-118700000 000008810001 1-11008910000 11000900 000-100000910 0-100 0-10109210000 -100-109300-1-10 0011094000-10 -1-100095101-10 0-1-1019600000 00100970-1000 100-109810010 01-10-1990 0-100 10010100101-1-1 -10001-5-10-1 -2-51-517 8 7。