[精品]道路两点间最优化行驶方案

装 订 线摘 要 论文利用动态规划方法建立了交通道路两点之间最优化行使方案的模型。首先利用交通流的知识建立了速度和截面车流量的关系模型。其次，假设车辆的有效行使方向是右向和竖直向，基于此建立有效路径搜索算法并求解得若干条有效路径。为了方便建模，把每个路段的车流量密度当做该路段车辆比例变量，建立截面车辆数模型和路段内的行使速度模型。最后，在每一个路网节点均平衡（流入车辆数等于流出车辆数）的条件下确定出每一条有效路径的总耗时。按照优化方案的目标，要在最短时间内通行，就需要保证每条路径耗时相等。依据此条件建立规划方程组。在约束条件下求解最优化解。1. 问题描述某区域道路网络如图1所示，每条道路等级完全相同，某时间段内，有N辆车要从节点1出发，目的地是节点0（假设该时间段内，路网中没有其它车辆）。在该时间段内，道路截面经过的车辆数越多，车辆在该路段行驶的速度就越慢。（1）确定有效的行驶路径及其算法；（2）确定每条路径上的通过的车辆数，使N辆车从节点1到节点0的总行驶时间最小；注：横向路段长度是纵向路段长度的2倍。 图1 某区域道路网络图2. 问题的初步分析该问题是一个单目标的非线性规划问题。我们需从整个路网系统的角度考虑，寻求整个系统总的出行时间最少的方案。问题的难点主要有以下几处：(1) 车辆流量与车辆速度相互影响，每段路上的流量还会受前面路段的影响，因此难以确定每段路上的最大流量。也就无法用网络最大流模型求解。(2) 如何确定每段路上得速度与流量对整个系统出行时间的影响，从而得到约束条件。(3) 求解非线性规划非常复杂，计算机能否给出准确的最优解。我们先考虑建立问题的非线性规划模型，尝试用Lingo编程求解。3. 模型假设基于问题的求解过程，作出如下假设：（1） 车辆的最大行驶速度为120km/h。（2） 纵向路段长为10km。（3） 每公里最大车辆密度为200辆/km。（4） 源点1是以最大流量向两条路发车。（5） 公路不允许超车，且无岔路口。 4. 符号说明um：车辆的最大速度;P：纵向路段的长度；m：每公里最大车辆密度；Qm：路径上的最大车流量；l1l15：各个路段的长度；v1v15：对应各个路段的车速；xi：第i路段的行车所用的时间；i：第i路段的车流量密度；ni：第i路段的截面车辆数；ai：第i个节点；in(i)qin：节点i流入的全部流量；out(i)qin：节点i流出的全部流量；ximax：第i路段的行车所用最大时间； 5. 模型建立和求解1. 问题一：交通流密度与速度关系的分析和求解（1） 交通流的基本函数：流量：qx,t时刻t单位时间内通过点x的车辆数；密度：x,t时刻t点x处单位长度内的车辆数；速度：ux,t时刻t通过点x的车流速度。（2） 基本函数间的关系上述的三个基本函数之间具有如下的关系： qx,t=ux,tx,t （1）即单位时间内通过的车辆数等于单位长度内的车辆数和车流速度的乘积。其次，经验告诉我们，车流速度u总是随着车流密度的增加而减小。当一辆汽车前面没有汽车时，它将以最大速度行驶，就可以描述为，=0，u=um(最大值)；当车队首尾相接或者造成拥堵的时候，车辆将无法前进，可以记作=m(最大值)时u=0。不妨简化设u是的线性函数，即： u=um1-m （2）根据（1）式可以化简得： q=um1-m （3）表明，流量随着车流密度的增加现增加后减小，当*=m2 时q将取得最大值 qm=14umm （4）2. 问题二：确立有效路径的算法分析为了算法需要，我们对道路网络图作如下的标定：以1号点为原点建立坐标系。右向为x轴的正向，竖直方向为y轴的正向。对于每个点，给出坐标表示。每一行的点具有相同的横坐标，不同的点之间按照从左到右的顺序依次编号。记作a(i,j)。有效路径的定义： 对于网络中的任一点，我们规定只有水平向右或者竖直向下的行驶路径才是有效行使路径。算法描述：对于从原点出发的每一辆车ci当行驶到任意点ai=a(i,j)时，对于下一个点ai+1=a(k,s)有如下论述：ki且sj此时ai到ai+1形成可选有效路径，记作：aiai+1.3. 问题三：分析和求解 为使过程简化，和方便模型建立，我们引入路径车辆比例系数i，并且令其等于每个路段的车流量密度i。即：i=i。 此时，对于截面车辆数ni就等于车流量qi，也就是单位时间里通过截面的车辆数目。可以得到：ni=qi=umi1-im和每个路段车辆行驶速度ui：ui=um1-im4. 问题四：建模和求解根据最优化理论，当系统总的行驶时间最小时，每辆车走着7条路径中的任意一条所用去的时间都是相等的，否则车辆必然会选择时间最短的那条路径，从而使那条路径上的车流密度变大，车速下降，走完路程所需的的时间就会相应上升，进而车辆又会选择其它路径，这一过程必定会达到一种动态平衡，此时我们就可近似认为，走任意一条路径所花的时间是相等的。参考文献1 杨启帆.数学建模竞赛.浙江大学出版社.20052 姜启源.数学模型（第三版）.高等教育出版社.20033 数学建模（原书第四版）Frank R.Giordano 机械工业出版社 (2009-08出版)4 数学建模方法与分析 Mark M.meerschaert 机械工业出版社5 数学建模案例选集. 姜启源、 谢金星 高等教育出版社 (2006-01出版)6