2015年五一数学建模联赛题目A.pdf
立即下载
樱花弄๑•ั็•็
2024-04-24
路径
行驶
时间
交通
分钟
车辆
算法
假设
平均
路段
93.7 KB
A 题 不确定性条件下的最优路径问题
目前，交通拥挤和事故正越来越严重的困扰着城市交通。随着我国交通运输
事业的迅速发展，交通“拥塞”已经成为很多城市的“痼疾”。在复杂的交通环境下，
如何寻找一条可靠、快速、安全的最优路径，已经成为所有驾驶员的共识。
传统的最优路径问题的研究大多数是基于“理想”的交通状况下分析的，即：
假设每条路段上的行驶时间是确定的。在这种情况下，最优路径就是行驶时间最
短的路径，可以用经典的最短路径算法来搜索(例如 Dijkstra 最短路径算法)。目
前的车辆路径导航系统也大都是基于这种理想的状况下的最优路径算法，寻找行
驶时间最短的路径。事实上，由于在现实生活中，会受到很多不确定性因素的影
响，例如：交通事故、恶劣天气、突发事件等，车辆的行驶时间存在着不确定性。
第一问：如图 1所示的交通网络，起点：中国矿业大学，终点：徐州火车站。假
设车辆的行驶时间是随机变量。如果走绕城快速路，平均 33分钟到达，虽然路
程远，但是很少发生堵车，所以行驶时间的波动很小，标准差只有 1分钟；如果
走市区道路，平均 30分钟到达，虽然路程近，但是市区经常发生堵车，所以行
驶时间的波动很大，标准差高达 15分钟。如果用传统的最优路径算法，应该选
市区道路，因为平均时间短。在现实中，为了准时到达目的地，驾驶员通常会选
择路程稍远的绕城快速路。
起点 终点
市区道路
均值 30分钟，标准差 15分钟
中国矿业大学 徐 州 火 车
站
绕城快速路
均值 33分钟，标准差 1分钟
图 1. 示例交通网络
对于一般的交通网络，假设已知每条路段行驶时间的均值和标准差，请建立数学
模型，定量的分析车辆行驶时间的不确定性，然后给出在不确定性条件下车辆从
起点到终点的最优路径的定义和数学表达式，将此模型应用到图 1的例子中会选
择哪条道路。提示：(1) 传统的最优路径可以看成是平均行驶时间最短的路径，
本题中的最优路径不仅要考虑平均行驶时间，而且还要考虑不确定性条件下车辆
准时到达终点的可靠性等因素; (2) 假设车辆在每条路段上的行驶时间是随机变
量，这里的“路段”相当于网络图中的“边”。
第二问：根据第一问的定义，假设已知每条路段行驶时间的均值和标准差，设计
算法搜索最优路径，并将该算法应用到具体的交通网络中
路径/行驶/时间/交通/分钟/车辆/算法/假设/平均/路段/
路径/行驶/时间/交通/分钟/车辆/算法/假设/平均/路段/
-->