数学建模最优路径设计

《数学建模最优路径设计》由会员分享，可在线阅读，更多相关《数学建模最优路径设计（18页珍藏版）》请在金锄头文库上搜索。

1、高教社杯全国大学生数学建模竞赛承 诺 书 我们仔细阅读了全国大学生数学建模竞赛章程和全国大学生数学建模竞赛参赛规则（如下简称为“竞赛章程和参赛规则”，可从全国大学生数学建模竞赛网站下载）。我们完全明白，在竞赛开始后参赛队员不能以任何方式（涉及电话、电子邮件、网上征询等）与队外的任何人（涉及指引教师）研究、讨论与赛题有关的问题。我们懂得，抄袭别人的成果是违背竞赛章程和参赛规则的，如果引用别人的成果或其她公开的资料（涉及网上查到的资料），必须按照规定的参照文献的表述方式在正文引用处和参照文献中明确列出。我们郑重承诺，严格遵守竞赛章程和参赛规则，以保证竞赛的公正、公平性。如有违背竞赛章程和参赛规则的

2、行为，我们将受到严肃解决。我们授权全国大学生数学建模竞赛组委会，可将我们的论文以任何形式进行公开展示（涉及进行网上公示，在书籍、期刊和其她媒体进行正式或非正式刊登等）。 我们参赛选择的题号是（从A/B/C/D中选择一项填写）： A 我们的参赛报名号为（如果赛区设立报名号的话）： 所属学校（请填写完整的全名 参赛队员 (打印并签名) ：1 2 指引教师或指引教师组负责人 (打印并签名)： （论文纸质版与电子版中的以上信息必须一致，只是电子版中无需签名。以上内容请仔细核对，提交后将不再容许做任何修改。如填写错误，论文也许被取消评奖资格。） 日期： 7 月 27 日赛区评阅编号（由赛区组委会评阅迈进

3、行编号）：高教社杯全国大学生数学建模竞赛编 号 专 用 页赛区评阅编号（由赛区组委会评阅迈进行编号）：赛区评阅记录（可供赛区评阅时使用）：评阅人评分备注全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅迈进行编号）：从成都工业学院到西南交通大学最优途径设计摘要 本文对目前生活中行车时间的不拟定性进行了分析，并给出了最优途径的定义，即：行车所需盼望时间最短且该路段行车时间的原则差最小。在将时间盼望值和时间原则差值两个决策变量合成为一种决策变量时，为消除不同指标带来的不可公度性，我们对这两个指标进行了无量纲化。 对于问题一，建立双目的优化模型，给出最优途径的定义和数学体现式

4、。将这两个目的相加合成单目的。运用MATLAB编程求解，将所建模型应用到例子中，得出的结论是：选择道路A。 对于问题二，在问题一定义的最优途径的基本上，建立图论模型，应用Dijkstra算法，运用MATLAB编程，得出最优途径选择成果为：成都工业学院CKG西南交通大学。 对与问题三，结合时间和空间上的有关性，采集足够多的时刻的车流速度，用神经网络算法可以拟合出该条路时刻有关车流速度的函数，建立图论模型分析时间和空间上的有关性。核心词：多目的优化 图论模型 Dijkstra算法 1、问题重述 随着国内交通运送事业的迅速发展，交通拥挤和事故正越来越严重的困扰着都市交通。在复杂的交通环境下，寻找一条

5、可靠、迅速、安全的最优途径，已成为所有驾驶员的共识。老式最优途径问题的研究大多是基于“抱负”交通状况下分析的，景点的最优途径算法都是假设每段路的行驶时间是拟定的。但是由于在现实生活中，行车会受到诸多不拟定性因素的影响，例如：交通事故、恶劣天气、突发事件等，车辆的行驶时间存在着不拟定性。基于这种不拟定性，讨论如下问题： 1.建立数学模型，定量的分析车辆行驶时间的不拟定性，然后给出在不拟定性条件下车辆从起点到终点的最优途径的定义和数学体现式 。并将此模型运用到图1例子中会选哪条路。2.根据第一问的定义，设计算法搜索最优途径，并将该算法应用到具体交通网络中，验证算法的有效性。3.交通路段之间的行驶时

6、间的有关性分析。时间上的有关性，对于相似路段不同步间段的有关性；空间上的有关性，相似时间段不同路段的有关性。或者将时间和空间上的有关性综合起来考虑。 2、模型假设1.假设题目所给数据是在大量实验记录后得到的，数据真实可靠；2.假设题目给出数据所用的样本容量大小相似；3.假设从起点到到终点时间消耗不超过1小时；4.假设同一路段上下行的盼望时间和原则差时间相似；5.假设各不同路段的盼望时间和原则差时间相对独立。3、变量阐明 ：表达从起点（成都工业学院）到终点（西南交通大学）盼望时间； ：表达从起点（成都工业学院）到终点（西南交通大学）原则差时间； ：类指标中的第个指标； ：类指标的平均值； ：无量

7、纲化后的指标； ：指标权重，变化盼望时间和原则差时间重要性的系数； ：无量纲化后的指标； ：无量纲化后的指标； ：盼望时间和原则差时间两个指标合成的指标； ：顶点集，即题图给出的AK的点； ：无向弧集； ：无向弧上的盼望时间； ：无向弧上的原则差时间； :表达从起点到终点盼望时间； :表达0，1变量，取1时，表达所选途径通过了节点到节点的路段；取0时，表达所选途径没有通过节点到节点的路段。 ：从起点到终点原则差时间，其中0表达起点位置标号，k表达终点位置标号； ：是第种指标的第个量无量纲化后的量; ：第种指标的第个量; 表达第种指标的平均数; :从第个节点到第个节点的盼望时间; :从第个节点到

