Risk Reward Strategy For Real Time Routing Under Unexpected Regional Blockage

Real time routing problem under unexpected blockage is a hot issue of the society and the international academia. Previous researches about the routing for the traffic blockage in urban traffic networks have made many achievements on the single road blockage. But the research on the regional blockage which is a kind of blockage that multiple incident roads are simultaneously blocked at certain times is less, and it is more difficult to deal with. Meanwhile, previous studies about regional blockage are under the classical online point of view, and this kind of method is conservative under uncertain environment. In this paper, the real routing problem under unexpected blockage is studied under the risk reward online framework, which is more flexible than the classical online framework. Under the risk reward online framework, the traveller is willing to take risks to forecast the recovery time of blockages and designing risk reward strategy. When the forecast is right, he/she will get less travel time, but when the forecast is wrong, he/she must get some lost. The major works of this paper are as follows.Establish the risk reward framework for real time routing problem under unexpected regional blockage on general network. The optimal online strategy-a waiting-reselection strategy is presented and its competitive ratio is 2. Then prove that waiting-reselection strategy is the optimal online strategy. On the basis of this, the definition of risk, reward are given under the risk reward framework, and then present optimistic strategy on general network and pessimistic strategy on general network according to two different forecasts of the recovery time, and then the rewards, risks of the two risk reward strategies are analyzed and compared.Establish the risk reward framework for real time routing problem under unexpected regional blockage on grid network. According to the characteristics of the grid network, design a shortest path algorithm-a multiple choice algorithm when the traveller doesn’t encounter any blockages on grid network. The optimal online strategy-a waiting-multiple choice strategy is presented and its competitive ratio is 1+h/m+n+2,where h is the maximum time of regional blockages the traveller will encounter and m,n denote the subscript of the destination vmn on grid network. Then prove that waiting-multiple choice strategy is the optimal online strategy. On the basis of this, optimistic strategy on grid network and pessimistic strategy on grid network are given according to two different forecasts of the recovery time under the risk reward framework, and the rewards, risks of the two risk reward strategies are analyzed and compared.