2023年12月24日发(作者：江苏学测数学试卷小学)

哈尔滨工业大学：苗鑫，高丽丽，李化南A题公路行驶时间估计与路线优化研究哈尔滨工业大学：苗鑫，高丽丽，李化南0问题概述对于出行者来说，对公路上行驶时间的估计是一个至关重要的问题。在美国，某些六车道公路的两侧安装有检测器，在不考虑行驶车辆车道变换的情况下，可以把整条道路简化成单一的车行道进行研究，如下图所示,图中方形代表检测器。636m417m522m475mtraveldirectionDetector1Detector2Detector3Detector4Detector5检测器可以对道路上行使的车辆进行全天观测，并以20秒为计数单位来报告平均车速而且可以将数据实时更新。A题中的表格仅提供了每两钟的后20秒的观测数据，下面结合交通工程中的交通特性指标，对这些数据进行统计分析，从而得出公路上的车辆运行特性并从中寻求规律。1公路上车辆行驶特性分析根据交通工程中的车速特性分布理论，行车速度和交通量一样，也是随机变量。对车速进行统计分析，一般要借助车速分布直方图、车速频率、累计频率分布曲线。表征车速统计分布特性的特征车速常用：中位车速：也称50%位车速，是指在该路段上该速度一下行驶的车辆属于在该速度已上行驶的车辆数相等。85%位车速：在该路段行驶的所有车辆中，有85%的车辆在此速度以下行驶，交通管理部门常以此速度作为某些路段的限制车速。15%位车速：与上述类似，在高速公路和快速道路上，为了行车安全，减少阻塞排队想象，保证交通流畅通，要规定低速限制，因此15%位车速测定是非常重要的。85%位车速与15%位车速之差反映了该路段上的车速波动幅度。根据题目中所给的临界条件，交通拥挤与非拥挤以速度来划分，临界速度值为50英里/小时，小于此速度则认为交通流进入拥挤状态。对表中已知观测数据进行统计分析，可得到下列图表：2005年全国研究生数学建模竞赛一等奖1

哈尔滨工业大学：苗鑫，高丽丽，李化南表1车速统计表Sensor1speedNMeanMedianVarianceMaximumPercentiles155085ValidMissing100054.1856.0044.4726445.0056.0060.00Flow110008.878.7511.69517.14.708.7512.97Sensor2Speed100057.8763.00268.6607856.0063.0066.85Flow210008.1368.35011.61315.34.4308.35012.000Sensor3speed100051.1961.50450.6007221.1561.5066.00Flow310007.8617.6008.63816.04.5457.60011.000Sensor4speed100028.0423.00515.514723.0023.0058.00Flow410008.238.259.644155.308.2511.47Sensor5speed100042.4153.00424.0836616.1553.0063.00Flow510009.329.408.91916.96.029.4012.67通过对表1的整理可得到各个检测器处的观测统计分析结果如下表：表2特征车速分析整理表监测器1均值方差最大值15%位车速中位车速85%位车速54.1844.4726445.0056.0060.00流量18.8711.69517.1监测器257.87268.6607856.0063.0066.85流量28.13611.61315.3监测器351.19450.6007221.1561.5066.00流量37.8618.63816.0监测器428.04515.514723.0023.0058.00流量48.239.64415监测器542.41424.0836616.1553.0063.00流量59.328.91916.9车速频率统计表如下：表3-1检测器1处的车速频率统计表FrequencyValid35383946484952005年全国研究生数学建模竞赛一等奖24272962Percent1.01.01.02.01.05.02.01.02.02.01.02.04.02.07.02.09.06.0ValidPercent1.01.01.02.01.05.02.01.02.02.01.02.04.02.07.02.09.06.0CumulativePercent1.02.03.05.06.011.013.014.016.018.019.021.025.027.034.036.045.051.0

