带有信息有限预知的片堵塞加拿大旅行者问题

提出突发性片堵塞下的实时路径选择问题即片堵塞加拿大旅行者问题(regional blockages Canadian traveller problem),考虑出行者对堵塞信息有限预知的情形,从在线问题与竞争策略的角度,建立片堵塞加拿大旅行者问题在线路径选择模型,设计贪婪策略,结合片堵塞中多条路段同时发生堵塞的特点,通过比较信息预知点到片堵塞起始点的路段(预知路段)通行时间与最短路径上堵塞路段恢复时间的大小来分析策略的不同情形,证明贪婪策略竞争比,并讨论影响贪婪策略竞争比的预知路段通行时间临界值.

Regional blockage Canadian traveler problem with finite lookahead

The real-time routing problem under unexpected regional blockages is proposed, the problem is called regional blockages Canadian traveller problem (RB-CTP). From the online point of view, the online routing model of RB-CTP is established with finite lookahead and a greedy strategy is presented. The competitive ratio is proved for the greedy strategy by comparing the travel time of the edge connecting vertex with finite lookahead and vertex of regional blockage with the recovery time of the blocked edge on the shortest path and analyzing the property of regional blockage including multiple edges blocking at the same time. The critical value of travel time is given for the edge connecting vertex with finite lookahead and vertex of regional blockage that influence the greedy strategy.