文档介绍：旅游路线的优化设计
摘要
本文通过查阅各景点之间的距离及时间的相关资料,运用图论中的Hamilton圈将相连后的景点看作为一个封闭的圈,参照货郎担(TSP)问题使用线性规划列出相关目标函数后运用lingo求解。
对于问题一,在得到距离数据后,在假设距离短则花费少的思路下,使用0-1规划建立目标函数,建立关于时间和景点数量的约束条件,。而在问题二中将距离数据改成时间数据,。
关键词:图论 Hamilton圈 0-1规划
一、问题重述
某背包客要独自旅游十个景点,分别是:江苏常州市恐龙园,山东青岛市崂山,北京八达岭长城,山西祁县乔家大院,河南洛阳市空门石窟,安徽黄山市黄鹤楼,陕西西安市秦始皇兵马俑,江西九江市庐山,浙江舟山市普陀山。又已知上述各个景点的最短停留时间分别是
4小时,6小时,3小时,3小时,3小时,7小时,2小时,2小时,7小时,6小时。
假设:
城际交通出行可以乘火车(含高铁)、长途汽车或飞机(不允许包车或包机),并且车票或机票可预订到。
市内交通出行可乘公交车(含专线大巴、小巴)、地铁或出租车。
旅游费用以网上公布为准,具体包括交通费、住宿费、景点门票(第一门票)。晚上20:00至次日早晨7:00之间,如果在某地停留超过6小时,必须住宿,住宿费用不超过200元/天。吃饭等其他费用60元/天。
假设景点开放时间为8:00至18:00。
问题:
根据以上要求,针对如下的几种情况,为该旅游爱好者设计详细的行程表,该行程表应包括具体的交通信息(车次、航班号、起止时间、票价等)、宾馆地址和名称,门票费用,在景点的停留时间等信息。
如果时间不限,游客将十个景点全旅游完,至少需要多少旅游费用?请建立相关数学模型并设计旅游行程表。
如果旅游费用不限,但由于“十一”假期只有7天,为了使游客能尽可能多游览景点,请通过建立相关数学模型,为其设计该旅游行程表。
如果这位游客只有7天的假期时间和5000元的旅游费用,想尽可能多游览景点,请建立相关数学模型并设计旅游行程表。
三、问题假设及符号约定
:
问题一中尽量不考虑以飞机作为交通工具,以节省费用车次或航班在旅行途中的时间。
问题中不考虑城市间的公交线路拥堵等造成的特殊情况。
各城市的公交费用相等,皆为10元。
:
:第个景点或第个景点;(分别代表浙江杭州、江苏常州、山东青岛、北京八达岭、山西祁县、西安兵马俑、湖北武汉、江西九江、安徽黄山、浙江舟山、河南洛阳);
:旅行者的旅游总消费;
:在第个景点的逗留时间;
:在第个景点的总消费;
:旅游者从第个景点到第景点路途所需时间;
:旅游者从第个景点到第景点路途所需的交通费用;
:1表示旅游者直接从第个景点到第景点;0表示其它;
:总的交通费用;
:旅行所花时间
二、问题分析
将该背包客旅游的景点一一描点相连,不难发现旅游范围几乎囊括了大半个中国。,也昭示着传统旅游旺季的来临,各大景点几乎是人满为患。因此旅游者安排一个合理的出行计划就至关重要了。
对于问题一,我们知道在时间不限,费用最少的要求下,黄金周时期高昂的机票让游客可以不用考虑乘坐飞机往来景点所在城市,剩下的便是城际的长途客车和铁路线系统。
生活观察中,我们发现出发地和目的地距离越远,乘坐交通工具所需的费用也就越大:参考网上的数据我们可以得到两两城市之间的大致距离,根据城际间的各种票价,我们发现不管何种交通工具,伴随着距离的增加费用也随之增长。
由此可以推断出,只要求得各大旅游城市距离总和的最小值,依据这个最小值,背包客可以决定旅游城市的先后顺序,参照当天的旅游情况,选择长途客车或铁路系统;同时为了减少费用,可以有选择的安排游客在夜间的长途客车或火车(包括动车高铁)中休息,即可省去在当地住宿的费用。
对于问题二,考虑旅游者费用充足且时间限定,因此我们可以极端的假设。一切都以时间最省为基准。在所有交通工具中飞机时间最省,加上登机时间,飞机较之于长途客车和铁路系统在时间的节省上也远远领先。参照网络中各个目的地之间的航班,确定出城市之间飞行所用时间。由于有些城市对另一城市不存在直达航班,此时我们考虑中途转机(或乘坐火车)到目的地邻近的城市再转动车或客车。在这样的安排下游客可以在7天内尽可能多游览景点。
四、模型的建立与求解
问题一:

根据两个城市之间的公路及铁路,经过数据查询,得到下表各个旅游城市之间的距离:
表一:各旅游城市距离表
起始
目的地
江苏常州
山东青岛
北京八达岭
山西祁县
西安兵马俑
湖北武汉
江西九江
安徽黄山