.2014广州大学华软软件学院“新秀杯”数学建模竞赛承 诺 书我们仔细阅读了广州大学华软软件学院数学建模竞赛章程和广州大学华软软件学院数学建模竞赛参赛规则（以下简称为“竞赛章程和参赛规则”，可从新秀杯咨询群：343759080下载）。我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛章程和参赛规则的，如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛章程和参赛规则，以保证竞赛的公正、公平性。如有违反竞赛章程和参赛规则的行为，我们将受到严肃处理。我们授权广州大学华软软件学院数学建模竞赛组委会，可将我们的论文以任何形式进行公开展示（包括进行网上公示，在书籍、期刊和其他媒体进行正式或非正式发表等）。我们参赛选择的题号是（从A/B/C中选择一项填写）：C 我们的报名参赛队号为：1020 所属学校（请填写完整的全名）：广州大学华软软件学院 参赛队员 (打印并签名) ：1. 林铭锴 2. 王堉权 3. 罗婉瑜 指导教师或指导教师组负责人 (打印并签名)： （论文纸质版与电子版中的以上信息必须一致，只是电子版中无需签名。以上内容请仔细核对，提交后将不再允许做任何修改。如填写错误，论文可能被取消评奖资格。 日期： 2015 年 11 月 24 日赛区评阅编号（由赛区组委会评阅前进行编号）：.2014广州大学华软软件学院“新秀杯”数学建模竞赛编 号 专 用 页赛区评阅编号（由赛区组委会评阅前进行编号）：赛区评阅记录（可供赛区评阅时使用）：评阅人评分备注一. 摘要本文研究的是最佳旅游路线的选择，包括花“最少的时间”“最少的花费”“最短的距离”等，制定一份全面的旅游计划，此问题属于旅游行商问题，我们建立相对应的三个模型，根据不同的路线需求，我们用改良的蚂蚁算法和图表法解决问题，后结合实际情况我们对三个模型进行科学地误差分析，并提出改进的方法。针对问题一，题目给出的是景点和酒店对应的站点信息，以及12条线路的具体信息，要求我们设计一条最优的乘车路线供游客们，以节省他们宝贵的时间，此问题属于旅行商问题。首先，我们通过word查找出12条线路中重复的站点并标出来，得出可换乘的站点以及相对应的路线（见附录）。然后，模拟公交网络图构造无向图进行分析，最后，我们用改进的蚂蚁算法建立程序框图，并进行演绎算出最佳路线。针对问题二三我们为旅客制定出一份最短时间内游览全部景点和制定一个最佳的C地2日游等俩个问题，我们通过资料和图表结合的分析方法，利用建立图表法，让题目的信息更加的具体化，一目了然，利于观察分析。关键词： 路线选择 蚂蚁算法 旅行商问题 图表法 二. 问题重述随着生活水平的提高，旅游逐渐成为最热门的户外活动之一。而在选择旅游方式时，大多数人都喜欢选择自由行，因为自由行是一种更自由、方便的旅游方式。然而想要有好的旅游，制定一个全面的旅游计划则是自由行的关键环节。在此制定计划时还要考虑到游客的普遍需求：1、旅游的费用尽可能最省。2、旅游时间要利用得合理。3、游客对路线的满意程度尽可能提高。4、游客能观赏的景点尽可能最多。因此设计合适的旅游路线方案来满足游客的各种需求，其核心是线路选择的模型与算法，应该从实际情况出发考虑，满足游客的各种不同需求。在这里针对为游客在城市C制定一个全面合理的自由行，而又要涉及交通工具选择、酒店安排以及旅游路线设计。对此需要解决如下问题：1、 在不考虑等车时间的情况下，根据城市C的公交路线、首末班车时间和相邻两班次间隔时间，要求设计出从每个酒店到每个景点的最优乘车路线，以及任意两个景点之间的最优乘车路线。对此还要具体给出V01-V08、V02-V04、H003-H010、H001-H004这几对目的地的最优路线。2、 不考虑住宿情况下，并根据游客的计划，为他设计一个能将所有景点都游览一遍并要求花费的时间最少。对此还要计算出其参观时间加上乘车时间需要多长。3、 根据游客的计划，为其制定一个最佳旅游计划，包括住宿安排和每天的旅游行程，使游客能在2天时间里花尽可能少的费用游览尽可能多的景点。三. 问题分析问题一、问题二和问题三的分析：针对问题一，制定出一份全面的旅游方案是自由行的关键环节。能为游客提供一条合适的公交行程，既能为游客提供方便，也能让游客有一个愉快而又轻松满意的旅程。通过资料分析，花最少的时间的乘车方案和求最短路程的问题可采用蚂蚁算法来解决，除此之外，dijkstra算法和弗洛伊德算法（Floyd）等也是可以求的，不过都存在一定的局限性和不足。但是，蚂蚁算法则可以看作是一个分布式的多agent系统，它在问题空间的多点同时开始进行独立的解搜索，不仅增加了算法的可靠性，也使得算法具有较强的全局搜索能力，在此更适合解决此题，使题目更加通俗易懂，容易解决。针对问题二，该问题需结合相应个景点的参观时间，在辅以公交车的乘车路线，利用改良的图表法建立出一条公交乘车时间短，参观景点日期少的方案。针对问题三，由于要在规定的时间内参观尽可能多的景点，且花费少。则需与景点的价格相结合，利用问题二所建的方法，最终得到每一天不同景点的不同组合方案。问题背景的理解：随着生活水平的提高，旅游逐渐成为最热门的户外活动之一。选择自由行的人也越来越多。而在旅游的时候，人们往往会想，怎样才能花最少的钱游最多的地方，怎样的路线才能够使自己最满意。这样就要求我们建立适当的数学模型来解决这些问题。根据对题目的理解我们可以知道，旅游的总费用包括交通费用和在景点游览时的费用，而在确定了要游览的景点的个数后，所以我们的目标就是在满足所有约束条件的情况下，求出成本的最小值。问题一、问题二和问题三的分析：四. 模型假设1、 游客根据不同需求，对路线选择具有自主权。2、 车辆的服务总体效率和服务质量相同，不影响游客对车辆的选择。3、 游客转站过程正常进行，忽略其他外界意外因素对转站时间的影响。4、 车辆运营正常，不存在发生意外事故而影响游客路线选择的情况。5、 游客活动的范围只在所给的区域内6、 游客满意度要求相对较高，则换车次数应尽可能少，现假设城区内游客 平均换乘1次货2次即可抵达目的地。7、 假设在简化问题过程中，附录所停供的数据真实有效，符合实际情况。五. 符号说明：Ti：任意两个景点的距离 t：时间S: 费用六. 模型的建立和求解6.1.问题一的模型建立和解决a. 模型的准备公交车网络图 公交车网络图其实是一个无向连通图，但是它又有特殊性。在公交车网络图中，一个顶点表示一个站点，顶点之间的边表示两个站点之间的公交连线。显然存在数据库中的任意两个站点都是可以找到一辆公共汽车到达的，或者通过转车到达，所以公交车网络图它必然是连通图，如图一所示。 A B C D E 图一 b.公交网络的描述 公交网络是由公交道路和相应的公交车线路组合而成的。本为为研究方便，结点仅指公交站点，而道路边指有某条公交线经过的相邻站点间道路，是一个经抽象化的概念。公交道路网用简单图G表示，而结点集V(G)是所有公交站点的集合。公交车线网络有特殊表示方式，公交车=（k，V(G),vi为上面站点数，此为旅游环线，k为2） (1) 式(1)表示公交车可从出发经过， 。所有公交车行成公交车线网络 L:L=|i=1，2为网络中车线数 模型建立和求解 设现在有一游客从起点站前往终点 ，其中i，sn（n表示最长站点数），r，j l（l表示总路线），则游客到达终点可能会遇到以下几种情况，用h表示换乘次数 h= 当h3时， _D_Dd_D8Dd8 本文将换乘次数考虑为零次，一次，两次的情况，搜索从起始站到终点站的线路（见附录一，二），再比较确定乘客需求的最优方案。下图为本文求解的思路 曲线表示YES，得出方案 箭头表示NO，继续搜索由此，我们可以给问题一所涉及的问题列出最优的乘车路线：a. V01-V08的最优路线V01(S0045)-S0903-S0901-S0925-S0923-S0921-H009(S0869)-S0763-V08(S0761)b. V02-V04的最优路线V02(S1171)-S1169-S1115-S1117-V04(S1353)c. H003-H010的最优路线H003(S0219)-S0223-S0217-S0215-S0213-S0513-S0515-S0517-S0521-S0757-S0759-S0761-S0763-H009(S0869)-S0025-S0915-0475-H010(S1157)d. H001-H004的最优路线H001(S1123)-S1121-V04(S1353)-S0045-S0903-S0901-S0925-S0923-S0921-S0869-S0025-S0915-S0475-S0475-S1157-S1233-S1231-S1229-S1227-S1225-H004(S1099)6.2 问题二：游客最短时间游览全部景点的问题任意两个景点之间的最短乘车时间Ti（相邻两个景点之间不存在第三个景点，若没有则不表示出来）：V01-VO257分钟VO1-VO335分钟VO1-V045分钟VO1-VO5VO1-VO615分钟VO1-VO7VO1-VO836分钟VO2-VO3108分钟VO2-VO415分钟VO2-