哈尔滨工业大学：苗鑫，高丽丽，李化南57585960616264Total99.011.013.08.03.01.04.0100.09.011.013.08.03.01.04.0100.060.071.084.092.095.096.0100.0表3-2检测器2处的车速频率统计表FrequencyValid4782535657585966676869707178Total21136221100Percent2.01.02.01.02.01.01.02.01.01.02.03.01.05.04.02.015.08.013.07.011.01.03.06.02.02.01.0100.0ValidPercent2.01.02.01.02.01.01.02.01.01.02.03.01.05.04.02.015.08.013.07.011.01.03.06.02.02.01.0100.0CumulativePercent2.03.05.06.08.09.010.012.013.014.016.019.020.025.029.031.046.054.067.074.085.086.089.095.097.099.0100.0表3-3检测器3处的车速频率统计表FrequencyValid23789102005年全国研究生数学建模竞赛一等奖5111113Percent5.01.01.01.01.01.0ValidPercent5.01.01.01.01.01.0CumulativePercent5.06.07.08.09.010.0

哈尔滨工业大学：苗鑫，高丽丽，李化南6272938394259666768697072Total21.01.02.01.01.02.02.01.01.02.01.01.01.01.01.05.01.04.04.06.012.03.010.03.09.03.04.02.02.02.0100.02.01.02.01.01.02.02.01.01.02.01.01.01.01.01.05.01.04.04.06.012.03.010.03.09.03.04.02.02.02.0100.012.013.015.016.017.019.021.022.023.025.026.027.028.029.030.035.036.040.044.050.062.065.075.078.087.090.094.096.098.0100.0表3-4检测器4处的车速频率统计表FrequencyValid2224Percent4.09.06.06.05.02.01.03.01.01.01.03.01.02.02.0ValidPercent4.09.06.06.05.02.01.03.01.01.01.03.01.02.02.0CumulativePercent4.013.019.025.030.032.033.036.037.038.039.042.043.045.047.02005年全国研究生数学建模竞赛一等奖

哈尔滨工业大学：苗鑫，高丽丽，李化南2223262829343637383944555758596162636472Total22311002.02.01.02.01.01.03.01.01.01.05.02.05.01.01.03.01.03.01.03.02.02.03.02.03.01.0100.02.02.01.02.01.01.03.01.01.01.05.02.05.01.01.03.01.03.01.03.02.02.03.02.03.01.0100.049.051.052.054.055.056.059.060.061.062.067.069.074.075.076.079.080.083.084.087.089.091.094.096.099.0100.0表3-5检测器5处的车速频率统计表FrequencyValid3451223235Percent1.05.01.03.01.02.01.01.01.01.02.02.01.01.02.02.03.02.03.0ValidPercent1.05.01.03.01.02.01.01.01.01.02.02.01.01.02.02.03.02.03.0CumulativePercent1.06.07.010.011.013.014.015.016.017.019.021.022.023.025.027.030.032.035.02005年全国研究生数学建模竞赛一等奖

哈尔滨工业大学：苗鑫，高丽丽，李化南29358596Total322322423.02.02.03.02.02.04.02.01.01.01.01.01.04.01.02.01.01.01.01.06.02.04.02.09.04.02.0100.03.02.02.03.02.02.04.02.01.01.01.01.01.04.01.02.01.01.01.01.06.02.04.02.09.04.02.0100.038.040.042.045.047.049.053.055.056.057.058.059.060.064.065.067.068.069.070.071.077.079.083.085.094.098.0100.0图1各检测器处的车速分布饼图Sensor1 speedSensor2 Speed35383946484955758596356575859666768697071782005年全国研究生数学建模竞赛一等奖6

Sensor3 speedSensor4 speed23789259666768697343637383944555758596162636472哈尔滨工业大学：苗鑫，高丽丽，李化南图2各检测器处的车速分布直方图Sensor5 speedsensor 1speed34931522520Frequency535455575859651560Mean = 54.18Std. Dev. = 6.669N = 10065Sensor1 speedsensor 2speedsensor 3speed50404030Frequency30FrequencyMean = 57.87Std. Dev. = 16.391N = 12Mean = 51.19Std. Dev. = 21.227N = 100Sensor2 SpeedSensor3 speed2005年全国研究生数学建模竞赛一等奖7

哈尔滨工业大学：苗鑫，高丽丽，李化南sensor 4speedsensor 5speed25202015Frequency15FrequencyMean = 28.04Std. Dev. = 22.705N = 160Mean = 39.3Std. Dev. = 19.651N = 10070Sensor4 speedSensor5 speed图3各检测器处对应不同时段的车速分布图Line Plot ( 1v*100c)70656055Sensor1

speedLine Plot ( 1v*100c)9:40:074:08:074:36:075:04:075:32:076:00:076:28:076:56:073:54:074:22:074:50:075:18:075:46:076:14:076:42:0720Sensor2Speed1003:40:074:08:074:36:075:04:075:32:076:00:076:28:076:56:073:54:074:22:074:50:075:18:075:46:076:14:076:42:07Line Plot ( 1v*100c)80706050Sensor3

speedLine Plot ( 1v*100c)80706050Sensor4

speed403020100-103:40:074:08:074:36:075:04:075:32:076:00:076:28:076:56:073:54:074:22:074:50:075:18:075:46:076:14:076:42:-103:40:074:08:074:36:075:04:075:32:076:00:076:28:076:56:073:54:074:22:074:50:075:18:075:46:076:14:076:42:072005年全国研究生数学建模竞赛一等奖8

哈尔滨工业大学：苗鑫，高丽丽，李化南Line Plot ( 1v*100c)706050Sensor5

speed4030201003:40:074:08:074:36:075:04:075:32:076:00:076:28:076:56:073:54:074:22:074:50:075:18:075:46:076:14:076:42:07根据题表和上面的图表可知，在第一个检测器附近，5:24:07PM时平均车速降到50mile/hr以下，以后十几分钟的时间里，车速在50mile/hr附近波动，可知此时交通流已经不稳定，将要进入拥挤状态，后续的观测数据进一步证实了这一点。从5:38:07PM到6:10:07PM，平均车速都低于50mile/hr，交通处于拥塞状态，直到6:12:07PM车速超过50mile/hr，且以后车速均大于50mile/hr，证明6:12:07PM左右拥塞消散。根据以上分析可见，检测器1处存在明显的交通拥塞和消散过程。从实际情况考虑，题表中的观测数据涵盖了下午的交通高峰时段，其原因是下班交通高峰造成，大约从5：40PM到6：10PM，持续半个小时左右。同理可以分析第2、3个检测器处的交通运行特征。在第2个检测器处，5:30:07PM左右，交通已经进入拥塞状态，一直持续到5:54:07PM左右，后来拥挤开始消散。在第3个检测器处,5:24:07PM左右交通进入拥塞状态，一直持续到6:18:07PM左右，后来拥挤开始消散。检测器4处的交通运行比较特殊，出现了多个平均车速低于50mile/hr的时段，据此信息可以推测第4个检测器处存在着外界对交通流的干扰因素，通常可能是由于道路两侧施工或临时占用道路等原因造成。从这个问题来看，监测器还可以用于道路异常状况及事故的检测。第5个检测器处的交通运行状况也比较特殊，其拥挤开始于4:36:07PM左右，而消散于6:34:07PM左右，拥塞时间开始早、结束晚，拥挤状态时长明显超过第1、2、3检测器附近的状况，所以可以推测第5个检测器处存在交通因素以外的原因造成车辆通行不畅，通常可能是由于道路通行能力由于某种原因降低，导致上游车流到达后不能及时疏散，造成较长时间的交通拥塞状态。下表是对5个检测器所提供的速度数据进行相关性分析所得到的相关矩阵：表4各检测器处的速度相关矩阵表Correlations(data2)Markedcorrelationsaresignificantatp<.05000N=100(Casewisedeletionofmissingdata)Sensor1SpeedSensor1SpeedSensor2SpeedSensor3speedSensor4speedSensor5speed1.0000p=---.5950p=.0001.0000p=---.7880p=0.00.7729p=0.009.5487p=.000.4067p=.000.4923p=.000.2197p=.028Sensor2Speed.5950p=.0002005年全国研究生数学建模竞赛一等奖

