我的建模题目

何刚·空军勤务学院
2015-05-01
阅读数2281

A 题不确定性条件下的最优路径问题
目前,交通拥挤和事故正越来越严重的困扰着城市交通。随着我国交通运输
事业的迅速发展,交通“拥塞”已经成为很多城市的“痼疾”。在复杂的交通环境下,
如何寻找一条可靠、快速、安全的最优路径,已经成为所有驾驶员的共识。
传统的最优路径问题的研究大多数是基于“理想”的交通状况下分析的,即:
假设每条路段上的行驶时间是确定的。在这种情况下,最优路径就是行驶时间最
短的路径,可以用经典的最短路径算法来搜索(例如Dijkstra 最短路径算法)。目
前的车辆路径导航系统也大都是基于这种理想的状况下的最优路径算法,寻找行
驶时间最短的路径。事实上,由于在现实生活中,会受到很多不确定性因素的影
响,例如:交通事故、恶劣天气、突发事件等,车辆的行驶时间存在着不确定性。
第一问:如图1 所示的交通网络,起点:中国矿业大学,终点:徐州火车站。假
设车辆的行驶时间是随机变量。如果走绕城快速路,平均33 分钟到达,虽然路
程远,但是很少发生堵车,所以行驶时间的波动很小,标准差只有1 分钟;如果
走市区道路,平均30 分钟到达,虽然路程近,但是市区经常发生堵车,所以行
驶时间的波动很大,标准差高达15 分钟。如果用传统的最优路径算法,应该选
市区道路,因为平均时间短。在现实中,为了准时到达目的地,驾驶员通常会选
择路程稍远的绕城快速路。
起点终点
市区道路
均值30 分钟,标准差15 分钟
中国矿业大学徐州火车

绕城快速路
均值33 分钟,标准差1 分钟
图1. 示例交通网络
对于一般的交通网络,假设已知每条路段行驶时间的均值和标准差,请建立数学
模型,定量的分析车辆行驶时间的不确定性,然后给出在不确定性条件下车辆从
起点到终点的最优路径的定义和数学表达式,将此模型应用到图1 的例子中会选
择哪条道路。提示:(1) 传统的最优路径可以看成是平均行驶时间最短的路径,
本题中的最优路径不仅要考虑平均行驶时间,而且还要考虑不确定性条件下车辆
准时到达终点的可靠性等因素; (2) 假设车辆在每条路段上的行驶时间是随机变
量,这里的“路段”相当于网络图中的“边”。
第二问:根据第一问的定义,假设已知每条路段行驶时间的均值和标准差,设计
算法搜索最优路径,并将该算法应用到具体的交通网络中,用计算结果验证算法
的有效性。如果可能的话,从理论上分析算法的收敛性、复杂性等性质。
第三问:在现实的交通网络中,某个路段发生了交通拥堵,对上游或者下游路段
的交通状况有很大的影响,从而导致了交通路段之间的行驶时间有一定的相关
性,这种相关性情况很复杂,其中一个典型的例子如下:下游路段发生交通拥堵
使车辆减速或者排队,导致上游路段发生拥堵。请建立数学模型描述这种交通路
段之间行驶时间的相关性,并将这种相关性应用到第一问和第二问的最优路径搜
索问题中,并设计算法解决考虑相关性的最优路径搜索问题,给出算例验证算法
的有效性。如果可能的话,从理论上分析算法的收敛性、复杂性等性质。提示:
这里的相关性,可以从空间和时间的两个方面考虑。空间相关性:同一个时间段
(例如7:00-8:00 之间),路段a 和路段b 的相关性。时间相关性:对于路段a,不
同时间段的相关性,例如7:00-8:00 和8:00-9:00 之间的相关性。当然,也可以两
种相关性同时考虑。
第四问:从不确定性条件下交通网络的实际情况出发,在合理假设下,进一步完
善前三问的数学模型和相关算法。或者,提出一种或多种与前三问不同的最优路
径的定义方法,建立相关的数学模型并设计算法,应用数值算例验证算法的有效
性。如果可能的话,从理论上分析算法的收敛性、复杂性等性质。
说明:本题中的所涉及的算例最好能采用真实的交通网络数据,也可以使用自己
假设的数据,交通网络的规模越大越好。

本文由 何刚 授权 赛氪网 发表,并经赛氪网编辑。转载此文章须经作者同意,并请附上出处(赛氪网)及本页链接。原文链接https://www.saikr.com/a/1445
收藏
分享
别默默的看了,快来和大家聊聊吧,登录后发表评论~ 登录 立即注册
打赏
何刚
打赏金额(金额:¥0)
给Ta留言
赏金已入袋,多谢!(*^__^*)
温馨提示

非常抱歉!本站不支持旧版本IE浏览器~~建议使用IE10/IE11/Chrome/Firefox/Safari等高级浏览器浏览。

温馨提示
温馨提示
帮助与反馈

热门问题

0
在线咨询