方格网络上用户均衡行为效率损失研究

针对用户出行时追求费用最短的路径,而不考虑其它用户如何选择路径,在一般网络中导致系统费用较高的问题,从实际出发,本文重点讨论特殊网络-方格网络上纳什均衡流与系统最优流之间的关系,研究了用户均衡行为的效率损失.研究结果表明,在方格网络上,当路阻函数是系数非负的线性函数和二次函数时,用户均衡行为的效率损失分别是0和0.35,而一般网络中用户均衡行为的效率损失分别是1/3和0.626,说明方格网络具有较好传送流量的功能.该研究为道路建设部门进行道路改造和增加新道路设计提供理论依据.     

环形路网上带有服务时长的在线TSP问题

为了提高快递揽件的时效性,需要对快递车辆进行有效调度。针对环形路网上服务时长以及需求无法预知的揽件问题,本文提出了以服务总时间尽可能短为目标的环形路网上带有服务时长的在线旅行商问题。用在线算法分析了此问题竞争比的下界,设计了两个在线算法并分析了各自的竞争比,结果表明服务时长可以改善在线车的性能。最后通过简单算例对两个算法进行说明,本文研究结论可以为环形路网上的快递车辆实时调度提供指导。     

拥挤收费策略设计及其效率损失分析

在静态交通量分配中,针对边际收费策略会引起系统总费用过大的问题,本文设计了最小收费策略收取拥挤道路使用费.同边际收费策略相比较,该收费策略不会增加系统的效率损失;当路阻函数不是常函数时,最小收费策略所收费用严格小于边际收费策略所收费用;最小收费策略能使得交通状况达到系统最优且收费总额度最小.     

不完全信息下城市交通量分配研究

由于缺乏信息,用户在出行时实际上并不能确切知道出发点处的交通量,由于城市私家车越来越多,用户往往会过高的估计出发地的交通量。本文假设所有用户总是悲观的预期即认为出发地有M≥r单位的交通量,其中r表示实际的交通量,悲观流就是所有用户悲观预期交通量时产生的流量。当费用函数是系数非负的线性函数时,证明了用户均衡流总费用不小于悲观流的总费用;当费用函数是系数非负、最大度数为d的多项式函数时,证明了用户均衡流的总费用不超过悲观流总费用的1/τd倍,其中1≥τ=r/M。研究结果表明,当用户过高估计交通量出行时,会改善交通状况,是因为部分用户绕行到费用更大的路径上,缓解了交通压力,改善了交通状况。     

成对需求占线服务器问题及公平原则策略

针对在对称度量空间上多服务需求的k-服务器占线问题,研究问题空间为k＋2（度量空间上有k＋2个顶点,但只有k个服务器）时的一个特例：即在任意时刻都同时有两个服务需求提出。建立了该问题的数学模型,给出了公平原则策略,该策略能使得任意两个服务器完成服务后花费费用之差不大于某个固定常数;进行了相应的策略分析和竞争比的证明,并同工作函数策略进行了比较。     

基于道路堵塞及顾客时间要求的快件配送最优路径选择

针对道路堵塞如节假日导致的临时最短配送路径失效的问题,提出配送网络最优路径选择模型,并设计了求解快递配送网络关键边和最优路径的算法。首先,计算出整个网络的关键边,掌握配送网络特征;其次,考虑顾客时间要求,研究不完全信息(中断无法提前预知,只有到达中断边的起点处才可知)下的最优路径,根据最短路径上各边新的特点,计算出每条边中断后对应的一组备用路径,再选择运输时间小于或等于顾客可等待时间的路径为有效路径,考虑道路堵塞情况,从有效路径中选择最优路径;最后,结合配送网络的实际情况对最优路径进行了算例分析。