考虑诱导信息耦合作用的人群疏散模型

为探究多种诱导信息对疏散中人群的叠加作用,在元胞自动机离散环境的基础上提出动态扫描算法,快速获取行人的第一人称视角。基于第一人称视角定义人群运动信息和引导员指示信息耦合规则,结合元胞自动机建立考虑诱导信息耦合作用的人群疏散模型。模拟结果表明:跟随效应作用会导致出口使用不均衡;引导员信息强度的适量增加可以有效改善出口使用的均衡程度,但强度超过某定值时几乎所有行人按引导员指示运动,出口使用失衡;引导员位置分布对疏散过程产生明显影响,且引导员连线应尽可能与疏散路线垂直。该模型提供一种多种视觉诱导信息耦合作用的研究框架。

平面上最接近点对问题的研究

针对平面上最接近点对问题,分别考虑其在离线环境和在线环境下的两种情况。在离线环境下,针对分治算法,结合点集本身的稀疏性质和圆的性质,给出一个改进的合并算法,使得在合并过程中由每个点的最多6次计算距离降为4次运算,从而提高算法的效率。在在线环境下,给出3种算法求解此问题。第1种算法是每给出第k个点就计算k-1次。第2种算法是给出一个判别式子,在给第k个点时,首先对前k-1个点进行判断,判断出与之会影响当前最小距离的点后再进行计算。第3种算法是结合几何知识,证明得到在此问题中,当新的点出现时,最多只会有6个点与之影响当前最小距离,所以通过插序找出此6点再进行计算。可以证明这3种算法的时间复杂度均为O(n2),但显然随着点数n的增大,算法的平均时间复杂度一定会依次降低。

单机上简单线性退化工件的随机在线调度问题

研究了单机上工件具有简单线性退化效应的随机在线调度问题.工件以时间在线的方式到达,决策者对将来到达工件的信息一无所知,当工件到达之后,决策者立刻知道工件加工时间的期望,且工件加工时间的期望是开工时间的简单线性函数,直到工件完工才能知道工件的实际加工时间.目标函数是最小化工件总完工时间和的期望.对于这个随机在线调度问题,通过改变工件的释放时间给出了竞争比为1+b_(max)的SHIFTSDR在线算法.这与LIU M等人所研究的确定性情形的下界相匹配,因此可以证明,对所研究的问题给出的在线算法是最好可能的在线算法.

关于恶化工件的单机在线调度最优算法的另一种证明

对于一台机器上在线调度简单恶化工件的最小化总完工时间问题,Liu在文献(Theoretical Computer Science 445(2012)75-81)中提出了一个最优在线算法DSGR,此算法在最坏情况下的比率是1+α_(max),其中α_(max)=majxα_j是所有工件的最大恶化率.对于这个结果我们给出了另外一种简单的证明.

基于历史数据的轨道交通站内客流预测模型

轨道交通站点内客流实时状况是进行客流管控与应急管理的基础,为实时监测轨道交通网络客流变化,对大客流进行预警,构建了一种基于历史数据的轨道交通站内客流预测模型。首先利用历史轨道交通每个站点的进出站数据,挖掘不同站点分时段客流OD分布估计及到达时间估计,再基于实时进站数据,预测乘客的终点站选择与行程时间,反推演乘客时空轨迹,最终根据乘客时空轨迹分析各个站点的人群动态变化,从而实现轨道交通站内客流预测。以上海市2015年4月份轨道交通客流数据验证了模型的有效性,并采用MAPE、MRD和MPC 3个参量评价模型优劣。结果表明:与实际客流相比,模型对客流变化规律性较强站点(如南京东路站、人民广场站)的预测误差较小,对数据量较少、客流变化随机性较大的偏远站点(如复兴岛站)的预测误差较大。因此,该模型能够实时预测轨道交通的站内客流变化,从而预警轨道交通大客流,以便采取预防性管控措施。

D-SWPT在线算法竞争比的简易证明方法

竞争比反映了算法构造的调度偏离最优调度的最大程度,是衡量一个算法优劣的重要指标.针对经典在线调度问题1|online,r_j|∑w_jC_j,著名学者Anderson和Potts在2004年给出了在线算法D-SWPT,并证明了其竞争比为2.然而,其证明过于复杂冗长.对此问题,作者提出一个新的简单易学的证明方法,证明了在线算法D-SWPT的竞争比为2.