The k-Canadian Travelers Problem with communication

Huili Zhang (), Yinfeng Xu () and Lan Qin ()
Additional contact information
Huili Zhang: Xi’an JiaoTong University
Yinfeng Xu: Xi’an JiaoTong University
Lan Qin: Xi’an JiaoTong University

Journal of Combinatorial Optimization, 2013, vol. 26, issue 2, No 3, 265 pages

Abstract: 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.

Keywords: Online k-CTP; Communication; Competitive analysis (search for similar items in EconPapers)
Date: 2013
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (10)

Downloads: (external link)
http://link.springer.com/10.1007/s10878-012-9503-x Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:26:y:2013:i:2:d:10.1007_s10878-012-9503-x

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-012-9503-x

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().