Investigating the benefits of re-optimisation while searching for two immobile entities on a network
type: Item
instance of: scholarly article
title: Investigating the benefits of re-optimisation while searching for two immobile entities on a network
zbMATH Open document ID: 1176.90266
DOI: 10.1504/IJMOR.2009.022875
author: Arun Jotshi
author: Rajan Batta
published in: International Journal of Mathematics in Operational Research
publication date: 2009-10-12T00:00:00Z
review text: Summary: We consider the problem of searching for two immobile entities on an undirected network where the entity locations are probabilistically known and dependent. This article extends the work of \textit{A. Jotshi} and \textit{R. Batta} [Eur. J. Oper. Res. 191, No.~2, 347--359 (2008; Zbl 1149.90026)] on the search for a single entity. The problem is first examined for the case where re-optimisation is not allowed, i.e., we are not allowed to change the path once we have started traversing it. In the second case, re-optimisation is allowed after the discovery of the first entity. For both cases, the objective is to minimise the expected search time to find both entities. Heuristic algorithms are introduced and computational results are presented showing the benefits of allowing re-optimisation.
Mathematics Subject Classification ID: 90B40
Mathematics Subject Classification ID: 90B10
Mathematics Subject Classification ID: 68T20
zbMATH DE Number: 5613384
zbMATH Keywords: immobile entities
zbMATH Keywords: re-optimisation
zbMATH Keywords: search problems
zbMATH Keywords: undirected network
MaRDI profile type: Publication
full work available at URL: ijmor.2009.022875
OpenAlex ID: W2110992643
description: scientific article; zbMATH DE number 5613384