旅游线路的优化设计

12011年第八届苏北数学建模联赛承诺书我们仔细阅读了第八届苏北数学建模联赛的竞赛规则。我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与本队以外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规则的,如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们愿意承担由此引起的一切后果。我们的参赛报名号为：参赛组别（研究生或本科或专科）：参赛队员(签名)：队员1：队员2：队员3：获奖证书邮寄地址：22011年第八届苏北数学建模联赛编号专用页参赛队伍的参赛号码：（请各个参赛队提前填写好）：竞赛统一编号（由竞赛组委会送至评委团前编号）：竞赛评阅编号（由竞赛评委团评阅前进行编号）：32011年第八届苏北数学建模联赛题目B题旅游线路的优化设计摘要本文主要研究最佳旅游路线的设计问题。在满足相关约束条件的情况下，花最少的钱、花最短的时间或者游览尽可能多的景点是我们追求的三大目标。基于对此的研究，建立数学模型，设计出最佳的旅游路线。第一问没有时间约束，要求游客游遍所有的景点，该问题也就成了典型的货郎担（TSP）问题。我们建立了一个最优规划模型，在给定游览景点个数的情况下以旅游总费用最小为目标。再引入两个0—1变量分别表示是否游览某个景点以及是否需要在该景点住宿，从而推出交通总费用、住宿费以及吃饭等其它费用的函数表达式，给出相应的约束条件，使用lingo编程对模型求解得到最佳旅游路线为：徐州→恐龙园→黄山→普陀山→庐山→黄鹤楼→龙门石窟→秦始皇兵马俑→乔家大院→长城→崂山→徐州，至少需要的旅游费用为2842元。第二问没有费用约束，要求游客游遍所有的景点，花最少的时间。同样使用第一问的约束条件，将目标函数改成时间函数，使用lingo编程得到最佳旅游路线为：徐州→崂山→长城→乔家大院→秦始皇兵马俑→龙门石窟→黄鹤楼→庐山→黄山→普陀山→恐龙园→徐州，又由附件一的给火车时刻表及逗留时间等得出，至少需要的旅游时间为8天。第三问给定费用约束，我们建立了一个最优规划模型，以景点个数最大为目标。再引入0—1变量表示是否游览某个景点，从而推出交通费用和景点花费的函数表达式，给出相应的约束条件，使用lingo编程对模型求解。得出最多可旅游7个景点的结论，且旅游路线为：徐州→恐龙园→庐山→黄鹤楼→龙门石窟→秦始皇兵马俑→乔家大院→长城→崂山→徐州。对于第四问，与第三问大同小异，只是将约束条件由费用改成了时间，目标函数还是以景点个数最大化。还是使用lingo编程对模型求解，得到最多可旅游8个景点的结论，且旅游路线为：徐州→恐龙园→庐山→黄鹤楼→秦始皇兵马俑→长城→乔家大院→龙门石窟→徐州。第五问，其实就是第三问与第四问的综合，在目标函数不变的基础上，将两问的约束条件合并即可。最后得出最多可旅游的景点数为6个，其路线为：徐州→恐龙园→庐山→乔家大院→秦始皇兵马俑→龙门石窟→黄鹤楼→徐州。本文思路清晰，模型恰当，结果合理.由于所需利用的数据较繁杂，给数据的整理带来了很多麻烦，故我们利用Excel排序，这样给处理数据带来了不少的方便。本文成功地对0—1变量进行了使用和约束，简化了模型建立难度，并且可方便地利用数学软件进行求解。此外，本文建立的模型具有很强普适性，便于推广。关键词：最佳路线TCP问题最短时间景点个数最小费用41问题重述随着人们的生活不断提高，旅游已成为提高人们生活质量的重要活动。江苏徐州有一位旅游爱好者打算现在的今年的五月一日早上8点之后出发，到全国一些著名景点旅游，最后回到徐州。由于跟团旅游会受到若干限制，他(她)打算自己作为背包客出游。他预选了十个省市旅游景点，如表1所示。表1.预选的十个省市旅游景点省市景点名称在景点的最短停留时间江苏常州市恐龙园4小时山东青岛市崂山6小时北京八达岭长城3小时山西祁县乔家大院3小时河南洛阳市龙门石窟3小时安徽黄山市黄山7小时湖北武汉市黄鹤楼2小时陕西西安市秦始皇兵马俑2小时江西九江市庐山7小时浙江舟山市普陀山6小时根据以上要求，针对如下的几种情况，为该旅游爱好者设计详细的行程表，该行程表应包括具体的交通信息(车次、航班号、起止时间、票价等)、宾馆地点和名称，门票费用，在景点的停留时间等信息。(1)如果时间不限，游客将十个景点全游览完，至少需要多少旅游费用？请建立相关数学模型并设计旅游行程表。(2)如果旅游费用不限，游客将十个景点全游览完，至少需要多少时间？请建立相关数学模型并设计旅游行程表。(3)如果这位游客准备2000元旅游费用，想尽可能多游览景点，请建立相关数学模型并设计旅游行程表。(4)如果这位游客只有5天的时间，想尽可能多游览景点，请建立相关数学模型并设计旅游行程表。(5)如果这位游客只有5天的时间和2000元的旅游费用，想尽可能多游览景点，请建立相关数学模型并设计旅游行程表。2问题分析2.1问题背景的理解：根据对题目的理解我们可以知道，游览的总费用由4部分组成，分别为交通总费用、住宿费、景点门票以及吃饭等其它费用。而在确定了相应的目标函数后，所以我们的目标就是在满足所有约束条件的情况下，求出目标函数的最优值。2.2问题一和问题二的分析：问题一要求我们为游客设计合适的旅游路线，使游客在无时间限制的情况下游览完全部的景点。在这里我们的做法是在满足相应的约束条件下，计算出在这种情况下的最小花费。这样最终会得出一个唯一的旅游路线图。问题二实质上是在问题一的基础上，将目标函数由旅游费用改为了旅游时间，即游5客要游览所有的景点花最少的时间，我们完全可以使用与问题一同样的方法进行求解。2.3问题三和问题四的分析：问题三和问题四均要求我们以旅游景点的个数为目标函数，并在问题一与问题二的基础上多加一个约束条件。不同之处在于，问题四的约束条件为时间约束，问题三的为旅游费用约束，其解题方法与问题一、二大同小异。2.4问题五的分析：问题五的求解只需将问题三与问题四的约束条件结合即可参照问题三或四的方法进行求解。3模型假设(1)城际交通出行可以乘火车(含高铁)、长途汽车或飞机（不允许包车或包机），并且车票或机票可预订到。(2)市内交通出行可乘公交车(含专线大巴、小巴)、地铁或出租车。(3)旅游费用以网上公布为准，具体包括交通费、住宿费、景点门票(第一门票)。晚上20：00至次日早晨7：00之间，如果在某地停留超过6小时，必须住宿，住宿费用不超过200元/天。吃饭等其它费用60元/天。(4)假设景点的开放时间为8:00至18:00。4符号说明i,j——第i个或者第j个景点，i，j=1，2，……，11；分别表示徐州、恐龙园、崂山、八达岭长城、乔家大院、龙门石窟、黄山、黄鹤楼、秦始皇兵马俑、庐山、普陀山；m——旅游总花费，元；1m——交通总费用，元；2m——住宿总费用，元；3m——景点门票总费用，元；4m——吃饭等其它费用，元；it——游客在第i个景点的停留时间，小时；ic——游客在i个景点的住宿费，元；pi——第i个景点的第一门票价格，元ijt——从第i个景点到第j个景点路途中所需时间，小时；ijc——从第i个景点到第j个景点所需的交通费用，元；01ijr其他个景点个景点到达第游客直接从第ji01si其他小时地停留超过，游客在至次日早晨晚上600:700:20i5模型建立及求解5.1问题一：5.1.1目标函数的确立：经过对题目分析，我们可以知道本题所要实现的目标是，使这位游客将十个景点全游览完花最少的钱。显然，花费最少是该问题的目标。因此，我们的做法是在满足6相应的约束条件下，计算出在这种情况下的最小花费。这样最终会得出一条最优旅游路线。游览的总费用由4部分组成，分别为交通总费用、住宿费、景点门票以及吃饭等其它费用。由于十个景点全游览，故景点门票费用是确定的，从而得到目标函数：Minm0＝1m+2m+m4(其中，m0表示除去景点门票后的旅游花费)（1）交通总花费因为ijc表示从第i个景点到第j个景点所需的交通费用，而ijr是判断这位游客是否从第i个景点直接到第j个景点的0—1变量，因此我们可以很容易的得到交通总费用为：1111111ijijijcrm（2）住宿总费用因为ic表示在第i个景点的平均住宿费，而is是判断这位游客是否在晚上20：00至次日早晨7：00之间，在某地停留超过6小时的0—1变量，则易知住宿总费用为：1112siiicm（3）吃饭等其它费用因为ijt表示从第i个景点到第j个景点路途中所需时间，所以路途中所需总时间为111111ijijijtr；it表示游客在第i个景点的停留时间，故在旅游景点的总停留时间为11111121ijjiijttr。故旅游花费的总时间为：111111ijijijtr+11111121ijjiijttr因此，吃饭等其它费用为：4m=60×{[111111ijijijtr+11111121ijjiijttr]÷24}从而我们可以得到目标函数为：Minm0＝1m+2m+m4＝111111ijijijcr+111siiic+60×{[111111ijijijtr+11111121ijjiijttr]÷24}5.1.2约束条件：（1）旅游景点数约束111111ijijr为游览的景点总数，由题目要求可知，因为时间不限，因此游客要游览完全部10个景点，徐州也假设为一个景点。因此该约束为：11111111ijijr(i，j=1，2，……，11)7（2）0——1变量约束根据假设，整个旅游路线是环形，即最终代表们要回到徐州，因此我们可以把整个路线看做一个Hamilton圈，这样该问题就归结为货郎担（TSP）问题，当然前提是我们已经知道了要旅游所有的景点。因此，对于Hamilton圈中的每个点来说，只允许有一条边进入，同样，也只允许有一条边出去。用公式表示即为：1iijr1jijr（i，j=1，2，……，11）同样，当i，2j时，根据题意不可能出现1jiijrr，即不可能出现游客在两地间往返旅游，因为这样显然不满足游览景点尽量多的原则。因此我们可得约束：0jiijrr（i，j=2，3，……，11）5.1.3模型建立：综上所述，我们可以得到总的模型为：Minm0＝111111ijijijcr+111siiic+60×{[111111ijijijtr+11111121ijjiijttr]÷24}约束条件：11111111ijijr（i，j=1，2，……，11）1iijr1jijr（i，j=1，2，……，11）0jiijrr（i，j=2，3，……，11）5.1.4模型求解与结果分析通过上网查询资料及原题所提供资料，我们可以得到旅客在第i个景点的最佳逗留时间和他们在第i个景点总消费：t1t2t3t4t5t6t7t8t9t10t1104633372276(单位：小时)地点到达景区时间/小时工具交通费用/元景区门票/元常州2公交旅游车10*2160青岛1公交2*290北京3公交5*245祁县2公交5*240洛阳1公交1.5*2120黄山2专车15*2230武汉2专车4*280西安1专车7*290九江0.5专车15*2180宁波3汽车、轮渡38*2200此外，综合考虑只会在宁波住宿，住宿费为90元。8从而根据模型，使用Lingo编程，得出最省钱的旅游路线为：徐州→恐龙园→黄山→普陀山→庐山→黄鹤楼→龙门石窟→秦始皇兵马俑→乔家大院→长城→崂山→徐州，至少需要的旅游费用为2842元。5.2问题二5.2.1目标函数的确立：此问与第一问大同小异，不同的是要求游客游遍所有的景点，花最少的时间。同样使用第一问的约束条件，将目标函数改成时间函数。