主管:中国科学院
主办:中国优选法统筹法与经济数学研究会
   中国科学院科技战略咨询研究院

Chinese Journal of Management Science ›› 2018, Vol. 26 ›› Issue (7): 151-158.doi: 10.16381/j.cnki.issn1003-207x.2018.07.016

• Articles • Previous Articles     Next Articles

Regional Blockage Canadian Traveler Problem under Two Vehicles Information Sharing

SU Bing, LIN Gang, CHENG Xin-feng, SUN Lu-lu   

  1. School of Economics and Management, Xi'an Technological University, Xi'an 710021, China
  • Received:2016-08-08 Revised:2018-01-18 Online:2018-07-20 Published:2018-09-20

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

CLC Number: