提出突发性片堵塞下两车信息共享的加拿大旅行者问题，即两车欲从起点出发去终点，在运输过程中会遭遇突发性片堵塞，若两车对堵塞信息都能有限预知且车辆间可以信息共享，如何制定路径选择策略使两车花费的总时间尽可能少。针对该问题，采用在线问题与竞争策略的理论和方法，建立突发性片堵塞下两车信息共享的在线路径选择模型，设计混合贪婪策略，结合片堵塞中多条路段同时发生堵塞的特点，以及所选路径是否经过信息预知点到片堵塞起始点的路段（预知路段）等策略不同情形的分析，证明混合贪婪策略竞争比。最后进行实例分析，验证模型和策略的有效性。
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.
[1] Papadimitriou C.H,Yannakakis M. Shortest paths without a map[J]. Theoretical Computer Science,1991, 84(1):127-150.
[2] Bar-Noy A, Schieber B. The Canadian traveler problem[C]//Proceedings of the Second annual ACM-SIAM Symposium on Discrete algorithms, 1991, 261-270.
[3] Sleator D D, Tarjan R E. Amortized efficiency of list update and paging rules[J]. Communications of the ACM, 1985, 28(2):202-208.
[4] Borodin A, El-Yaniv R. Online computation and competitive analysis[M]. Cambridge:Cambridge University Press, 1998.
[5] Fiat A, Rabani Y, Ravid Y. Competitive k-server algorithms[J]. Journal of Computer & System Sciences, 1994, 48(3):410-428.
[6] Fiat A, Woeginger G J. Online algorithms:The state of art[M]. Berlin:Springer, 1998.
[7] Xu Yinfeng,Hu Maolin, Su Bing,et al.The Canadian traveller problem and its competitive analysis[J]. Journal of Combinatorial Optimization,2009, 18(2):195-205.
[8] Hu Maolin. Comparison strategy and its competitive ratio analysis of scheduling for on-line routing[J]. Journal of Ningxia University, 2005, (3):207-210.
[9] Westphal S.A note on the k-Canadian traveler problem[J]. Information Processing Letters,2008, 106(3):87-89.
[10] Zhu Zhijun, Xu Yinfeng, Liu Chuncao. Scheduling for on-line routing problem and its competitive strategy analysis[J].Journal of System Engineering, 2003, 18(4):261-270.
[11] Zhang Huili, Xu Yinfeng, Qin Lan.The k-Canadian Travelers Problem with communication[J].Journal of Combinatorial Optimization, 2013, 26(2):251-265.
[12] 徐寅峰,张惠丽,余海燕,等. 基于方格路网的两车应急救援路径在线选择[J]. 系统工程理论与实践,2013,33(1):175-180.
[13] 苏兵,徐寅峰.堵塞恢复时间随机的加拿大旅行者问题[J].系统工程理论与实践,2005,25(10):108-113.
[14] 苏兵,兰小毅.有限预知信息的可恢复加大旅行者问题[J].系统工程,2009,27(9):102-107.
[15] 马丽娟,徐寅峰,苏兵,等.一条路上的占线可恢复加拿大旅行者问题混合策略[J].系统工程理论方法应用,2005,14(4):318-321,325.
[16] 崔晓.突发性片堵塞下的实时路径选择策略研究[D].西安:西安工业大学,2012.
