第八届苏北数学建模联赛B题一等奖获奖论文---旅游路线的优化设计模型

2011年第八届苏北数学建模联赛题目旅游路线的优化设计模型摘要本文研究了旅游路线的优化问题，通过上网搜索了旅游路线、车次（航班）、门票等有关数据，并通过Lingo软件处理了数据。全文主要运用了贪婪法、线性规划法和图论hamilton圈等方法，分别建立了旅游路线的优化设计模型。模型一：考虑车费、景点费、车次衔接、旅游路线最短等因素，使用最优化方法和线性规划法，建立总费用最小的最优路线目标函数：MinA111111ijijijcx+11111112ijijijxbb+11111112ijijijxdd，利用Lingo软件求解出最低费用为2924元时的最优路线:徐州→常州→舟山→黄山→九江→武汉→西安→洛阳→祁县→北京→青岛→徐州。模型二：建立新约束条件和目标函数的线性规划模型：MinT111111ijijijtx11111112ijijijxtt+11111112ijijijxee，利用了Lingo软件求解出最短时间路线，但受“车次的时间衔接”等现实条件约束需对其作适当调整，最终得到最少时间为9天的旅游路线:徐州→青岛→常州→舟山→黄山→北京→洛阳→西安→祁县→武汉→九江→徐州。模型三：使用图论Hamilton-圈原理，建立费用固定下游览最多景点的最优路线模型，得到景点数为7个的最优路线：徐州→常州→黄山→九江→武汉→西安→洛阳→祁县→徐州。模型四：考虑交通班次有无、时间衔接矛盾等实际条件，利用贪婪法建立模型，通过求取局部最优解最终确定一条游览6个景点的较优路线：徐州→北京→祁县→常州→武汉→西安→洛阳→徐州。模型五：结合模型三、四，建立约束条件式（5.5.1.1）、（5.5.1.2），利用贪婪法求解出一条包含6个景点较优路线：徐州→常州→黄山→武汉→洛阳→祁县→徐州。关键词：Lingo软件最短路线贪婪法线性规划Hamilton圈1一．问题的重述随着人们生活水平的提高，人们越来越喜欢旅游这项活动。徐州的一位旅游爱好者，想在五一期间到全国一些著名景点旅游。由于跟着旅游团会受到若干限制，所以他（她）打算自己作为背包客旅游。在出游之前他（她）选择了全国十个省市的旅游景点，作为五一的旅游目的地，分别如下：徐州，山东(青岛)，北京（八达岭），山西（祁县），陕西（西安），湖北（武汉），江西（九江），安徽（黄山），浙江（舟山），江苏（常州），河南（洛阳）景点分布如图：（景点分布图）由于旅游时会受到多种实际因素影响，如：游览景点的数目，旅游的时间，旅游者的经济状况等所以产生了如下的问题：一．为旅客设计合适的旅游线路，在不受时间约束的情况下，使旅客花最少的钱游览全部的景点。二．如果旅游费用不限，旅客想游览十个景点，那么需要设计一个最优的路线，使旅客花费最少的时间。三．如果旅客受到旅游费用的限制，只带来2000元，他（她）想游览尽可能多的景点，要想满足该条件，我们必须设计一条合适的路线，使旅客满意。四．在不考虑旅游费用的情况下，旅客想在五天的时间里游览尽可能多的景点，则要求我们设计一条满足要求的路线。五．在旅游的时间和旅游的费用受到限制时，要想游览较多的景点，则在满足要求的情况下，设计一条使旅客满意的旅游路线。二．符号说明i,j--第i个景点或第j个景点，,1,2,......9,10,11ij分别表示徐州，山东(青岛)，北京（八达岭），山西（祁县），陕西（西安），湖北（武汉），江西（九江），安徽（黄山），浙江（舟山），江苏（常州），河南（洛阳）2it--旅客在第i个景点的逗留时间（包括旅客从车站到达景点所花费的行车时间和游览景点的停留时间）；ib--旅客在第i个景点的门票消费费用；ijt--旅客从第i个景点到第j个景点路途中所花费的时间；ijc--旅客从第i个景点到第j个景点所花费的交通费用，不包括路途中的其他费用；10ijijx旅客从第个景点到第个景点其他；ie--旅客可能在第i个景点的住宿时间；id--旅客在第i个景点的消费，包括住宿费和吃饭的费用；三．问题的分析根据对题目的理解，我们知道问题的求解是在满足每题要求的情况下，要设计一条最优的路线，从而使旅客花费的钱最少或使用的时间最短或游览的景点数最多。所以我们需要对每一个问题进行分析。3.1问题一的分析：问题一要求我们设计合适的路线，在不受时间限制的情况下，让旅客花最少的钱游览完十个景点。在满足景点约束的条件下，我们使用货郎担问题解决办法和Lingo软件，设计出一条最优的旅游路线，让旅客花的费用最少。3.2问题二的分析：问题二改变了目标，即要求我们游览完十个景点后，使旅客花费的时间最短，且旅游费用不限。在满足这些条件下，我们可以选择路线较短的行走或使用较快的交通工具等，通过分析我们使用Lingo软件，设计较优的路线。那么根据这些我们要设计一条较优的路线，满足旅客的要求。3.3问题三的分析：问题三给了我们确定的旅游费用，时间没有具体的限制，要旅客完成尽可能多的景点游览。通过对题目的理解，我们可以选择在满足旅游费用的情况下，用图论法和Hamiltom-圈法，使用较便宜的交通工具，但同时要满足住宿费的限制。3.4问题四的分析：问题四要求在五天的时间里，使旅客尽可能的游览较多的景点，在这里旅游的费用没有确切的限制。根据对题目的理解，我们可以选择使用较快的交通工具或选择较短的路线行走，则我们使用贪婪法对问题进行求解，从而可以设计两条较优的路线，供旅客选择。3.5问题五的分析：可以看出问题五是问题三和问题四结合起来的题，本题受到时间和旅游费用的约束，在这种情况下要想游览较多的景点，我们可以选择交通费用较少，使用时间较短的路线行走。结合贪婪法和图论法，这样我们可以设计一条较优的路线，使游览的景点最3多。四．模型假设1.假设旅客到达一个城市后，从车站到旅游景点的时间和费用，算在旅客在景点的停留时间和停留时所花费的费用；2.旅行中没有意外情况的发生，如：交通堵塞、航班（车次）的推迟、天气影响等；3.旅客能够成功订购车票和景点门票;4.假设景点的开放时间为8：00至18：00;5.城际交通出行可以乘火车（含高铁）、长途汽车、飞机（不允许包车和包机）：五．模型建立及求解5.1模型一的求解：5.1.1目标函数的确立：根据题目，我们有这样的理解：在访问一个城市后必须要有一个即将访问的确切城市；访问城市j前必须要有一个刚刚访问过的确切城市，且是一次“巡回”则111231011nijix（i,j，，，，），111231011nijjx（i,j，，，）为了避免产生子巡回，我们引入额外变量iu（i=1，2，3........n）附加到问题中，则附加下面形式的约束条件：1ijijuunxn2ijn为了证明该约束条件有预期的效果，必须证明：（1）任何含子巡回的路线都不满足该约束条件；（2）全部巡回都满足该约束条件首先证明（1）：用反证法。假设还存在子巡回，也就是说至少有两个子巡回。那么至少存在一个子巡回中不含城市1.把该子巡回记为121......ikiii，则必有121iiuun231iiuunn......11ikiuunn把这k个式子相加，有1nn矛盾！故假设不正确，结论（1）得证。4下面证明（2）：采用构造法。对于任意的总巡回11...1inii，可取iu=访问城市i的顺序数，取值范围为0,1,...2n因此，2ijuun，2ijn.下面来证明总巡回满足该约束条件。（i）总巡回上的边：1223211111........................................11nniiiiiiuunnnuunnnuunnn（ii）非总巡回上的边：11211,2,...,2,2,3,...212,3,...rnijrrijruunnrnjniiuunnjni从而结论（2）得证。根据以上的证明，再结合本题的题目，我们可以知道在不受时间限制的情况下，要想游览的景点多，并且费用较少，经过分析可得，旅游的费用由三部分组成，即路费、门票费用和可能的费用（包括住宿费用、吃饭的费用等），所以我们定义：A—旅客旅游所花费的总费用；1a--旅客在路上所花费的总费用（组要是路费，其他的不考虑）；2a--旅客在各景点所花费的门票费；3a--旅客可能花费的费用（住宿费、吃饭的费用等）；所以建立的目标函数为：23iMinAaaa（1）交通总花费因为ijc表示旅客从第i个景点到第j个景点所需的交通费用;用ijx表示旅客是否从第i个景点直接到达第j个景点的0---1变量，由于旅客游览十个景点，且是一次巡回，所以我们得到交通总费用为：1111111ijijijacx（2）旅游景点的门票花费用ib表示旅客在第i个景点的消费，用ijx表示旅客是否从第i个景点直接到达第j景5点的0---1变量，由对本题的分析可知，本题为环形路线，且是一次巡回，所以我们得到旅游景点的门票费用为：111121112ijijijaxbb（3）可能的费用用id表示旅客在第i个景点消费费用，其中有住宿费、吃饭费用和其他方面的费用；用ijx表示旅客是否从第i个景点到达第j景点的0---1变量，由对本题的分析可知，本题为环形路线，且是一次巡回，所以我们得到可能的费用为：111131112ijijijaxdd综上所述，我们可得总的目标函数为：23iMinAaaa=111111ijijijcx+11111112ijijijxbb+11111112ijijijxdd（5.1.1.1）5.1.2约束条件：①旅游景点数的约束根据题目要求及假设情况，我们用111111ijijx表示旅游的景点数，则我们假设旅游的景点数为n(n=2,3,4,5,6,7,8,9,10),因为旅客要游览十个景点，所以n=11。故旅游景点数约束为：11111111ijijx（n=1，2,3,4,5,6,7,8,9,11）②0—1变量约束为了使旅游费用最少，则我们需要选择不同的旅游路线，因为本题为环形路线，且是一次巡回，所以我们可以把所有的景点连成一个圈，而把每一个景点看做圈上一个点。对于每个点来说，只允许最多一条边进入，同样只允许最多一条边出来，并且只要有一条边进入就要有一条边出去。因此可得约束：11111ijijijxx（,ij=1，2，3……9,10,11）当1i时，因为徐州是出发点，所以11ijix；1j时，因为代表们最终要回到徐州，所以11ijjx.根据题目所述，我们可以得到以下结论：1ijijijxx611ijix11ijjx（,ij=1，2，3……9,10,11）同样，当i，2j时，根据题意不可能出现1ijjixx，即不可能出现游客在两地间往返旅游，因为本题为一次巡回，则综上所述，我们可得约束为：0ijjixx5.1.3模型建立：根据对本题的分析，我们可以得到总的模型为：23iMinAaaa111111ijijijcx+11111112ijijijxbb+11111112ijijijxdd（5.1.3.1）约束条件11111111ijijx（,ij=1，2，3……9,10,11）1ijijijxx（,ij=1，2，3……9,10,11）111,1ijijijxx（,ij=1，2，3……9,10,11）0ijjixx（,ij=2，3……9,10,11）5.1.4模型求解与结果分析：根据模型，利用Lingo软件求解出最短路线。由于现实条件约束，参照最短路线综合考虑各种因素，求解出最低费用为2924元的较优路线：徐州→常州→舟山→黄山→九江→武汉→西安→洛阳→祁县→北京→青