A Mathematical Programming Approach to Immobile Entity Search
Moskal, Michael D., II
MetadataShow full item record
With the expanding role of graph theory in real-world military and transportation problems, it is critical to develop new mathematical models and problems to permit the transition from theory to application. This research focuses on a graph theory problem related to search. Its specific purpose is to is establish a parsimonious mixed integer program for immobile entity search in the context of the Utilitarian Postman Problem (UPP), which is a relatively new topic in operations research with strong ties to the well-studied Chinese Postman Problem. We focus initially on unit graphs which are important in modeling transportation networks, and their planar properties lead to linear time partitioning algorithms. A total of six formulations are presented relevant to immobile entity search and prize collection. The directed unit graph model serves as the basis for the logic in the undirected unit graph model which is the main focus of our research. These models are then further generalized to model the situation of a Utilitarian Postman (UP) path on graphs with non-uniform edge lengths. These models are readily formulated and understood, and their relative compactness make them very powerful tools in the scope of the UPP. These models are also incredibly flexible, allowing easy manipulation to accommodate new problem constraints. The formulations presented closely parallel the definition of the prize-collection arc routing problem, where the objective is to maximize the net profit collected along the edges across of the entire network. A variation of the aforementioned models is provided in the context of prize-collection arc routing, where new variable and constraint set definitions permit application beyond immobile entity search. Since unit and generalized graphs do not necessarily provide an adequate representation of complex transportation networks, a mixed graph model is also developed. This enhanced model is capable of handling graphs with directed and undirected arcs of non-uniform length. A computational study on the undirected unit graph model is performed using a series of randomly generated unit graphs. Our results reveal that the formulation together with the direct application of the MIP solver in CPLEX struggles to close the gap to optimality through branching and bounding in the solver on large graphs. This is not unexpected from sizable MIP formulations. To establish scalability of the models, a divide-and-conquer heuristic is developed. A comparison is drawn between the only other known mathematical programming formulation to the UPP. This comparison demonstrates that our work has significant potential to deliver further insights into the properties of the UPP.