数学建模竞赛论文-基于Hamilton回路算法的最优旅游路线设计问题

《数学建模竞赛论文-基于Hamilton回路算法的最优旅游路线设计问题》由会员分享，可在线阅读，更多相关《数学建模竞赛论文-基于Hamilton回路算法的最优旅游路线设计问题（16页珍藏版）》请在金锄头文库上搜索。

1、题 目 基于 Hamilton 回路算法的最优旅游路线设计问题摘要本文围绕五一黄金周的旅游问题进行了定量评估，对无时限的旅游费用问题、无费用限制的旅游时间问题、有费用限制的旅游质量问题、有时限的旅游质量问题、既有时限又有费用限制的旅游质量问题分别建立了数学模型并设计了旅游行程表，对求解结果进行了分析。问题一放开了对时间的限制，要求设计一条用尽可能少的费用游览十个景点的旅游线路。首先，我们对预选的旅游景点之间消耗的费用和时间进行了分析。由于约束条件只要求费用最低，因此我们从火车和长途汽车班次中选取费用最低的并记录下来建立了最优通行费表。第二步，根据 Hamilton 回路算法的有关方法，以费用为

2、参考量，我们建立了一个适用于本问题最优规划模型。第三步，用 C 语言编写模型的指令，运行后得到最优旅游路线： ； 第四 0 1 10 9 6 7 5 8 4 3 2 0步，综合考虑安排，建立行程表；计算可得最少的总旅行费用为 3101 元。问题二在不限制费用的条件下，要求用最短的时间游览完十个景点。其原理与问题一非常相似，故可用问题一的数学模型及方法，改用景点之间消耗的时间作为参考量，最终得到行程表且知最优旅游路线： ；最短的旅行总时间 0 2 6 1 8 4 3 5 7 9 10 08 天 22 小时 23 分。T问题三要求我们在只有 2000 元旅游费用的条件下游览尽可能多的城市。因此我们

3、引入 01 变量表示是否游览某个景点，从而推出交通费用和景点花费的函数表达式，给出相应的约束条件。这样寻找不同景点数时的最优旅游路线，并计算其总费用。则最优旅游路线的总花费为 1795 元，游览了 7 个景点，是不超过 2000 元的最大值，据此构建行程表。问题四中我们要在 5 天的时间内游览最多的景点并回到徐州。其实质是把问题三中的费用约束条件变成了时间约束，故在此我们依然可用问题三中的模型进行求解，得到最多可游览 6 个景点，耗时 4 天 13 小时（106 小时） ，据此建立行程表。问题五可看做是问题三、四的合并，其中费用和时间都是约束条件。因此我们综合问题三、四中的算法，运用问题三中的

4、模型对其进行全面分析，得到最多可游览 6个景点，并建立行程表。关键词：Hamilton回路算法 C语言 最优旅游路线 01模型11.问题重述随着人们的生活不断提高，旅游已成为提高人们生活质量的重要活动。江苏徐州有一位旅游爱好者打算现在的今年的五月一日早上 8 点之后出发，到全国一些著名景点旅游，最后回到徐州。由于跟团旅游会受到若干限制，他(她)打算自己作为背包客出游。他预选了十个省市旅游景点，如表 1 所示。表 1. 预选的十个省市旅游景点省市 景点名称 在景点的最短停留时间江苏 常州市恐龙园 4 小时山东 青岛市崂山 6 小时北京 八达岭长城 3 小时山西 祁县乔家大院 3 小时河南 洛阳市

5、龙门石窟 3 小时安徽 黄山市黄山 7 小时湖北 武汉市黄鹤楼 2 小时陕西 西安市秦始皇兵马俑 2 小时江西 九江市庐山 7 小时浙江 舟山市普陀山 6 小时假设：(A) 城际交通出行可以乘火车(含高铁)、长途汽车或飞机（不允许包车或包机） ，并且车票或机票可预订到。(B) 市内交通出行可乘公交车(含专线大巴、小巴)、地铁或出租车。(C) 旅游费用以网上公布为准，具体包括交通费、住宿费、景点门票(第一门票)。晚上 20：00 至次日早晨 7：00 之间，如果在某地停留超过 6 小时，必须住宿，住宿费用不超过 200 元/天。吃饭等其它费用 60 元/天。(D) 假设景点的开放时间为 8:00

