基于随机时变路网的运输路径选择.doc

基于随机时变路网的运输路径选择刻帅唐伯明刘松重庆交通大学土木工程学院学院摘要：针对运输路网中各路段上的行驶时间受交通管理、交通拥挤、天气变化等不确定 性因素的影响而呈现出随机时变的特点，引入了路网评审技术中的三时估值法， 建立了随机时变路网下以行驶时间最短为目标的路径优化模型，提出了车辆跨 时段行驶时路段的时间依赖函数，设计了动态规划标号算法求解算例求解优化 结果的对比分析验证了模型及算法的有效性关键词：交通运输工程;随机时变;跨时段;动态规划;作者简介：刘帅（1982一），男，山东菏泽人，博士研究生，主要从事物流方面 的石JI•宄E-mail :wordday@sina. com作者简介：唐伯明（1962一），男，江苏东台人，教授，工学博士，博士生导师, 主要从事交通运输工程方而的研究E-mai 1: tbm@nctcase. com收稿日期：2016-12-19基金：教育部人文社会科学研究规划基金项目（17YJA630079）Transportation Route Selection in Stochastic Time-Dependent NetworkLIU Shuai TANG Boming LIU SongSchool of Civil Engineering，Chongqing JiaotongUniversity; School of Traffic & Transportation, Chongqing Jiaotong University;Abstract：The travel time at each section of road transportation network was affected by traffic management, traffic congestion, weather changes and other uncertainties, so it showed stochastic time-dependent characteristics. The three-time valuation method in road network evaluation technique was introduced, and a path optimization model in stochastic timedependent road network to minimize the travel time was established. A time-dependent function of the road sections when the vehicle travelled inter-temporally was proposed. Moreover, an algorithm of dynamically programming and labeling was designed to solve the function. Through a comparative analysis of the optimization results of the application examples, the effectiveness of the proposed model and algorithm was verified.Keyword：traffic and transportation engineering; stochastic time-dependent; over time; dynamic programming;Received： 2016-12-190引言交通拥挤、交通事故等因素的不确定性，导致车辆在各路段行驶中的行驶成本、 行驶时间等也具有不确定性，呈现出随机时变特性。

随机时变路网模型由于考虑 了现实路网的时变性与随机性，能更好的反映实际交通路网状态，其中如何合 理的处理具有时变性和随机性的路段权值是关键问题董振宁等m考虑y路段权值的随机性，假设路段权值服从指数分布，以期望路 长最短为目标对随机路网最短路进行优化;范巍巍等m、郑龙等位:、周光发等 ui研宄了带约束条件的随机路网最短路问题但以上学者没有考虑路段权值随 时间不同而呈现出的时变特点贺政纲等包1考虑了路段权值的时变特点，对行 驶风险随时间变化的带时间窗的最短路进行优化;范文璟等m、刘丽萍等m考 虑丫在时变路网中带约束条件的应急救援路径优化;彭勇等in对时变路网中以 配送完成时间最早为优化目标的车辆配送路径优化进行了研宄;王莺等m研宄了时变路网中，以运输成本和运输损耗为目标的最短路问题这些学者考虑了路 段权值的吋变性，但没有考虑路段的随机性将路网的随机性和吋变性特点同吋加以考虑的学者不多，陈京荣等［10］考虑了 路网的随机性和时变性特点研究最短路问题;魏航等mi考虑/路网的随机时变 特点对有时间窗限制的应急路径进行优化;曹慧等mi利用鲁棒优化方法研宂了 随机时变路网下的最短路径问题虽然以上学者同时考虑了路网的随机性和时变 性，但是没有考虑随机时变网络中不可忽略的first input first output (FIFO) 问题以及跨时段行驶问题。

笔者运用计划评审技术中解决非确定型统筹问题所采用的三时估计法来处理随 机时变路网路段权值问题三吋估计法是实际工程中估计工作持续吋间的主要方 法之一，是一种有效的工程项目进度风险分析方法车辆在道路上的行驶时间可 认为是车辆在道路上需要工作的时间，与工程项目工序完成时间一致，所以， 三时估计法也可用于运输中的不确定性分析笔者借鉴三吋估计法和动态规划标 号法，寻求在随机时变路网环境下，车辆从起点0到终点I),以行驶时间最短为 目标，满足FIFO规则和车辆跨时段行驶的最短路线1问题描述及条件假设1.1问题描述对于随机时变路网下运输路径的问题，一般可以抽象为午.辆在冇向路网图G= (V, E, td)中的运输线路选择问题，其中:V为节点集合，表示道路节点，节点的数 量|V|=n;E为弧集合，表示路段，路段的数量为车辆在1\时刻所处的 第k个时段时由节点i出发到达节点j所需的时间1.2条件假设1) 各路段的交通状况相互独立2) 已知车辆通过交通路网中各路段的时间分亦，且车辆在第k个时段通过路段 (i, j)的时间服从正态分布N (b，Sd (注：(i，j)为从结点i到节点j的 有向路段)3) 车辆在各节点处的等待吋间为0。

