On the online multi-agent O‐D k-Canadian Traveler Problem

On the online multi-agent O‐D k-Canadian Traveler Problem

0.00 Avg rating0 Votes
Article ID: iaor20172779
Volume: 34
Issue: 2
Start Page Number: 453
End Page Number: 461
Publication Date: Aug 2017
Journal: Journal of Combinatorial Optimization
Authors: ,
Keywords: combinatorial optimization, graphs, heuristics, simulation
Abstract:

In this article, we present new results on the online multi‐agent O–D k‐Canadian Traveler Problem, in which there are multiple agents and an input graph with a given source node O and a destination node D together with edge costs such that at most k edges are blocked. The blocked edges are not known a priori and are not recoverable. All of the agents are initially located at O. The objective is to find an online strategy such that at least one of the agents finds a route from the initial location O to a given destination D with minimum total cost. We focus on the case where communication among the agents is limited in the sense that some travelers can both send and receive information while the others can only receive information. We formalize the definition of agents’ intelligence by specifying three levels. We introduce two online strategies which utilize higher levels of agents’ intelligence to provide updated lower bounds to this problem. We show that one of our strategies is optimal in both cases with complete and limited communication in the special case of O–D edge‐disjoint graphs and highest level of agents’ intelligence.

Reviews

Required fields are marked *. Your email address will not be published.