突发性面拥堵实时路径选择的风险回报策略

发布时间：2018-10-26 11:37

【摘要】：出行前无法预知突发性拥堵下的实时路径选择是整个社会和国际学术界关注的热点问题。现有成果大多假设拥堵发生在网络的单一边上,对多条关联边同时拥堵即面拥堵下的实时路径选择相关研究较少,而且这些研究采用了经典在线问题与竞争策略的理论分析框架,在更为不确定的环境下,这种方法显得较为保守。论文采用更为灵活的风险回报在线问题与竞争策略的理论分析框架,研究出行者遭遇突发性面拥堵实时路径选择的风险回报策略,即假设出行者愿意冒着风险对当前拥堵持续时间进行预测并采取相应策略,如果预测正确则得到比经典在线策略更好的收益,如果预测错误将承担损失。论文的主要工作和成果如下。建立风险回报在线框架下一般网络上突发性面拥堵的实时路径选择模型并进行策略设计及其竞争性能分析。首先设计经典在线框架下的最优在线策略——等待-重选策略,证明其为竞争比为2的最优在线策略；在此基础上给出风险回报在线框架下风险和回报的定义,结合出行者预测的拥堵持续时间设计一般网络上的风险回报策略——乐观策略和悲观策略；在风险回报在线框架下分析不同风险回报策略的约束竞争比,给出并比较一般网络上的乐观策略和悲观策略的风险回报。建立风险回报在线框架下方格网络上突发性面拥堵的实时路径选择模型并进行策略设计及其竞争性能分析。首先分析面拥堵在方格网络上的表现形式,结合方格网络特点,设计经典在线框架下的最优在线策略——等待-多选择混合策略,证明其为竞争比为1+h/m+n+2(其中,h为遭遇面拥堵的最大次数,m,n为终点vman在方格网络上的下标)的最优在线策略；在此基础上结合出行者预测的拥堵持续时间设计了方格网络上的风险回报策略——乐观策略和悲观策略；在风险回报在线框架下分析不同风险回报策略的约束竞争比,给出并比较方格网络上的乐观策略和悲观策略的风险回报。
[Abstract]:It is a hot issue that the whole society and the international academic circles pay attention to the real-time path selection under unexpected congestion before travel. Most of the existing results assume that congestion occurs on the single edge of the network. Moreover, these studies adopt the theoretical analysis framework of classical online problem and competition strategy, which is more conservative in the more uncertain environment. In this paper, a more flexible theoretical analysis framework of online risk return problem and competitive strategy is used to study the risk return strategy of real-time path selection for travelers suffering from sudden congestion. That is to say, if the traveler is willing to take the risk to predict the duration of current congestion and adopt the corresponding strategy, if the prediction is correct, the gains will be better than the classical online strategy, and if the prediction is wrong, the loss will be borne. The main work and results are as follows. The real-time path selection model of sudden congestion on general network is established under the online framework of risk return, and the strategy design and competitive performance analysis are carried out. First, we design the optimal online strategy under the classical online framework, that is, waiting and reselection, and prove that it is the optimal online strategy with a competitive ratio of 2. On this basis, the paper gives the definition of risk and return under the online framework of risk return, and designs the optimistic strategy and pessimistic strategy of general network based on the congestion duration predicted by travelers. In this paper, the constrained competitive ratio of different risk-return strategies is analyzed under the online framework of risk return, and the risk return of optimistic strategy and pessimistic strategy on general network is given and compared. The real time path selection model of sudden congestion on grid network under the online framework of risk return is established, and the strategy design and competitive performance analysis are carried out. In this paper, we first analyze the expression of surface congestion on grid network, and combine the characteristics of grid network, we design the optimal online strategy under the classical online framework, which is the hybrid strategy of waiting and multi-choice, and prove that it is a competitive ratio of 1 h / m n 2. H is the maximum number of face congestion encountered, and Mon n is the subscript of vman on the grid network) the optimal online strategy; On the basis of this, combined with the forecast congestion duration of the traveler, the paper designs the risk return strategy on the grid network, which is optimistic strategy and pessimistic strategy. In this paper, the constrained competitive ratio of different risk-return strategies is analyzed under the online framework of risk return, and the risk return of optimistic strategy and pessimistic strategy on grid network is given and compared.
【学位授予单位】：西安工业大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：U491

【参考文献】