Anzeige
Erschienen in:
01.08.2013
The k-Canadian Travelers Problem with communication
Erschienen in: Journal of Combinatorial Optimization | Ausgabe 2/2013
EinloggenAktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
This paper studies a variation of the online k-Canadian Traveler Problem (k-CTP), in which there are multiple travelers who can communicate with each other, to share real-time blockage information of the edges. We study two different communication levels for the problem, complete communication (where all travelers can receive and send blockage information with each other) and limited communication (where only some travelers can both receive and send information while the others can only receive information). The objective is that at least one traveler finds a feasible route from the origin to the destination with as small cost as possible. We give lower bounds on the competitive ratio for both the two communication levels. Considering the urban traffic environment, we propose the Retrace-Alternating strategy and Greedy strategy for both the two communication levels, and prove that increasing the number of travelers with complete communication ability may not always improve the competitive ratio of online strategies.