哈尔滨工业大学：苗鑫，高丽丽，李化南Sensor3speed.7880p=0.00.7729p=0.00.4067p=.000.2197p=.0281.0000p=---.5760p=.000.4740p=.000.5760p=.0001.0000p=---.4275p=.000.4740p=.000.4275p=.0001.0000p=---Sensor4speed.5487p=.000Sensor5speed.4923p=.000从表中可以看出v1与v3的相关性较强，v2和v3的相关性较强。在95%的置信水平下，各个监测器监测到的速度之间的相关性都是显著的，因此在考虑整个过程的行驶时间的时候，各个监测器在t时刻监测到的速度最好是要考虑在内的。2流量未知情况下的行驶时间估计设t时刻所有检测器记录的当时当地的车速分别是v1,v2,v3,v4,v5，以D1,D2,D3,D4,D5来表示五个检测器，以L1,L2,L3,L4表示四段路程的长度。在不考虑交通流量的情况下，车辆的行驶时间与车辆的行驶速度和路程有直接关系，即t=f(v,L)。设一辆车在t时刻通过第一个检测器，要在t时刻给出这辆车行驶到第五个检测器所用的时间，必须要对未来一段时间内四段路上的交通情况（行1车速度）进行估计。我们可以用v1和v2的平均值(v1+v2)来刻画车辆在第一段2路上的行驶速度，记为v22，车辆以这个速度行驶到D2，并以这个速度作为此刻D2检测到的速度，对应的此时后面各个检测器所检测到的速度为v23,v24,v25，1，与v2i-1和vi有关，我们令v2i=(v2,i-1+vi)，这样就得到了v2i（其中i=3,4,5）2当车辆行驶到D2时，其他检测器检测到的速度的一个估计量。车辆在D2和D31之间的行驶速度受v22和v23的影响，在此我们取v33=(v22+v23)作为车辆在这段2路上的行驶速度和到达D3处时检测器检测到的速度。以下以此类推，我们就得到了各个路段上行驶的速度，具体表达式如下ì1(v+vi-1,j),i

哈尔滨工业大学：苗鑫，高丽丽，李化南Lkk=ivkk如果能够得到每20秒的实时数据，而不是每2分钟的数据，那么本算法对行驶时间的估计将更加精确。首先，由于在实际情况下，某辆车的路段行驶速度很可能是不断变化的，基本关系式是：路程等于速度和行驶时间的乘积，路程可看作是在时间——速度坐标中，由速度曲线与时间轴所围成的面积；从积分的角度来看，把时间轴划分的份数越多，积分计算越准确。现在是在已知路程的情况下求行驶时间，道理都一样，计时间隔时段划分的越细，对真实速度的反映就越精确、越接近实际情况，从而路段行驶时间的估计结果越精确。再者，本算法通过不断更新的实时平均速度数据来估计某辆车的行驶速度，因此本算法本身也具有实时性，能将路上车流速度的变化及时地反映在路段行驶时间的计算中。检测器显示数据间隔时段越短，越接近于反映道路上车辆运行的实时情况，从而能够为计算所提供的信息就越多。则行驶到D5的时间很容易求出t=å53流量已知情况下的行驶时间估计如题所述，检测器可以检测每20秒内的车速和流量，根据表中提供的数据，估计车辆到达第5个检测器所需的时间。由于车流速度受交通状况和道路状况的影响，在道路状况一定的情况下，稳定交通流中的车速主要受交通流量的影响，因此已知交通量的情况下，可以提高路段行驶时间估计的合理性和准确性。而且平均速度的表达，以空间平均速度来代替时间平均速度，也将使行驶时间的计算更具有合理性和准确性。下面给出交通工程学中时间平均车速与空间平均车速的定义：时间平均车速vt：在单位时间内测定的通过道路某断面各车辆的点车速，这些点速度的算术平均值，即为该断面的时间平均车速，即：1nvt=åvini=1式中：vt——时间平均车速(千米/小时)或（米/秒）；vi——第i辆车的地点车速(千米/小时)或（米/秒）；n——单位时间内观测到的车辆总数（辆）。空间平均车速vs：在某一特定瞬间，行驶于道路某一特定长度内的全部车辆的车速分布的平均值，当观测长度为一定时，其数值为地点车速观测值得调和平均值，即vs=111åni=1vin（3）=nsåti=1n（4）i式中：2005年全国研究生数学建模竞赛一等奖11