2问题建模2.1随机时变路网下行程时间分析路段的行程时间由于受交通事故、天气变化等因素影响难以准确估计而呈现出随 机时变特性，因此，笔者引入计划评审技术中解决非确定型问题所釆用的三时 估计法来处理路段行程时间随机时变的不确定性问题，把随机时变路网转化为 确定性时变路网将路段的时间分为悲观时间、乐观时间，及在正常情况下的最 可能时间，再计算其期望时间和方差用aij表示在第k个吋间段由i出发到达j所需吋间的乐观估计;用bij表示在第k 个时间段由i出发到达j所需时间的悲观估计;用^表示在第k个时间段由i出 发到达j所需时间的最可能估计利用三时估值法得到第k个时间段由i出发到 达j的期望时间和方差：在随机时变路网中，路段的权值与出发时间有关，因此，确定路网的时间依赖 函数就非常重耍当前，关于随机时变路网中的吋间依赖函数的研究大多还处于 较为理想的状态MALANDRAKI C等首次采用时间分段函数作为时间依赖函 数来表示路段行程吋间，如图1图 1 行驶时间时间依赖函数 Fig. 1 Time-dependent function of travel time 下载原图图1显示路段（i, j）在不同时段所需的行驶时间，如果1号车在08:50离开 i,在09:50到达j;同时，2号车在09:00离开i,却在09:40到达j，比1号车 早到，违反丫 FIFO原则。

因此尽管时间分段法分段数越多越接近实际情况，但 是该方法为了满足路网的先入先出FIFO特性，需耍假定车辆在节点处等待一定 时间，这与实际情况不符K. SUNG等［14］证明了使用如图2的行驶速度时间依赖模型满足FIFO原则图 2 行驶速度时间依赖函数 Fig. 2 Time-dependent function of travel speed 下载原图为了使得车辆在随机时变路网中的行驶时间满足FIFO原则，笔者设计了以下方 法计算路段（i, j）的行驶时间设K为时间分段的集合{1，…，k，…，K},为第k个时段;为节点i的出发时 刻;Tj为到达j的时刻;Zij为车辆在L时刻所处的第k个时段由节点i出发到达 节点j的成本;h （L）为车辆在1\时刻由节点i出发到达节点j所需的时间 在第k个时段，车辆平均行驶速度为（k=l，2,…），路段（i, j）的距离为 d.j,若车辆驶离i的时刻T,落在第k个时段内，即T,e时，车辆在（i，j）上的行驶时间分3种情况计算:不跨、部分跨、完全跨时段车辆由节点i出发到 达节点j所需跨越吋段数计为N （N:l, 1, 2，…，N） , N^K-k, N的计算如下:1） 若 UkOtij,则 N=0;2） 若 Uk-T/tij, Uk+「Uk彡tij-Uk,则 N=l;同理可得，车辆由节点i出发到达节点j所需跨越时段数N。

1）如果车辆完全在k时段内行驶完路段（i，j），即N=0，不跨时段行驶，由 于假设在各个节点处等待时间为0，故节点的到达时间等于出发时间则抵达节 点j的时刻几为2）若车辆在路段（i，j）上行驶由k时段跨越到了 k+1时段，即N=l，则到达j 的时刻T、为命题若车辆在路段（i, j）上行驶从k时段跨越到了 k+N （N^2）个时段，贝删 达j的时刻L为推导1）当车辆从k时段跨越到了 k+2个时段时，到达节点j的时刻L为2）当车.辆从k时段跨越到了 k+3个时段时，到达节点j的时刻几为3）当车辆从k时段跨越到了 k+N个时段时，到达节点j的时刻Tj为2.2数学模型设X是路径可行解的集合，人（A ex）是起点0和终点D之间的一条可行路径, 则所求问题的优化模型为约束条件如式（7） &式（9）:式（6）为目标函数，最小化车辆的行驶时间；式（7）表示在t时段路段（i, j） 被路径X使用，则Xij=l，否则，Xij=0;式（8）表示起点、终点以及路网其他节 点的路网流平衡约束，保证车辆行驶路径的连续性;式（9）表示任意路段只能 被使用一次，保证车辆行驶路径中没有回路3算法设计由于考虑了路网的随机性和时变性，随机时变路网路径求解算法比静态路网复 杂。

随机时变网络己被证明是NP完全问题（non-determini stic polynomial complete problem）笔者将其转化为满足FIFO特性的确定型时变路网问题，可 设计动态规划和标号法求解对于一个随机吋变的运输网络，在求解过程中，通 常可将其划分为若干个阶段，然后逐个阶段由前往后推移，直至终点用标号法 求解，先要设计标号给节点j标号［（j, t,」，zQj, TJ L,q,Ti,其中所 属阶段;T,为由i到达j的时刻，Tj按式（4广式⑹求得J为到达i的吋刻; 为边（i，j）的权值;为在时间tj到达节点j的目标值这样，基于动态规划 和标号法的求解步骤如下：1） 对运输路网进行阶段的划分，得到阶段数Q，阶段q的节点集合记作Nq2） 给出出发时间tQ,并给起点0以固定标号［（0, 0, 0, TJ ］0, 1,此时TQ=tQ,Q= 13） 寻求和Nq+1中节点氏+1为凡的前向节点集合,ieNq, jeNq+1,其中,i、jeN,。