基于最小费用最大流算法的冲突车流分配-论文.pdf

《基于最小费用最大流算法的冲突车流分配-论文.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第23卷第2期山东交通学院学报V01．23No．22015年6月JOURNALOFSHANDONGJIAOTONGUNIVERSITYJun．2015DOI：10．3969／j．issn．1672-0032．2015．02．005基于最小费用最大流算法的冲突车流分配李运，潘应久，侯礼兴(长安大学公路学院，陕西西安710064)摘要：从最短路径角度研究交通分配问题，利用Dijkstra算法求解最短路径，根据道路容量和运行时间的限制，得出非冲突车流的优化路径，在此基础上假设冲突发生，采用设置优先通行规则与最小费用最大流算法相结合，实现有交通冲突情况下的交通流分配。关键词：冲突车流；交通分配；最小费

2、用最大流算法；Matlab中图分类号：U491．2文献标志码：A文章编号：1672-0032(2015)02--0025--06交通分配是把各种出行方式的空间O．D(Origin．Destination)分配到具体交通网络上。对于交通分配，国内外均有较多的研究，数学规划法、图论法及计算机技术的发展，为交通分配模型的研制及应用提供了坚实的基础1]。国际上通常采用平衡和非平衡两大类方法对交通分配进行划分¨2j。在交通规划方法相对成熟之后，业内开始把注意力更多的转向交通控制与诱导，由此动态交通分配(DynamicTrafficAssignment)诞生。动态交通流分配理论从提出至今经过了20多年的发

3、展，在理论研究和方法应用上都有一定的进步与突破J，但仍处于发展阶段，究其根本原因是考虑时间变量因素，建立合适的数学模型并设计相应的算法非常困难J。冲突车流分配研究同步于动态分配研究，目前要找到一种解决冲突车流的合适方法仍然是比较困难的。本文先用Dijkstra算法研究非冲突车流的最短路径，再根据最小费用最大流算法得出非冲突车流的分配并考虑多种情况，最后利用设置优先通行规则与最小费用最大流算法相结合的方法获得冲突车流的分配1最小费用最大流算法最小费用最大流问题是经济学和管理学中的一类典型的基本问题J。在一个网络中每条路径都存在“容量”和“费用”两个限制条件，此类问题是想寻找出：车流从地到B地，选

4、择合适的路径及考虑分配路径的流量，使其能够在流量最大的前提下，达到所用的费用最小的要求。假设辆卡车要从A地到地运送物品，由于每条路段都存在不同的收费情况，每条路能容纳的车的数量也有一定限制，最小费用最大流问题指如何分配卡车的出发路径可以使费用降到最低，物品又能准确全部的送达]。物流成本最小问题称为最小费用流问题，在现实生活中有很多的应用，一般把其归为一类网络优化问题_8J。可以把容量作为流，费用作为时间代价，来研究交通运输问题。最小费用最大流算法包含很多经典的算法和流程，本文主要采用其中的最大流算法和最小费用最大流对偶算法。1．1最大流算法流程1)对网络G=[，E，c，]，给出流值为零的初始流

5、，其中G[V，E]为具有几个顶点、m条弧的有向收稿日期：2Ol5-03—31作者简介：李运(199O一)，男，内蒙古包头人，硕士研究生，主要研究方向为交通规划及交通政策26山东交通学院学报2015年6月第23卷图，为n个顶点的非空有限集合，E为m条弧的非空有限集合，C为弧容量，为弧间的费用函数。2)作伴随初始流的增流网络G=[，E，]。G的顶点同G，V=V(顶点相同)，G，[，E]为增流网络的n个顶点、r条弧的有向图，为增流网络间的费用函数。若G中-厂(u，)

6、(／2,，)、c(u，)分别为可行流的边权值和容量的边权值。若G中．厂(／Z，)>0，贝0G中建边(，u)，W(，／Z)=一(U，)。3)若G不存在至Y的路径，则G的流即为最小费用最大流，停止计算；否则用标号法(Dijkstra算法)找出至Y的最短路径P。4)对P的每条边(U，)，若G存在(U，)，则(／,，／3)增流；若G存在(，U)，则(，u)减流。增(减)流后，应保证对任一边有c(e)≥Jr(e)>10。其中：c(e)、厂(e)分别为该弧的弧容量和弧流量。5)根据计算最短路径时的各顶点的标号值L()，修改G所有边的权数W(e)，有L()+W(e)—制(e)。6)将新流视为初始流，转到步骤

7、2)。1．2最大流最小费用对偶算法流程1)任意∈V，令7r=0；任意(，f)∈E，令，=0。、，为顶点V集合里的第i和第个顶点，7r为在i点处构造的弧，为间的可行流。2)如果。=(，)，．~lJf是最小费用流，否则转3)。其中：。为最大流的流值，(为可行流的流值。3)构造网络G(f，7r)，对任意∈V，求出G(f，7r)中关于W的最短且由到的权d(i)，令7r+d=。G(f，7r)为以／为顶点、7