{"id":{"repo_id":"vt","oai_identifier":"oai:vtechworks.lib.vt.edu:10919/91146"},"canonical_url":"https://search.dev.ndltd.org/etd/vt/oai:vtechworks.lib.vt.edu:10919/91146","repository":{"repo_id":"vt","name":"Virginia Tech","base_url":"https://vtechworks.lib.vt.edu/oai/request"},"display":{"title":"Capacitated, unbalanced p-median problems on a chain graph with a continuum of link demands","abstract":"This study is concerned with the problem of locating p capacitated facilities on a chain graph, and simultaneously determining the allocation of their supplies in order to satisfy a continuum of demand which is characterized by some weighted probability density function defined on the chain graph. The objective is to minimize the total (expected) transportation cost. This location-allocation problem is also referred to as the capacitated p-median problem on a chain graph. Two unbalanced cases of this problem are considered, namely, the over-capacitated case when total supply exceeds total demand, and the deficit capacity case when total supply is less than total demand. Both these problems are nonconvex, and are shown to be NP-hard even if the demand density function is piecewise uniform and positive. We provide a first-order characterization of optimality for these two problems, and prescribe an enumerative algorithm based on a partitioning of the dual space in order to optimally solve them. An extension of these algorithms for solving the capacitated, unbalanced 2-median problem on a tree graph is also given.","abstract_html":"This study is concerned with the problem of locating p capacitated facilities on a chain graph, and simultaneously determining the allocation of their supplies in order to satisfy a continuum of demand which is characterized by some weighted probability density function defined on the chain graph. The objective is to minimize the total (expected) transportation cost. This location-allocation problem is also referred to as the capacitated p-median problem on a chain graph. Two unbalanced cases of this problem are considered, namely, the over-capacitated case when total supply exceeds total demand, and the deficit capacity case when total supply is less than total demand. Both these problems are nonconvex, and are shown to be NP-hard even if the demand density function is piecewise uniform and positive. We provide a first-order characterization of optimality for these two problems, and prescribe an enumerative algorithm based on a partitioning of the dual space in order to optimally solve them. An extension of these algorithms for solving the capacitated, unbalanced 2-median problem on a tree graph is also given.","abstract_has_math":false,"creators":["Rizzo, Thomas Philip"],"institution":"Virginia Polytechnic Institute and State University","degree_name":"M.S.","degree_level":"masters","degree_discipline":"Industrial Engineering and Operations Research","degree_department":"Industrial Engineering and Operations Research","school":null,"contributors":[],"advisors":[],"committee_chairs":[],"committee_members":[],"year":1986,"date_issued":"1986","date_published":"1986","updated_at":"2026-07-22T22:19:37Z","subjects":[],"languages":["en_US"],"rights":["In Copyright"],"rights_urls":["http://rightsstatements.org/vocab/InC/1.0/"],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/10919/91146","outbound_label":"Handle","outbound_source":"dc:identifier.uri"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.department","label":"Department","values":["Industrial Engineering and Operations Research"]},{"key":"dc:creator","label":"Author","values":["Rizzo, Thomas Philip"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2019-07-03T20:34:00Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2019-07-03T20:34:00Z"]},{"key":"dc:date.issued","label":"Date","values":["1986"]},{"key":"dc:publisher","label":"Institution","values":["Virginia Polytechnic Institute and State University"]},{"key":"dc:type","label":"Dc Type","values":["Thesis"]},{"key":"dc:type.dcmitype","label":"Dc Type Dcmitype","values":["Text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Industrial Engineering and Operations Research"]},{"key":"thesis:degree_level","label":"Degree Level","values":["masters"]},{"key":"thesis:degree_name","label":"Degree Name","values":["M.S."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["Virginia Polytechnic Institute and State University"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language.iso","label":"Language (ISO)","values":["en_US"]},{"key":"dc:rights","label":"Dc Rights","values":["In Copyright"]},{"key":"dc:rights.uri","label":"Rights URI","values":["http://rightsstatements.org/vocab/InC/1.0/"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["http://hdl.handle.net/10919/91146"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["This study is concerned with the problem of locating p capacitated facilities on a chain graph, and simultaneously determining the allocation of their supplies in order to satisfy a continuum of demand which is characterized by some weighted probability density function defined on the chain graph. The objective is to minimize the total (expected) transportation cost. This location-allocation problem is also referred to as the capacitated p-median problem on a chain graph. Two unbalanced cases of this problem are considered, namely, the over-capacitated case when total supply exceeds total demand, and the deficit capacity case when total supply is less than total demand. Both these problems are nonconvex, and are shown to be NP-hard even if the demand density function is piecewise uniform and positive. We provide a first-order characterization of optimality for these two problems, and prescribe an enumerative algorithm based on a partitioning of the dual space in order to optimally solve them. An extension of these algorithms for solving the capacitated, unbalanced 2-median problem on a tree graph is also given."]},{"key":"dc:description.degree","label":"Dc Description Degree","values":["M.S."]},{"key":"dc:format.mimetype","label":"Dc Format Mimetype","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Capacitated, unbalanced p-median problems on a chain graph with a continuum of link demands"]}]}],"canonical_facts":{"dc:contributor.department":["Industrial Engineering and Operations Research"],"dc:creator":["Rizzo, Thomas Philip"],"dc:date.accessioned":["2019-07-03T20:34:00Z"],"dc:date.available":["2019-07-03T20:34:00Z"],"dc:date.issued":["1986"],"dc:description.abstract":["This study is concerned with the problem of locating p capacitated facilities on a chain graph, and simultaneously determining the allocation of their supplies in order to satisfy a continuum of demand which is characterized by some weighted probability density function defined on the chain graph. The objective is to minimize the total (expected) transportation cost. This location-allocation problem is also referred to as the capacitated p-median problem on a chain graph. Two unbalanced cases of this problem are considered, namely, the over-capacitated case when total supply exceeds total demand, and the deficit capacity case when total supply is less than total demand. Both these problems are nonconvex, and are shown to be NP-hard even if the demand density function is piecewise uniform and positive. We provide a first-order characterization of optimality for these two problems, and prescribe an enumerative algorithm based on a partitioning of the dual space in order to optimally solve them. An extension of these algorithms for solving the capacitated, unbalanced 2-median problem on a tree graph is also given."],"dc:description.degree":["M.S."],"dc:format.mimetype":["application/pdf"],"dc:identifier.uri":["http://hdl.handle.net/10919/91146"],"dc:language.iso":["en_US"],"dc:publisher":["Virginia Polytechnic Institute and State University"],"dc:rights":["In Copyright"],"dc:rights.uri":["http://rightsstatements.org/vocab/InC/1.0/"],"dc:title":["Capacitated, unbalanced p-median problems on a chain graph with a continuum of link demands"],"dc:type":["Thesis"],"dc:type.dcmitype":["Text"],"thesis:degree_discipline":["Industrial Engineering and Operations Research"],"thesis:degree_level":["masters"],"thesis:degree_name":["M.S."],"thesis:institution_name":["Virginia Polytechnic Institute and State University"]},"updated_at":"2026-07-22T22:19:37Z"}