《旅游路线规划1 (2).doc》由会员分享，可在线阅读，更多相关《旅游路线规划1 (2).doc（17页珍藏版）》请在金锄头文库上搜索。
1、旅游路线的优化设计摘要本文通过查阅各景点之间的距离及时间的相关资料，运用图论中的Hamilton圈将相连后的景点看作为一个封闭的圈，参照货郎担（TSP）问题使用线性规划列出相关目标函数后运用lingo求解。对于问题一，在得到距离数据后，在假设距离短则花费少的思路下，使用0-1规划建立目标函数，建立关于时间和景点数量的约束条件，在软件求解下得到十个景点3892.5元的最小旅行花费。而在问题二中将距离数据改成时间数据，得到7.5天游玩8个景点的优化方案。关键词：图论 Hamilton圈 0-1规划 一、问题重述某背包客要独自旅游十个景点，分别是：江苏常州市恐龙园，山东青岛市崂山，北京八达岭长城，山
2、西祁县乔家大院，河南洛阳市空门石窟，安徽黄山市黄鹤楼，陕西西安市秦始皇兵马俑，江西九江市庐山，浙江舟山市普陀山。又已知上述各个景点的最短停留时间分别是4小时，6小时，3小时，3小时，3小时，7小时，2小时，2小时，7小时，6小时。假设：1 城际交通出行可以乘火车（含高铁）、长途汽车或飞机（不允许包车或包机），并且车票或机票可预订到。2 市内交通出行可乘公交车（含专线大巴、小巴）、地铁或出租车。3 旅游费用以网上公布为准，具体包括交通费、住宿费、景点门票（第一门票）。晚上20:00至次日早晨7:00之间，如果在某地停留超过6小时，必须住宿，住宿费用不超过200元/天。吃饭等其他费用60元/天。一
3、、 假设景点开放时间为8:00至18:00。问题：根据以上要求，针对如下的几种情况，为该旅游爱好者设计详细的行程表，该行程表应包括具体的交通信息（车次、航班号、起止时间、票价等）、宾馆地址和名称，门票费用，在景点的停留时间等信息。（1） 如果时间不限，游客将十个景点全旅游完，至少需要多少旅游费用？请建立相关数学模型并设计旅游行程表。（2） 如果旅游费用不限，但由于“十一”假期只有7天，为了使游客能尽可能多游览景点，请通过建立相关数学模型，为其设计该旅游行程表。如果这位游客只有7天的假期时间和5000元的旅游费用，想尽可能多游览景点，请建立相关数学模型并设计旅游行程表。三、问题假设及符号约定1.
4、模型假设：1) 问题一中尽量不考虑以飞机作为交通工具，以节省费用车次或航班在旅行途中的时间。2) 问题中不考虑城市间的公交线路拥堵等造成的特殊情况。3) 各城市的公交费用相等，皆为10元。2.符号约定：第个景点或第个景点 ；（分别代表浙江杭州、江苏常州、山东青岛、北京八达岭、山西祁县、西安兵马俑、湖北武汉、江西九江、安徽黄山、浙江舟山、河南洛阳）；：旅行者的旅游总消费；：在第个景点的逗留时间；：在第个景点的总消费；：旅游者从第个景点到第景点路途所需时间；：旅游者从第个景点到第景点路途所需的交通费用；：1表示旅游者直接从第个景点到第景点；0表示其它；：总的交通费用；：旅行所花时间二、问题分析将该
5、背包客旅游的景点一一描点相连，不难发现旅游范围几乎囊括了大半个中国。旅游的时间段为10.1黄金周，也昭示着传统旅游旺季的来临，各大景点几乎是人满为患。因此旅游者安排一个合理的出行计划就至关重要了。对于问题一，我们知道在时间不限，费用最少的要求下，黄金周时期高昂的机票让游客可以不用考虑乘坐飞机往来景点所在城市，剩下的便是城际的长途客车和铁路线系统。生活观察中，我们发现出发地和目的地距离越远，乘坐交通工具所需的费用也就越大：参考网上的数据我们可以得到两两城市之间的大致距离，根据城际间的各种票价，我们发现不管何种交通工具，伴随着距离的增加费用也随之增长。由此可以推断出，只要求得各大旅游城市距离总和的
6、最小值，依据这个最小值，背包客可以决定旅游城市的先后顺序，参照当天的旅游情况，选择长途客车或铁路系统；同时为了减少费用，可以有选择的安排游客在夜间的长途客车或火车（包括动车高铁）中休息，即可省去在当地住宿的费用。对于问题二，考虑旅游者费用充足且时间限定，因此我们可以极端的假设。一切都以时间最省为基准。在所有交通工具中飞机时间最省，加上登机时间，飞机较之于长途客车和铁路系统在时间的节省上也远远领先。参照网络中各个目的地之间的航班，确定出城市之间飞行所用时间。由于有些城市对另一城市不存在直达航班，此时我们考虑中途转机（或乘坐火车）到目的地邻近的城市再转动车或客车。在这样的安排下游客可以在7天内尽可
7、能多游览景点。四、模型的建立与求解问题一：4.1.1数据准备根据两个城市之间的公路及铁路，经过数据查询，得到下表各个旅游城市之间的距离：表一：各旅游城市距离表起始目的地江苏常州山东青岛北京八达岭山西祁县西安兵马俑湖北武汉江西九江安徽黄山浙江舟山河南洛阳杭州35214241591159615588077794222301171常州973129813321344662586507385957青岛819100815721518142015439751185北京81511591200131415331430807祁县593124311681315.61569.6706西安102511021386160
8、9387武汉2407491059638九江571779964黄山4621113舟山1200洛阳灰格子代表该景点与另一个景点距离重复在上表中，为方便统计，将浙江杭州到河南洛阳依次编排序号为111，记为 。4.1.2 算法的确定将至共11个点两两相连，利用排列组合公式得到11个景点共条线路，得到图一：图一从图中看出，11个城市之间的路线十分复杂，但必定存在一种最短路径法求解11个城市的次序。根据假设，整个旅游路线是环形，即最终旅游者要回到杭州，因此我们可以把整个路线看做一个Hamilton圈，这样该问题就归结为货郎担（TSP）问题。4.1.3 目标函数的确立： 经过对题目分析，我们可以知道本题所要
9、实现的目标是，使旅游者在不规定时间的情况下游玩十个景点所花的费用最少。显然，花费最少是该问题的目标。因此，我们的做法是在满足相应的约束条件下，先确定游览的景点先后，然后计算出在这种情况下的最小花费。游览的总费分别为交通总费用和在旅游景点的花费等组成，其中大部分都是规定的，只有交通费用是可以选择的。所以我们定义：每个旅游者的旅游总花费；每个旅游者的交通总费用；从而得到目标函数： 因为表示从第个景点到第个景点所需的交通费用，而是判断代表们是否从第个景点直接到第个景点的01变量，因此我们可以很容易的得到交通总费用为：从而我们可以得到目标函数为：4.1.3约束条件：时间约束 问题一放宽了对时间的要求，
10、我们不妨可以假定限制的时间为15天（360个小时），因为表示从第个景点到第个景点路途中所需时间，所以路途中所需总时间为；表示旅游者在第个景点的逗留时间，故旅游者在旅游景点的总逗留时间为。因此，总的时间约束可得：旅游景点数约束 由题目要求可知，因为旅游者的时间充裕，因此他（她）打算游览完全部11个景点。因此将其约束为： (，=1，2，11)01变量约束在已经知道了要旅游所有的景点的前提下，对于Hamilton圈中的每个点来说，只允许有一条边进入，同样，也只允许有一条边出去。用公式表示即为： （，=1，2，11）同样，当，时，根据题意不可能出现，即不可能出现游客在两地间往返旅游，因为这样显然不满足
11、游览景点尽量多的原则。因此我们可得约束： （，=2，3，11）最后我们将其模型建立为如下所示： 运用lingo解得旅游者游行十个景点通所用的费用为1224，景点先后顺序如下所示：浙江杭州浙江舟山安徽黄山江西九江湖北武汉河南洛阳西安兵马俑山西祁县北京八达岭山东青岛江苏常州浙江杭州。如下图所示：图二4.1.4问题一所建模型结果 根据搜索出来的数据值，我们在对时间的放宽情况下，选取交通费用最少的交通工具和住宿费用来安排其的行程安排表，如下表所示：日期起终车次起止时间价格/元景点逗留时间/h住宿/价格1号杭州舟山客车 高大27：5011：30706舟山普陀港城商务酒店单人房178元/天2号不游玩舟山宁
12、波客车 高速7：058：3032宁波黄山客车 高大一13：4018：20132世界家庭式酒店/民宿 90元/天 3号黄山8：0018：0010世界家庭式酒店/民宿 90元/天4号黄山九江大巴8：0013：00122学校招待所40元/天5号九江庐山8：0015：007九江武汉火车 k398/k39517：0020：3041武汉岭南佳园连锁酒店119元/天6号武汉黄鹤楼8：0010：002武汉洛阳火车 k864/k86115：2522：0087洛阳易国际青年旅舍40元/天7号洛阳市龙门石窟8：0011：003洛阳西安火车 k128/k125 14：5019：2055西安七贤国际青年旅舍50元/天8
13、号西安秦始皇兵马俑8：0010：002西安太原空调普快221：486：48148太原祁县乔家大院6815次列车7：009：005.5乔家大院10：0013：003山西北京空调特快T7014：4519：49北京富山国际青年旅舍46元/天9号八达岭长城8：0018：0010北京山东青岛快速K712/k70922：0010：0819510号青岛崂山11：0018：007青岛南京快速 K416/k41320：0011：3020811号南京杭州空调普快200112：4220：0264在将其交通所用的费用，住宿所用的费用，10个景点门票所花的费用，以及11天所用的伙食费累加起来得到在时间不限的情况下至少要消费3892.5元。问题二：4.2.1模型的建立与求解在得到各个旅游城市之间的最小旅行时间后，可以同样利用问题一中所用的，将点与点之间的时间看作为它们边的权值，起点与终点相连可以构成封闭圈，采用Hamilton图
