建模之旅游路线优化问题(2).doc

论文题目论文题目:旅游线路的优化设计模型旅游线路的优化设计模型姓名：姜羽 学号：20090531017 专业：数学与应用数学姓名：付裕 学号：20100551175 专业：数学与应用数学 姓名：赵冰清 学号：20090531046 专业：数学与应用数学目录目录一.摘要.......................................................... 二.问题的重述...................................................... 三.问题的假设.................................................... 四.问题的分析.................................................... 五.建模过程...................................................... 1）问题一..................................................... 1.模型假设................................................... 2.定义符号说明............................................... 3.模型建立................................................... 4.模型求解................................................... 2）问题二..................................................... 1.基本假设................................................... 2.定义符号说明............................................... 3.模型建立................................................... 4.模型求解................................................... 3）问题三..................................................... 1.模型建立...................................................2.模型求解................................................... 3.模型检验与分析............................................. 4).问题四..................................................... 1.模型建立................................................... 2.模型求解................................................. 3.评价方案................................................... 六.模型的评价与改进.............................................. 七.参考文献......................................................一一. .摘要摘要: :本文研究了旅游路线的选取在各种限制情形下的优化问题，通过上网搜索了各地 之间直线距离及旅游路线、车次（航班） 、门票等有关数据，并通过 Lingo 软件处理了 数据和 Matlab 软件绘制出路线图。

全文主要运用了运筹学最短路问题求法、线性规划 法和图论 hamilton 圈等方法，分别建立了旅游路线的优化设计模型问题一：考虑车 费、景点门票费、旅游路线最短等因素，使用优化方法和线性规划法，建立总费用最小的最优路线目标函数问题二：建立新约束条件和目标函数的线性规划模型求解 出最短时间路线，但受“车次的时间衔接”等现实条件约束需对其作适当调整问题 三：使用图论 Hamilton-圈原理，建立费用固定下游览最多景点的最优路线模型，得到 景点数为 7 个的最优路线：徐州→常州→黄山→九江→武汉→西安→洛阳→祁县→徐 州问题四：考虑交通班次有无、时间衔接矛盾等实际条件，利用贪婪法建立模型， 通过求取局部最优解最终确定一条游览 6 个景点的较优路线：徐州→北京→祁县→常 州→武汉→西安→洛阳→徐州关键词关键词：最短路线 线性规划 Hamilton 圈 matlab 及 lingo 软件二二. .问题的重述：问题的重述：随着人们的生活不断提高，旅游已成为提高人们生活质量的重要活动江苏徐州 有一位旅游爱好者打算现在的今年的五月一日早上 8 点之后出发，到全国一些著名景 点旅游，最后回到徐州由于跟团旅游会受到若干限制，他(她)打算自己作为背包客 出游。

他预选了十个省市旅游景点，分别为：徐州，山东(青岛)，北京（八达岭） ，山 西（祁县） ，陕西（西安） ，湖北（武汉） ，江西（九江） ，安徽（黄山） ，浙江（舟山） ， 江苏（常州） ，河南（洛阳） 图见附表 1附表 1 问题：问题： (1) 如果时间不限，游客将十个景点全游览完，至少需要多少旅游费用？请建立相 关数学模型并设计旅游行程表 (2) 如果旅游费用不限，游客将十个景点全游览完，至少需要多少时间？请建立相 关数学模型并设计旅游行程表 (3) 如果这位游客准备 2000 元旅游费用，想尽可能多游览景点，请建立相关数学 模型并设计旅游行程表 (4) 如果这位游客只有 5 天的时间，想尽可能多游览景点，请建立相关数学模型并 设计旅游行程表三三. .问题的假设：、问题的假设：、1、城际交通出行可以乘火车(含高铁)、长途汽车或飞机（不允许包车或包机） ，并 且车票或机票可预订到,且不存在晚点的情况 2、市内交通出行可乘公交车(含专线大巴、小巴)、地铁或出租车忽略乘坐出租 车时经过收费路段所交的费用 3、在每个城市中停留时，难免会遇到等车、堵车等延时情况，在此问题中我们不 做考虑； 4、旅游费用以网上公布为准，具体包括交通费、住宿费、景点门票(第一门票)。