哈尔滨工业大学：苗鑫，高丽丽，李化南vs——空间平均车速(千米/小时)或（米/秒）；s——路段长度（千米）或（米）；ti——第i辆车的行驶时间；n——长度为s的路段上所具有的车辆数；vi——第i辆车的行驶车速(千米/小时)或（米/秒）。题表中给出的车速观测数据是各个20秒内的时间平均车速vt。下面根据流量数据来计算空间平均车速vs。根据表中统计结果可知，20秒内的最大流量为17.1辆，即0.855辆/秒。出现在4:32:07PM时的检测记录中，由第一个检测器所检测到，其对应的平均行驶车速为59英里/小时。在交通管理与控制中，一般将调查得到的交通高峰时段实际流量的最大值作为道路所能通过的极大流量Qm，题表中观测数据的时间范围在下午3：40到7：00之间，其内存在下班时间的交通高峰时段，所以可以用其观测到的流量最大值来作为Qm值。根据交通工程学之中交通流三参数（车1速、流量、车流密度）的基本关系可以推导出Qm所对应的行驶速度为vf，其2中vf为畅行速度，即车流密度趋于零、车辆可以畅通无阻时的平均速度。此题中可以认为vf=2´59=118英里/小时，换算为52.75米/秒。又有基本关系式：1Qm=vfkj，其中：kj为阻塞密度，即车流密集到所有车辆无法移动(v=0)时4的车流密度。则由上式可得kj=0.065辆/米。交通工程学中，流量与车流速度有下图所示的关系：vf非拥挤区拥挤区Qmvs2由公式Q=kj(vs-)，可求出交通流量Q所对应的vs的值。则：vfìvf4kjQ2(kj+kj-),ifï2kvïjfvs=í4kjQïvf2(k-k-),ifjjï2kvfîjvt³50mile/hr（5）vt<50mile/hr根据5个检测器所测得的流量值，就可以由上式分别求得各流量所对应的空2005年全国研究生数学建模竞赛一等奖12

哈尔滨工业大学：苗鑫，高丽丽，李化南间平均车速vsi,i=1,2,3,4,5。将vsi的值代入到上面流量未知情况下的算法中来代替其中相应的时间平均车速v1,v2,v3,v4,v5，即可求出更精确合理的路段行驶时间。这样以流量作为输入，以题表中给出的时间平均车速作为控制条件，充分利用了检测车速和流量两种数据，并相当于知道了20秒内通过检测器断面的所有车辆在实际道路上瞬间车速分布的均值，从而实现了时间数据向空间数据的转化，更趋近于表达实际车辆在道路上的分布与运行情况，因而更合理。4链路行驶时间独立且随机情况下的最短路问题由于假设任何两条链路的行驶时间相互独立，也就是说在某一条链路上行驶时不必考虑其他链路的情况，因此，此处将最优路线定义为：由出发点到目的地行驶时间最短的路线为最优路线。这样，问题就转化为求城市交通网络中任意两点间的最短路径问题。算法描述如下图所示：输入道路节点数及节点的邻接矩计算任意两点间的最短路径长度、记录路径信息由司机输入行驶的起点和终点寻找最短路径及计算路径长度分别估算各段路的行驶时间，并将其相加分别输入最短路径每段路上处于正常工作状态的传感器个数、各传感器间的距离以及每个传感器所观测到的速度和流量值最短路径及行驶时间算法的实现过程：首先是建立城市交通网络，需要输入交通节点数和任意两个节点之间的链路距离（如果某两个节点间没有直接道路相通，那么这两点间的路权为∞）。这些信息输入以后，系统将自动计算出任意两个节点中的最短路径并计算出该路径的长度。然后由司机输入起点和终点信息，系统将列出与指定的起点和终点相对应2005年全国研究生数学建模竞赛一等奖13

