论文部分内容阅读
提出突发性片堵塞下的实时路径选择问题即片堵塞加拿大旅行者问题(regional blockages Canadian traveller problem),考虑出行者对堵塞信息有限预知的情形,从在线问题与竞争策略的角度,建立片堵塞加拿大旅行者问题在线路径选择模型,设计贪婪策略,结合片堵塞中多条路段同时发生堵塞的特点,通过比较信息预知点到片堵塞起始点的路段(预知路段)通行时间与最短路径上堵塞路段恢复时间的大小来分析策略的不同情形,证明贪婪策略竞争比,并讨论影响贪婪策略竞争比的预知路段通行时间临界值.
This paper proposes a real-time routing problem under patch jamming, ie regional blockages Canadian traveler problem. Considering travelers’ limited prediction of jamming information, this paper proposes a patch jamming method based on online problems and competitive strategies Canada travel problem online routing model, the design of greedy strategy, combined with the blockage of multiple sections in the jam at the same time, by comparing the information to predict the point to the piece of block the starting point of the road (predicted road) passage of time and the shortest path blockage Recovery time to analyze the different scenarios of the strategy to prove the competition ratio of greedy strategies and to discuss the threshold value of the predicted passage time-of-passage that affects the competition ratio of greedy strategies.