8、第个节点的原则差时间; :无量纲化后的量; :无量纲化后的量; :所有的路段的盼望时间平均值; :所有的路段的原则差时间平均值; :由盼望时间和原则差时间两个指标合成的指标。 ：第个节点到第个节点的那段街的有关时刻的函数值，即速度。 ：表达起点0到点的最短消耗时间。4、模型准备4.1对最优途径的理解 影响实际问题的因素诸多，要解决实际问题就要建立合适的数学模型，即要把建模对象所波及的次要因素忽视掉，否则所得模型会由于构造太复杂而失去可解性同步又不能把与实质有关的因素忽视掉，而导致所得模型由于不能足够对的反映实际状况而失去可靠性。因此需要对实际问题进行抽象、简化、拟定变量和参数，并应用某些“规律

9、”建立起变量、参数间拟定的数学模型。 影响路线选择的因素诸多，譬如瞬时车流量、与否有交通事故、车辆状况等，而实际要解决的是从成都工业学院到西南交通大学的时间最省途径，因此车流量和途径长度成为影响解决本问题的重要因素，而与否有交通事故发生和车辆状况等次要因素均可忽视掉。 因此最优途径可定义为：实际行车途径所需盼望时间最短且该途径行车时间的总原则差最小。5、模型的建立与求解5.1问题1模型的建立与求解5.1.1建模思路 问题1规定给出在不拟定条件下车辆从起点到终点最优途径的定义和数学体现式并将此模型应用于例子中，阐明选择哪条路。建立双目的优化模型，再建立优化模型，将两个目的综合起来考虑，使之变为一

10、种目的。对于问题一和问题二我们在不考虑时间有关性和空间有关性的状况下，我们假设各路段行车的原则差时间互相独立，由概率的基本知识可以得知，多种随机变量互相独立，多种随机变量和的原则差就等于各自原则差的和。因此在解决问题一和问题二的时候，在假设原则差时间是互相独立的状况下，我们将各原则差时间相加作为和的原则差是合理的解决方式。5.1.2模型建立 最优途径的定义：行车所需盼望时间最短且该路段行车时间的原则差最小，考虑建立双目的决策：目的：总的盼望时间最短，即：(1) 表达从起点到终点盼望时间。目的二：时间波动要小，即规定这个途径的总原则差要小。(2)表达从起点到终点原则差时间。5.1.3模型求解 对

11、于多目的，这里用相加合成为单目的，在这之前要进行无量纲化，这里用均值法无量纲化法，公式如下：(3) 是类指标中的第个指标。是类指标的平均值，是无量纲化后的指标。 通过无量纲后，就可以转换成单目的。(4) 是指标权重，变化盼望时间和原则差时间重要性的系数，对于不同的人看重的不同，因此这里分别取0.2,0.5和0.8。是无量纲化后的指标，是无量纲化后的指标，是由盼望时间和原则差时间两个指标合成的指标。 合成的单目的就为：(5)取0.2时，成果：选择道路A.取0.5时，成果：选择道路A.取0.8时，成果：选择道路B.5.2问题2模型的建立与求解5.2.1建模建立 为了可以尽量迅速达到目的地，因此规定

12、这条途径总盼望时间要短，又考虑到不拟定因素的影响，因此规定期间的波动最小，即这条途径原则差要小。目的：总的盼望时间最短，即：(6) 表达从起点到终点盼望时间，表达起点位置标号，k表达终点位置标号。(7) 表达节点到节点的路段盼望时间，表达0，1变量，取1时，表达所选途径通过了节点到节点的路段；取0时，表达所选途径没有通过节点到节点的路段。 目的二：时间波动要小，即规定这个途径的原则差要小。(8)表达从起点到终点原则差时间，其中表达起点位置标号，k表达终点位置标号。(9)这里表达节点到节点的路段原则差时间，表达0，1变量，取1时，表达所选途径通过了节点到节点的路段；取0时，表达所选途径没有通过节

13、点到节点的路段。约束一：每个节点最多可以进入一次且最多只可以出去一次。(10)(11)约束二：由于这里的途径不必要形成一种圈，因此起点只能出去一次，即进入零次，终点只能进入一次，即出去零次。(12)(13) 这里表达起点位置标号，k表达终点位置标号，表达从第个节点与否到起点的0,1变量，取0时表达第个节点不到起点，取1时表达第个节点要到起点，表达从终点与否到第个节点的0,1变量，取0时表达从终点不到第个节点，取1时表达从终点要到第个节点。 综上：(14)(15)(16)(17)(18)5.2.2模型优化 对于多目的问题难以求解，通过一定关系把多目的合成一单目的，在这之前，先对这两个指标进行无量纲化，采用均值法来无量纲化。即：(19) 是第种指标的第个量无量纲化后的量，表达第种指标的第个量，表达第种指标的平均数。通过以上无量化公式可对，无量纲化，即：(20)(21) 是表达从第个节点到第个节点的盼望时间，是表达从第个节点到第个节点的