哈尔滨工业大学：苗鑫，高丽丽，李化南的最短路径及其长度，并根据第I题的思想估算出此路线的行驶时间。在估算行驶时间之前，需要获得一些相关信息：①该最短路径每个路段上处于正常工作状态的传感器的个数；②每个处于正常工作状态的传感器上所观测到的速度值和流量值；③各个处于正常工作状态的传感器之间的距离、该段路起点与第一个处于正常工作状态的传感器间的距离、最后一个处于正常工作状态的传感器与该段路终点间的距离。以上3条信息在现实情况下是不需要输入的，而是系统根据某段道路上的传感器的实际情况而获得的。但是由于该程序是一个模拟的过程，因此像这样的必要信息是需要作为输入而提供给系统的。在计算任意两点之间的最短路径的时候用到了Floyd算法，算法描述如下：for(k=1;k<=n;k++)for(i=1;i<=n;i++)for(j=1;j<=n;j++)if(A[i][k]+A[k][j]

哈尔滨工业大学：苗鑫，高丽丽，李化南然后分别输入1至4，4至3路段上的传感器相关信息，具体如下：1至4路段：3个传感器传感器1：流量10（辆/20秒），速度51km/.h；传感器2：流量12（辆/20秒），速度49km/.h；传感器3：流量11（辆/20秒），速度60km/.h；各传感器将路段分成的距离分别为：60m,30m,120m,90m。4至3路段：4个传感器传感器1：流量10（辆/20秒），速度57km/.h；传感器2：流量9.7（辆/20秒），速度54km/.h；传感器3：流量10.7（辆/20秒），速度20km/.h；传感器4：流量5.9（辆/20秒），速度58km/.h；各传感器将路段分成的距离分别为：40m,60m,30m,30m,40m。执行结果如下：2005年全国研究生数学建模竞赛一等奖15

哈尔滨工业大学：苗鑫，高丽丽，李化南5动态随机网络情况下的最短路问题研究第Ⅱ大问题中的第2个问题，说明路段行驶时间取决于启程时间，同时又和其他路段行驶时间相关。所以，可以说路段行驶时间是与时间相关的随机变量，路段行驶时间随整个路网的交通状况呈动态变化，这种情况下寻找最短路的问题属于动态随机最短路问题。根据上面问题描述，可以将此情境下的最优路线定义为：车辆在动态随机路网中，从起始点到目的地过程中，行程总时间的均值和方差都尽可能小的路线。基本假设：1、每一时段内的路段行驶时间的样本均值和相应方差和任意两段路的相关系数是可以统计获得的；2、路段行驶时间是连续的、随时间变化的随机变量；3、不连续时段统计到的样本均值和方差可以作为输入数据；4、行驶时间与启程时间和到达目的地所要经过的路段（两个交叉口之间的公路）的行驶时间是相关的。这里把每个交叉口都看作是一个节点，并以从左到右，从上到下的顺序给各个节点命名，美国德克萨斯州的SanAntonio的道路的交叉口共有q个。假设从节点Oi到Oi+1的行驶时间ti服从某一分布（其中i=1,2,K,q），这一分布满足以下条件：（下面的t均为随即变量）（1）数学期望为mi，其中i=1,2,K,q表示从节点Oi到Oi+1的平均行驶时间。（2）方差为si，其中i=1,2,K,q，，表示从节点Oi到Oi+1的行驶时间相对于平均行驶时间的偏离程度。2005年全国研究生数学建模竞赛一等奖16

哈尔滨工业大学：苗鑫，高丽丽，李化南由假设可以知道mi和si是可以通过统计获得的。但未来时段链路行驶时间的预测具有不确定性，未来时段链路行驶时间预测的不确定性是同平均链路行驶时间的预测误差相关的，而不是同单个驾驶员的链路行驶时间相关。从这种意义上来说，总体的不确定性或个体司机链路行驶时间预测值的方差包括两个部分：平均行驶时间预测的误差，各个车辆行驶时间的方差。考虑到以上因素，令tˆi=ti+e，其中e:N(0,1)为随机扰动项，由于司机个人的偏好产生。我们用tˆi来衡量行驶时间。那么实际的行驶时间为：ˆi=E(tˆi)=E(ti+e)=mimˆi)=D(ti+e)=D(ti)+1+2cov(ti,e)，ˆi=D(t对应的方差为s由于随机误差项与ˆi=D(ti)+1。行驶时间之间是独立的，因此在上式中第三项为0，即s当车辆所要走的路程经过多个节点时，不妨设车辆从节点Oi行驶到Ol的行驶时间为til，则有til=åtk，但是，不同车辆的行驶时间存在很大差异，例如：k=il对于一天当中的任意时间t来说，某个驾驶员的车速可能会高于或低于观测到的平均链路行驶时间，某个车辆的行驶时间取决于驾驶员的自身的要求和该车辆周围的交通量。在上述情况下，单个链路的行驶时间可以表为由平均链路行驶时间和残差所决定的函数。其中，残差项刻画了司机个体的行为。上述关系可以用函数表示如下：我们可以把tˆil=åtˆk+d，作为实际的行驶时间，其中d:N(0,1)为系统误差，k=il与行驶时间和个人误差项独立。则tˆil有以下的统计特征：ˆil，其中i

哈尔滨工业大学：苗鑫，高丽丽，李化南xa(yi)来表示。实际上可以假定链路行驶时间取决于两个随机变量：某一车辆到达上游节点的时间和它在此链路上的行驶时间。于是，可以用fxa(xa|yi)来表示在y=yi时xa的条件概率函数。这里协方差矩阵具体的设计方法和规则如下：（1）由于协方差的统计意义反应的是两个随机变量的相关性，所以我们首先要找出影响两段路的相关性的因素。根据客观的分析我们可以知道，协方差与两个节点之间的路程和所经过的节点数，以及各个节点处所连接的道路数有关系。（2）根据问题我们可以知道司机想去的方向，因此，只有前方道路的状况会对现在行驶时间产生影响。而且两个节点之间的路程越长，相关性越小；所经过的节点数越多，Okl对Oij（2

哈尔滨工业大学：苗鑫，高丽丽，李化南的过程中，需要考虑该路径上其他路段的情况对当前路段的影响，需要用到一个反映各路段时间关联度的协方差矩阵。该算法的实现过程主要分为两部分：①寻找所有可能的路径；②估算每条路径的行驶时间，找出最优路线。由于在建立模型阶段对此部分已经做了比较详细的阐述，这里就不再赘叙，主要就第一部分——寻找起点到终点的所有可能路径进行说明。首先还是输入交通结点个数和关于各个结点的邻接矩阵，建立城市交通网，然后以起点和终点作为输入，经过计算，输出所有可能的路径。搜索路径的过程中采用的是树的先深搜索思想，对遇到的结点分以下三种情况处理：①所遇到的结点先前未曾经过，并且该结点不是终点：将该结点存入路径，继续进行搜索；②所遇到的结点是终点：将该结点作为终点存入路径，并将该路径作为最后结果中的一条可能的路径保存；③所遇到的结点不是终点，但曾经遇到过：这样就形成了环路，因此对此结点不作任何处理，直接返回上层结点继续搜索。然后对于每个可能的路径，估算该路径上各路段的行驶时间，并给出该估算时间的误差，当然这里要考虑到各路段在时间上的相关度。最后比较各个路径的估算时间均值和方差，在允许误差的范围内取耗时均值和方差尽可能小的路径作为最优路线。7给定两点间最优路线选择与行驶时间估计要求解第Ⅲ个问题，首先要确定期望和方差与链路长度和两端节点数的关系。由已知，车辆在各个链路上行驶时间的均值与路段长度成正比，方差与路段长度2/3次幂的倒数成正比，同时与这段路的两个端点所连接路径条数成正比。这样就可以得到关系式为：ìmij=k1Lijï-2í3ïîsij=k2Lijninj其中ni,nj分别表示链路Lij两个端点处所连接的道路条数。我们可以通过t时刻传感器所提供的速度和流量数据，根据问题Ⅰ的解决办法，得到每段路上的速度平均值，取他们的均值作为整个链路上的行驶速度，设1这个平均值为v，令上面关系中的k1=，则能得到路程与行驶时间的具体函数v关系。并可以根据假设和已知信息设计14个节点之间的协方差矩阵。对于链路3到14和14到3的最优行驶时间，我们可以在问题1中的监测器监测到的速度和流量的样本中，按照3到14和14到3两节点间路段上的监测器个数随机的选取样本，分别作为估计3到14和14到3行驶时间的录入数据。输入及输出结果如下：2005年全国研究生数学建模竞赛一等奖19

哈尔滨工业大学：苗鑫，高丽丽，李化南输入起点3，终点14，从节结点3到结点14的所有路径如下：3—〉2—〉1—〉4—〉5—〉6—〉9—〉8—〉7—〉11—〉143—〉2—〉1—〉4—〉5—〉6—〉9—〉81—〉12—〉11—〉143—〉2—〉1—〉4—〉5—〉6—〉9—〉13—〉12—〉8—〉7—〉11—〉143—〉6—〉9—〉13—〉12—〉11—〉14通过计算时间得出第一条路径为最优路线，估算的时间为984.692秒，对应的方差为6.747。实际的行驶时间在[964.451,1004.933]内，都认为估计是合理的。从结点14到结点3的所有路径如下：14—〉11—〉12—〉13—〉9—〉6—〉3所以最优路线就是14—〉11—〉12—〉13—〉9—〉6—〉3，估算时间为873.347秒，对应的方差为10.885。实际的行驶时间在[840.692,906.002]内，都认为估计是合理的。由于路径太长，因此所涉及到的传感器的输入太多，这里无法将程序执行的原图贴出，只能打出程序执行的结果。参考文献[1].Shortestpathsinanetworkwithtime-dependentflowspeeds，KiseokSunga,*,,1,MyeongkiSeongc,2,SoondalParkc,3，EuropeanJournalofOperationalResearch121(2000)32-39[2].EXPECTEDSHORTESTPATHSINDYNAMICANDSTOCHASTICTRAFFICNETWORKS，LIPINGFU，，TranspnRes.-B,Vol.32,No.7,pp.499-516,1998[3].Geneticalgorithmsforreroutingshortestpathsindynamicandstochasticnetworks，CedricDavies,PawanLingras，EuropeanJournalofOperationalResearch144(2003)27–38[4].Dynamicandstochasticshortestpathintransportationnetworkswithtwocomponentsoftraveltimeuncertaint，ParichartPattanamekar,DongjooPark，,JeomhoLee,ChoulkiLee，TransportationResearchPartC11(2003)331–354[5].概率论与数理统计，梁之舜，邓集贤等，高等教育出版社，2001，3[6].数学模型，姜启源，高等教育出版社，2002，1[7].数学实验，萧树铁等，高等教育出版社，2003，8[8].数据结构与算法基础，郭福顺，廖明宏，李莲志，大连理工大学出版社，2000，6[9].c/c++语言入门与精通，王丽宏，苏晓红，哈尔滨工业大学出版社，1999，92005年全国研究生数学建模竞赛一等奖20


更多推荐

时间,行驶,车速,速度,车辆,路径