2011年第八届苏北数学建模联赛
承 诺 书
我们仔细阅读了第八届苏北数学建模联赛的竞赛规则。
我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与本队以外的任何人（包括指导教师）研究、讨论与赛题有关的问题。
我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。
我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们愿意承担由此引起的一切后果。
我们的参赛报名号为：
参赛组别（研究生或本科或专科）：本科
参赛队员 (签名) ：
队员2：
队员3：
获奖证书邮寄地址：
队员1：
2011年第八届苏北数学建模联赛
编 号 专 用 页
参赛队伍的参赛号码：（请各个参赛队提前填写好）：
竞赛统一编号（由竞赛组委会送至评委团前编号）：
竞赛评阅编号（由竞赛评委团评阅前进行编号）：
2011年第八届苏北数学建模联赛
题 目 基于Hamilton回路算法的最优旅游路线设计问题
摘要
本文围绕五一黄金周的旅游问题进行了定量评估，对无时限的旅游费用问题、无费用限制的旅游时间问题、有费用限制的旅游质量问题、有时限的旅游质量问题、既有时限又有费用限制的旅游质量问题分别建立了数学模型并设计了旅游行程表，对求解结果进行了分析。
问题一放开了对时间的限制，要求设计一条用尽可能少的费用游览十个景点的旅游线路。首先，我们对预选的旅游景点之间消耗的费用和时间进行了分析。由于约束条件只要求费用最低，因此我们从火车和长途汽车班次中选取费用最低的并记录下来建立了最优通行费表。第二步，根据Hamilton回路算法的有关方法，以费用为参考量，我们建立了一个适用于本问题最优规划模型。第三步，用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?○0；最短的旅行总时间T?8天22小时23分。
问题三要求我们在只有2000元旅游费用的条件下游览尽可能多的城市。因此我们引入0—1变量表示是否游览某个景点，从而推出交通费用和景点花费的函数表达式，给出相应的约束条件。这样寻找不同景点数时的最优旅游路线，并计算其总费用。则最优旅游路线的总花费为1795元，游览了7个景点，是不超过2000元的最大值，据此构建行程表。
问题四中我们要在5天的时间内游览最多的景点并回到徐州。其实质是把问题三中的费用约束条件变成了时间约束，故在此我们依然可用问题三中的模型进行求解，得到最多可游览6个景点，耗时4天13小时（106小时），据此建立行程表。
问题五可看做是问题三、四的合并，其中费用和时间都是约束条件。因此我们综合问题三、四中的算法，运用问题三中的模型对其进行全面分析，得到最多可游览6个景点，并建立行程表。
关键词：Hamilton回路算法 C语言 最优旅游路线 0—1模型
1.问题重述
随着人们的生活不断提高，旅游已成为提高人们生活质量的重要活动。江苏徐州有一位旅游爱好者打算现在的今年的五月一日早上8点之后出发，到全国一些著名景点旅游，最后回到徐州。由于跟团旅游会受到若干限制，他(她)打算自己作为背包客出游。他预选了十个省市旅游景点，如表1所示。
表1. 预选的十个省市旅游景点 省市 景点名称 在景点的最短停留时间 江苏 常州市恐龙园 4小时 山东 青岛市崂山 6小时 北京 八达岭长城 3小时 山西 祁县乔家大院 3小时 河南 洛阳市龙门石窟 3小时 安徽 黄山市黄山 7小时 湖北 武汉市黄鹤楼 2小时 陕西 西安市秦始皇兵马俑 2小时 江西 九江市庐山 7小时 浙江 舟山市普陀山 6小时
假设：
(A) 城际交通出行可以乘火车(含高铁)、长途汽车或飞机（不允许包车或包机），并且车票或机票可预订到。
(B) 市内交通出行可乘公交车(含专线大巴、小巴)、地铁或出租车。
(C) 旅游费用以网上公布为准，具体包括交通费、住宿费、景点门票(第一门票)。晚上20：00至次日早晨7：00之间，如果在某地停留超过6小时，必须住宿，住宿费用不超过200元/天。吃饭等其它费用60元/天。 (D) 假设景点的开放时间为8:00至18:00。
问题：
根据以上要求，针对如下的几种情况，为该旅游爱好者设计详细的行程表，该行程表应包括具体的交通信息(车次、航班号、起止时间、票价等)、宾馆地点和名称，门票费用，在景点的停留时间等信息。
(1) 如果时间不限，游客将十个景点全游览完，至少需要多少旅游费用？请建立相关数学模型并设计旅游行程表。
(2) 如果旅游费用不限，游客将十个景点全游览完，至少需要多少时间？请建立相关数学模型并设计旅游行程表。
(3) 如果这位游客准备2000元旅游费用，想尽可能多游览景点，请建立相关数学模型并设计旅游行程表。
(4) 如果这位游客只有5天的时间，想尽可能多游览景点，请建立相关数学模型并设计旅游行程表。
(5) 如果这位游客只有5天的时间和2000元的旅游费用，想尽可能多游览景点，请建立相关数学模型并设计旅游行程表。
1
2.模型的假设与符号说明
2.1模型的假设
五一黄金周正值旅游旺季，各地旅游景点吸引了大批游客前往观光。考虑到该游客的旅游路线跨越区域较大，交通情况尚存在一些不确定因素。为了研究方便，我们给出以下假设：
（1）城际交通出行可以乘火车(含高铁)、长途汽车或飞机（不允许包车或包机），并且车票或机票可预订到；
（2）市内交通出行可乘公交车(含专线大巴、小巴)、地铁或出租车；
（3）旅游费用以网上公布为准，具体包括交通费、住宿费、景点门票(第一门票)，晚上20：00至次日早晨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,2·······10； （2）Z表示计划行程中的总费用；
（3）W表示各城市（景点）之间的交通费用的总和，Wij表示各城市（景点）之间的交通费用；
（4）A表示在景点所在城市的总花费，其中包括Mi表示第i个城市（景点）内的交通费用，Si表示第i个城市（景点）内的食宿费用，Gi表示第i个城市的景点门票费用，
Ai表示第i个城市（景点）内的总费用，故Ai?Mi?Si?Gi；
（5）ti表示在第i个城市（景点）的逗留时间，tij表示从第i个景点到第j个景点路
途中所需时间，T表示本次旅游的总时间； （6）rij?
?10游客直接从第i个到第j个景点其他
3.问题的分析
3.1 问题背景的分析
根据对题目的理解我们知道，旅游时的总费用包括交通费用、住宿费用和在景点旅游时的费用，在研究确定旅游路线和选用的交通工具后，我们的目标就是在所有的约束条件情况下，求出所求目标的最优解。 3.2对问题一和问题二的分析
问题一要求我们在不限定时间的情况下，游览完十个景点，并设计出花费最少的旅游路线，故要尽量选择便宜的交通工具。这里我们的做法是以任意两景点间的交通费用为权值，构建一个完备图；然后利用Hamilton回路算法[1]计算出近似最佳旅游路线，进而得出最佳方案。
问题二实质上是在问题一的基础上改变了约束条件，在不限资金的条件下尽快结束十个景点的旅程。故可用与问题一类似的方法，且应尽量乘坐飞机以减少时间。 3.3对问题三和问题四的分析
2
第八届苏北地区数学建模联赛B题一等奖论文