晚上 20：00 至次日早晨 7：00 之间，如果在某地停留超过 6 小时，必须住宿， 住宿费用不超过 200 元/天吃饭等其它费用 60 元/天所有旅馆都未客满，并 且忽略从旅馆到火车站或景点的时间 5、假设景点的开放时间为 8:00 至 18:00在时间的认识上，我们把当天的 8 点至 次日的 8 点作为一天，景点的开放，列车和航班的运营不受天气的影响四四.问题的分析：问题的分析：根据对题目的理解，我们知道问题的求解是在满足每题要求的情况下，要设计一 条最优的路线，从而使旅客花费的钱最少或使用的时间最短或游览的景点数最多所 以我们需要对每一个问题进行分析 问题一的分析问题一的分析： 问题一要求我们设计合适的路线，在不受时间限制的情况下，让旅客花最少的钱 游览完十个景点在满足景点约束的条件下，我们使用货郎担问题解决办法和软件， 设计出一条最优的旅游路线，让旅客花的费用最少 问题二的分析问题二的分析： 问题二改变了目标，即要求我们游览完十个景点后，使旅客花费的时间最短，且 旅游费用不限在满足这些条件下，我们可以选择路线较短的行走或使用较快的交通 工具等，通过分析我们使用 Matlab 软件，设计较优的路线。

那么根据这些我们要设计 一条较优的路线，满足旅客的要求 问题三的分析问题三的分析： 问题三给了我们确定的旅游费用，时间没有具体的限制，要旅客完成尽可能多的 景点游览通过对题目的理解，我们可以选择在满足旅游费用的情况下，用图论法和 Hamiltom-圈法，使用较便宜的交通工具，但同时要满足住宿费的限制 问题四的分析问题四的分析： 问题四要求在五天的时间里，使旅客尽可能的游览较多的景点，在这里旅游的费 用没有确切的限制根据对题目的理解，我们可以选择使用较快的交通工具或选择较 短的路线行走，则我们使用贪婪法对问题进行求解，从而可以设计两条较优的路线， 供旅客选择五．建立模型五．建立模型1）问题一：）问题一：1.符号说明符号说明：,--第 个景点或第个景点， ijij,1,2,......9,10,11i j 分别表示徐州，山东(青岛)，北京（八达岭） ，山西（祁县） ，陕西（西安） ，湖北（武汉） ，江西（九江） ，安徽（黄山） ，浙江（舟山） ，江苏（常州） ，河南（洛阳）--旅客在第 个景点的逗留时间（包括旅客从车站到达景点所花费的行车时间和游览iti景点的停留时间） ；--旅客在第 个景点的门票消费费用；ibi--旅客从第 个景点到第个景点路途中所花费的时间；ijtij--旅客从第 个景点到第个景点所花费的交通费用，不包括路途中的其他费用；ijcij；10ijijx 旅客从第个景点到第个景点其他2.建立模型：建立模型：根据 Tsp 问题中对于巡回的定义在访问一个城市后必须要有一个即将访问的确切城市； 访问城市前必须要有一个刚刚访问过的确切城市，且是一次“巡回”则j，111 2 31011nij ix（i , j，，，，）111 2 31011nij jx（i , j，，，）根据本题的题目，我们可以知道在不受时间限制的情况下，要想游览的景点多， 并且费用较少，经过分析可得，旅游的费用由三部分组成，即路费、门票费用和可能 的费用（包括住宿费用、吃饭的费用等） ，所以我们定义： A—旅客旅游所花费的总费用；--旅客在路上所花费的总费用（组要是路费，其他的不考虑） ；1a--旅客在各景点所花费的门票费；2a--旅客可能花费的费用（住宿费、吃饭的费用等） ；3a所以建立的目标函数为：23iMinAaaa（1）交通总花费因为表示旅客从第 个景点到第个景点所需的交通费用;用表示旅客是否从ijcijijx第 个景点直接到达第个景点的 0---1 变量，由于旅客游览十个景点，且是一次巡回，ij 所以我们得到交通总费用为：11111 11ijij ijac x（2）旅游景点的门票花费用表示旅客在第 个景点的消费，用表示旅客是否从第 个景点直接到达第ibiijxi景点的 0---1 变量，由对本题的分析可知，本题为环形路线，且是一次巡回，所以j 我们得到旅游景点的门票费用为：11112 111 2ijij ijaxbb（3）可能的费用用表示旅客在第 个景点消费费用，其中有住宿费、吃饭费用和其他方面的费用；idi用表示旅客是否从第 个景点到达第景点的 0---1 变量，由对本题的分析可知，本ijxij题为环形路线，且是一次巡回，所以我们得到可能的费用为：11113 111 2ijij ijaxdd综上所述，我们可得总的目标函数为：=++ 23iMinAaaa111111ijij ijc x1111111 2ijij ijxbb1111111 2ijij ijxdd约束条件：①旅游景点数的约束，②0—1 变量约束。

根据题目要求及假设情况，我们用表示旅游的景点数，则我们假设旅游的111111ij ijx景点数为 n(n=2,3,4,5,6,7,8,9,10),因为旅客要游览十个景点，所以 n=11故旅游景 点数约束为：（n=1，2,3,4,5,6,7,8,9,11）11111111ij ijx。