6、 至 18:00。问题：根据以上要求，针对如下的几种情况，为该旅游爱好者设计详细的行程表，该行程表应包括具体的交通信息(车次、航班号、起止时间、票价等)、宾馆地点和名称，门票费用，在景点的停留时间等信息。(1) 如果时间不限，游客将十个景点全游览完，至少需要多少旅游费用？请建立相关数学模型并设计旅游行程表。(2) 如果旅游费用不限，游客将十个景点全游览完，至少需要多少时间？请建立相关数学模型并设计旅游行程表。(3) 如果这位游客准备 2000 元旅游费用，想尽可能多游览景点，请建立相关数学模型并设计旅游行程表。(4) 如果这位游客只有 5 天的时间，想尽可能多游览景点，请建立相关数学模型并设计

7、旅游行程表。(5) 如果这位游客只有 5 天的时间和 2000 元的旅游费用，想尽可能多游览景点，请建立相关数学模型并设计旅游行程表。22.模型的假设与符号说明2.1 模型的假设五一黄金周正值旅游旺季，各地旅游景点吸引了大批游客前往观光。考虑到该游客的旅游路线跨越区域较大，交通情况尚存在一些不确定因素。为了研究方便，我们给出以下假设：（1）城际交通出行可以乘火车(含高铁)、长途汽车或飞机（不允许包车或包机） ，并且车票或机票可预订到；（2）市内交通出行可乘公交车(含专线大巴、小巴)、地铁或出租车；（3）旅游费用以网上公布为准，具体包括交通费、住宿费、景点门票(第一门票)，晚上 20：00 至次

8、日早晨 7：00 之间，如果在某地停留超过 6 小时，必须住宿，住宿费用不超过 200 元/天。吃饭等其它费用 60 元/天；（4）假设景点的开放时间为 8:00 至 18:00；（5）假设火车、汽车和飞机均正点到达，行程中无事故、无阻碍；（6）假设由火车换乘汽车或者汽车换乘火车的时间很短，忽略不计；（7）假设旅游过程中天气条件良好，不影响行程；（8）由于考虑到在城市内有时需坐公交（大巴）有时需坐出租车，经过近似计算，取每个城市内交通费用为 10 元。2.2 模型的符号说明（1）i,j 表示第 i 个城市（景点）或第 j 个城市（景点） ，i，j=0,1,210，分别表示徐州、常州、青岛、北京

9、、祁县、洛阳、黄山、武汉、西安、九江、舟山；（2） 表示计划行程中的总费用；Z（3） 表示各城市（景点）之间的交通费用的总和， 表示各城市（景点）之间的WijW交通费用；（4） 表示第 i 个城市（景点）内的交通费用；iM（5） 表示第 i 个城市（景点）内的食宿费用；S（6） 表示第 i 个城市的景点门票费用。iG2.2 模型的符号说明（1）i,j 表示第 i 个城市（景点）或第 j 个城市（景点） ，i，j=0,1,210；（2） 表示计划行程中的总费用；Z（3） 表示各城市（景点）之间的交通费用的总和， 表示各城市（景点）之间的WijW交通费用；（4） 表示在景点所在城市的总花费，其中包

10、括 表示第 i 个城市（景点）内的交AiM通费用， 表示第 i 个城市（景点）内的食宿费用， 表示第 i 个城市的景点门票费iS G用， 表示第 i 个城市（景点）内的总费用，故 ；i iiiSA（5） 表示在第 i 个城市（景点）的逗留时间， 表示从第 i 个景点到第 j 个景点路t jt途中所需时间，T 表示本次旅游的总时间；（6） 个 景 点个 到 第游 客 直 接 从 第其 他 ji10ijr33.问题的分析3.1 问题背景的分析根据对题目的理解我们知道，旅游时的总费用包括交通费用、住宿费用和在景点旅游时的费用，在研究确定旅游路线和选用的交通工具后，我们的目标就是在所有的约束条件情况下

