一种基于路况数据的城市道路交叉口拥堵评价指数研究

提出了交叉口总延误时间指数和单一方向最大延误时间指数,利用从导航软件获取的交叉口各进口方向路况、排队长度和车道数等数据,建立了交叉口拥堵评价指数模型。利用北京交叉口实例对模型的适用性进行了验证,在此基础上依据交叉口总延误时间指数和单一方向最大延误时间指数对案例交叉口进行了拥堵水平排序,排序结果与实际情况相符。交叉口延误时间指数相较于传统的交叉口评价指标,充分利用导航软件的大数据,避免了繁琐的现场调研工作,具有很强的规模化操作性和实用性,为城市管理者在交叉口改造决策方面提供了更加可靠的理论依据。

分批排序问题1|B,r_j,s_j|L_(max)的近似算法

主要讨论了工件有到达时间、加工时间和尺寸的目标函数是极小化最大延误时间的单机分批排序问题1|B,rj,sj|Lmax.在机器容量B为常数时,即使在B=2和工件的到达时间与尺寸都相同时,问题也是强NP—难的.基于问题1|B,rj|Lmax目前最好的多项式时间近似算法——PTAS算法(从算法的最差性能比来说是最好的),我们采用任意工件可以按尺寸拆分的技巧,针对问题1|B,rj,sj|Lmax设计了一个多项式时间的近似算法,并分析出这个算法的最差性能比为2+ε(其中ε是任意小的正数).