Conditional covering problem: Study of complexity and optimization methods

Persistent Link:
http://hdl.handle.net/10150/290032
Title:
Conditional covering problem: Study of complexity and optimization methods
Author:
Horne, Jennifer Amy
Issue Date:
2004
Publisher:
The University of Arizona.
Rights:
Copyright © is held by the author. Digital access to this material is made possible by the University Libraries, University of Arizona. Further transmission, reproduction or presentation (such as public display or performance) of protected items is prohibited except with permission of the author.
Abstract:
The Conditional Covering Problem (CCP) is a facility location problem on a graph, where the set of nodes represents the demand points and the potential facility locations. The CCP minimizes the sum of the facility location costs required to cover all demand points. The key aspect of the CCP is that a facility covers all nodes within a given coverage radius, except for the node on which it is located. Our investigation of the CCP will first show that solving CCP on a general graph structure is NP-Hard, prohibiting finding exact optimal solutions in a finite amount of time. While the CCP is NP-Hard on general graphs, we will present a quadratic algorithm that will find optimal solutions to CCP on path and extended star graphs (multiple path graphs with one node in common). We will then present a polynomial time algorithm for tree graphs building off the quadratic algorithms for a star and tree. Given that CCP is NP-Hard on general graphs we next focused on determining near optimal solutions for general graphs. We applied both greedy heuristics and metaheuristics to determine near-optimal solutions. Building off our understanding of optimal solutions on tree structures, we incorporate the idea of trees into our heuristic search. We found that greedy heuristics provide near-optimal solutions in a very short period of time. We showed that simulated annealing with binary encoding provided higher quality solutions to the CCP.
Type:
text; Dissertation-Reproduction (electronic)
Keywords:
Engineering, Industrial.
Degree Name:
Ph.D.
Degree Level:
doctoral
Degree Program:
Graduate College; Systems and Industrial Engineering
Degree Grantor:
University of Arizona
Advisor:
Smith, J. Cole

Full metadata record

DC FieldValue Language
dc.language.isoen_USen_US
dc.titleConditional covering problem: Study of complexity and optimization methodsen_US
dc.creatorHorne, Jennifer Amyen_US
dc.contributor.authorHorne, Jennifer Amyen_US
dc.date.issued2004en_US
dc.publisherThe University of Arizona.en_US
dc.rightsCopyright © is held by the author. Digital access to this material is made possible by the University Libraries, University of Arizona. Further transmission, reproduction or presentation (such as public display or performance) of protected items is prohibited except with permission of the author.en_US
dc.description.abstractThe Conditional Covering Problem (CCP) is a facility location problem on a graph, where the set of nodes represents the demand points and the potential facility locations. The CCP minimizes the sum of the facility location costs required to cover all demand points. The key aspect of the CCP is that a facility covers all nodes within a given coverage radius, except for the node on which it is located. Our investigation of the CCP will first show that solving CCP on a general graph structure is NP-Hard, prohibiting finding exact optimal solutions in a finite amount of time. While the CCP is NP-Hard on general graphs, we will present a quadratic algorithm that will find optimal solutions to CCP on path and extended star graphs (multiple path graphs with one node in common). We will then present a polynomial time algorithm for tree graphs building off the quadratic algorithms for a star and tree. Given that CCP is NP-Hard on general graphs we next focused on determining near optimal solutions for general graphs. We applied both greedy heuristics and metaheuristics to determine near-optimal solutions. Building off our understanding of optimal solutions on tree structures, we incorporate the idea of trees into our heuristic search. We found that greedy heuristics provide near-optimal solutions in a very short period of time. We showed that simulated annealing with binary encoding provided higher quality solutions to the CCP.en_US
dc.typetexten_US
dc.typeDissertation-Reproduction (electronic)en_US
dc.subjectEngineering, Industrial.en_US
thesis.degree.namePh.D.en_US
thesis.degree.leveldoctoralen_US
thesis.degree.disciplineGraduate Collegeen_US
thesis.degree.disciplineSystems and Industrial Engineeringen_US
thesis.degree.grantorUniversity of Arizonaen_US
dc.contributor.advisorSmith, J. Coleen_US
dc.identifier.proquest3131604en_US
dc.identifier.bibrecord.b46708546en_US
All Items in UA Campus Repository are protected by copyright, with all rights reserved, unless otherwise indicated.