11、，求出所求目标的最优解。3.2 对问题一和问题二的分析问题一要求我们在不限定时间的情况下，游览完十个景点，并设计出花费最少的旅游路线，故要尽量选择便宜的交通工具。这里我们的做法是以任意两景点间的交通费用为权值，构建一个完备图；然后利用 Hamilton 回路算法 1计算出近似最佳旅游路线，进而得出最佳方案。问题二实质上是在问题一的基础上改变了约束条件，在不限资金的条件下尽快结束十个景点的旅程。故可用与问题一类似的方法，且应尽量乘坐飞机以减少时间。3.3 对问题三和问题四的分析经过分析，我们可以知道这两个问题所要实现的目标是，使游客在规定的时间内和规定的花费内游览尽可能多的地方。游览的总费用由两

12、部分组成，分别为交通总费用和在旅游景点的花费。对于问题三，花费在 2000 元以内且游览的景点尽量多是该问题的目标。因此，我们的做法是在满足相应的约束条件下，先确定游览的景点数，然后利用 Hamilton 回路算法和 0-1 模型 2计算出在这种情况下的最小花费，这样最终会得出几种旅游路线。问题四中，花费在 2000 元以内的条件改为限定时间为最多 5 天，故可使用与问题三类似的方法求得最优解。3.4 对于问题五的分析问题五是对问题三和问题四进一步综合，要求我们用 5 天的时间和 2000 元的旅游费用游览尽可能多的景点。故可采用与问题三、四类似的方法，进行综合性的求解。4.模型的准备先给 1

13、1 个旅游城市分别进行编号，徐州、常州、青岛、北京、祁县、洛阳、黄山、武汉、西安、九江、舟山分别编为 、 、 、 、 、 、 、 、 、 、 ， 0 1 2 3 4 5 6 7 8 9 10则这 11 个城市和其交通线路构成了一个网络图。这些城市可看作该网络图的节点，这些节点由相应的交通线路相连，节点之间的边就是交通线路。4.2 01 模型44.2.1 目标函数的确立：游览的总费用由 2 部分组成，分别为交通总费用和在旅游景点的花费。我们已经定义：旅游总花费； 交通总费用； 旅游景点的花费；ZWA从而得到目标函数： ZMin（1）交通总花费因为 表示第 i 个景点到第 j 个景点所需的交通费用

14、，而 是判断游客们是ij ijr否从第 i 个景点直接到第 j 个景点的 01 变量，因此我们可以很容易的得到交通总费用为：10ijijir（2）旅游景点的花费因为 表示游客在 i 个景点的总消费， 也可以表示出是否到达过第 i 个和第iAijrj 个景点，而整个旅游路线又是一个环形，因此 实际上将所到景点的10ij jiiA）（花费计算了两遍，从而我们可以得到旅游景点的花费为：10ij jiir2）（从而我们可以得到目标函数为：10i 10ij jiijiji Ar2WrAZMin ）（4.2.2 约束条件:时间约束旅游时间应该不超过 5 天，而这些时间包括在路途中的时间和在旅游景点逗留的时

15、间。因为 表示从第 i 个景点到第 j 个景点路途中所需时间，所以路途中所需的总ijt时间为 ； 表示在第 i 个景点的逗留时间，故在旅游景点的总逗留时间为10ijijrit。因此，总的时间约束为：0ijjiit2）（120tr21tr0ijjii10ijij ）（旅游景点数约束根据假设，整个旅游路线是环形，即最终要回到徐州，因此 即表示旅游的10ijir景点数，这里我们假定要旅游的景点数为 n（n=1，2，3，10） 。因此旅游景点数约束为：），（ 10,r10iji 01 变量约束 3我们可以吧所有的景点连成一个圈，而把妹一个景点看做圈上一个点。对于每个5景点来说，只允许最多一条边进入，同样只允许最多一条边出来，并且有一条边进入就要有一条边出去。因此可得约束：），（ 10,2ji1rjiij 当 i=1 时，因为徐州是出发点，所以 ；j=1 时，因为最终要回到徐州，所以0ijr。综上所述，我们可以得到总的模型为：0ji1r10i 10ij jiijiji Ar2WrAZMin ）（约束条件：），（ ），（ ），（ ）（10,2ji0r1r 10,ji2nr 2tr1tijjiijijij10ijij 0ijjiiij各大景点门票信息 4景点常州市