关键词: 信息有限预知, 片堵塞, 两车信息共享, 加拿大旅行者问题

Abstract: The Canadian Traveler Problem has been introduced in Papadimitriou and Yannakakis, in which the vehicles know in advance the structure of the graph and the costs of all edges. However, some edges may fail and vehicles only observe that upon reaching an adjacent vertex of the blocked edge. The goal is to find the least-cost route from the source O to the destination D, more precisely, to find an adaptive strategy minimizing the competitive ratio by comparing the performance of this strategy with that of a hypothetical offline algorithm that knows the entire topologyin advance. Previous researches suppose that a vehicle sees that only one edge is blocked in each blockage, but the regional blockages often occur in a traffic network which is composed of multiple blockededges.In this paper, the regional blockage Canadian traveler problem of two vehicles information sharing is proposed, in which two vehicles can get the regional blockage information with finite lookaheadand share information each other. The goal is to find the least total travel time for two vehicles from the source O to the destination D.From the online point of view, an adaptive strategy——mixed greedy strategy is presented and the competitive ratio for the strategy is proved. An application of mixed greedy strategy for two vehicles in a traffic network is shown. The research results of this paper can provide effective theoretical basis for the multiple vehicles real-time routing problem and traffic flow guidance by traffic management department.

Key words: finite lookahead, regional blockage, information sharing, the Canadian Traveler Problem