Researcher:
Shiri, Davood

Profile Picture
ORCID

Job Title

PhD Student

First Name

Davood

Last Name

Shiri

Name

Name Variants

Shiri, Davood

Email Address

Birth Date

Filters

2017 - 201932020 - 20214

Advanced Search

Filter by

Settings

Researcher Of Publications: search.filters.isAuthorOfPublication.8cc221f4-a8d5-4959-912d-a889217340b3

Search Results

Now showing 1 - 7 of 7
  • Placeholder
    PublicationMetadata only
    On the randomized online strategies for the k-Canadian traveler problem
    (Springer, 2019) N/A; N/A; Department of Industrial Engineering; Shiri, Davood; Salman, Fatma Sibel; PhD Student; Faculty Member; Department of Industrial Engineering; Graduate School of Sciences and Engineering; College of Engineering; N/A; N/A; 178838
    We consider the online k-Canadian Traveler Problem (k-CTP) which is defined on an undirected graph with a given source node O and a destination node D. Non-negative edge costs are given. The traveling agent is initially at O. There are k blocked edges in the graph, but these edges are not known to the agent. A blocked edge is learned when the agent arrives at one of its end-nodes. The goal of the agent is to arrive at D with minimum total cost. We consider the k-CTP on graphs that consist of only node-disjoint O-D paths, where it was shown that there is no randomized online strategy with competitive ratio better than k+1. An optimal randomized online strategy was also given. However, we prove that the given strategy cannot be implemented in some cases. We also modify the given strategy such that it can be implemented in all cases and meets the lower bound of k+1.
  • Placeholder
    PublicationMetadata only
    Online optimization of first-responder routes in disaster response logistics
    (IBM, 2020) N/A; Department of Industrial Engineering; Shiri, Davood; Salman, Fatma Sibel; PhD Student; Faculty Member; Department of Industrial Engineering; Graduate School of Sciences and Engineering; College of Engineering; N/A; 178838
    After a disaster, first responders should reach critical locations in the disaster-affected region in the shortest time. However, road network edges can be damaged or blocked by debris. Since response time is crucial, relief operations may start before knowing which edges are blocked. A blocked edge is revealed online when it is visited at one o f its end-nodes. Multiple first-responder teams, who can communicate the blockage information, gather initially at an origin node and are assigned to target destinations (nodes) in the disaster-affected area. We consider multiple teams assigned to one destination. The objective is to find an online travel plan such that at least one of the teams finds a route from the origin to the destination in minimum time. This problem is known as the online multi-agent Canadian traveler problem. We develop an effective online heuristic policy and test it on real city road networks as well as randomly generated networks leading to instances with multiple blockages. We compare the performance of the online strategy with the offline optimum and obtain an average competitive ratio of 1.164 over 70,100 instances with varying parameter values.
  • Placeholder
    PublicationMetadata only
    On the online multi-agent O-D k-Canadian traveler problem
    (Springer, 2017) N/A; Department of Industrial Engineering; Shiri, Davood; Salman, Fatma Sibel; PhD Student; Faculty Member; Department of Industrial Engineering; Graduate School of Sciences and Engineering; College of Engineering; N/A; 178838
    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.
  • Placeholder
    PublicationMetadata only
    Competitive analysis of randomized online strategies for the multi-agent k-Canadian traveler problem
    (Springer, 2019) N/A; Department of Industrial Engineering; Shiri, Davood; Salman, Fatma Sibel; PhD Student; Faculty Member; Department of Industrial Engineering; Graduate School of Sciences and Engineering; College of Engineering; N/A; 178838
    In this article, we study randomized online strategies for the multi-agent k-Canadian Traveler Problem which is defined on an undirected graph with a given source node O and a destination node D. Non-negative edge costs are given. The traveling agents are initially at O. There are k blocked edges in the graph, but these edges are not known to the agents. A blocked edge is learned when at least one of the agents arrives at one of its end-nodes. The objective is to find an online strategy such that at least one of the agents finds a route from O to D with minimum travel cost. We analyze the problem in three cases: (1) without communication, (2) with limited communication, and (3) with complete communication. We derive lower bounds on the competitive ratio of randomized online strategies for these cases. We show that increasing the number of agents can improve the competitive ratio of randomized online strategies when there is no communication between agents. We introduce a randomized online strategy which is optimal for both cases with limited and complete communication on O-D edge-disjoint graphs. We also prove that the competitive ratio of the optimal randomized strategy does not improve on O-D edge-disjoint graphs, when the case with complete communication is compared to the case with limited communication.
  • Placeholder
    PublicationMetadata only
    Online routing and scheduling of search‑and‑rescue teams
    (Springer, 2020) Akbari, Vahid; N/A; Department of Industrial Engineering; Shiri, Davood; Salman, Fatma Sibel; PhD Student; Faculty Member; Department of Industrial Engineering; Graduate School of Sciences and Engineering; College of Engineering; N/A; 178838
    We study how to allocate and route search-and-rescue teams to areas with trapped victims in a coordinated manner after a disaster. We propose two online strategies for these time-critical decisions considering the uncertainty about the operation times required to rescue the victims and the condition of the roads that may delay the operations. First, we follow the theoretical competitive analysis approach that takes a worst-case perspective and prove lower bounds on the competitive ratio of the two variants of the defined online problem with makespan and weighted latency objectives. Then, we test the proposed online strategies and observe their good performance against the offline optimal solutions on randomly generated instances.
  • Placeholder
    PublicationMetadata only
    Correction to: online failure diagnosis in interdependent networks (Operations Research Forum, (2021), 2, 1, (10), 10.1007/s43069-021-00055-2)
    (Springer International Publishing, 2021) Akbari, Vahid; N/A; Shiri, Davood; PhD Student; Graduate School of Sciences and Engineering; N/A
    N/A
  • Thumbnail Image
    PublicationOpen Access
    Online failure diagnosis in interdependent networks
    (Springer Nature, 2021) Akbari, Vahid; N/A; Shiri, Davood; PhD Student; Graduate School of Sciences and Engineering
    In interdependent networks, nodes are connected to each other with respect to their failure dependency relations. As a result of this dependency, a failure in one of the nodes of one of the networks within a system of several interdependent networks can cause the failure of the entire system. Diagnosing the initial source of the failure in a collapsed system of interdependent networks is an important problem to be addressed. We study an online failure diagnosis problem defined on a collapsed system of interdependent networks where the source of the failure is at an unknown node (v). In this problem, each node of the system has a positive inspection cost and the source of the failure is diagnosed when v is inspected. The objective is to provide an online algorithm which considers dependency relations between nodes and diagnoses v with minimum total inspection cost. We address this problem from worst-case competitive analysis perspective for the first time. In this approach, solutions which are provided under incomplete information are compared with the best solution that is provided in presence of complete information using the competitive ratio (CR) notion. We give a lower bound of the CR for deterministic online algorithms and prove its tightness by providing an optimal deterministic online algorithm. Furthermore, we provide a lower bound on the expected CR of randomized online algorithms and prove its tightness by presenting an optimal randomized online algorithm. We prove that randomized algorithms are able to obtain better CR compared to deterministic algorithms in the expected sense for this online problem.