Search for a single entity on a network.

摘要

We consider the problem of searching for a single entity on a network. The entity is either immobile or with limited mobility. The search time is a random variable depending on the search path and location/moving path of the entity. The objective is to minimize the expected search time. A specific application is a disaster scenario in which the searcher is an emergency vehicle and the entity is a casualty.;The dissertation is divided into three parts. Part 1 reviews a closely related arc covering problem - Chinese Postman Problem(CPP). Our problem differs from CPP in the way that here the objective is not to find the minimum length tour that covers all the links at least once, but instead to minimize the expected time to find the entity. Part 2 is dedicated to the problem of search for an immobile entity. Three mathematical programming models are proposed. The first model is a network flow-based model. The second model is a mixed integer quadratic constraint problem. The third model is the linearized form of the second model. These three models are compared in terms of their computational time and solution quality. Based on several proven properties of the optimal solution, we proposed an algorithm named SIEUG to solve the problem. Part 3 addresses the problem of search for a mobile entity on a network. A search game model is built and a simulation approach is used to evaluate the search time under different strategies of the searcher and mobile entity. The impact of four factors are investigated - relative speed of the searcher and the entity; the size of the network; the structure of the network and the detection radius. Optimal strategy pair in terms of the minimum expected search time and two other objectives are found from extensive numerical testing through a design of experiments mechanism.