p-Cable Trench Problem with Covering

dc.creatorMarianov, Vladimir
dc.creatorGutiérrez-Jarpa, Gabriel
dc.creatorObreque-Niñez, Carlos Enrique
dc.date2018-09-20T13:24:55Z
dc.date2022-06-18T19:24:07Z
dc.date2018-09-20T13:24:55Z
dc.date2022-06-18T19:24:07Z
dc.date2015-05-22
dc.date2015
dc.date2015-05-20
dc.date.accessioned2023-08-21T23:25:08Z
dc.date.available2023-08-21T23:25:08Z
dc.identifier1130878
dc.identifierhttps://hdl.handle.net/10533/220556
dc.identifier.urihttps://repositorioslatinoamericanos.uchile.cl/handle/2250/8295255
dc.descriptionWe introduce the p-Cable Trench problem with Covering. In this problem, p primary servers (e.g., routers) are located and a set of secondary servers (e.g., extended range WiFi antennas) is connected to each of them, to achieve complete demand coverage by a service (e.g., WiFi), at minimum cost. The topology is a forest, in which the primary servers are roots of trees whose leaves and some other nodes are occupied by secondary servers. Some of the nodes of the trees are Steiner XXII EURO Working Group on Locational Analysis Meeting 2015 2 nodes. Both primary and secondary servers provide the service within a coverage radius. The cost is composed by a trench digging cost and a cable cost. Each secondary server requires a single, dedicated cable connecting it to a primary server, and all cables must lie in a trench. The p-cable trench problem with covering is a generalization of several known problems: • If the coverage radius is zero and the location of primary and secondary servers is known, the problem becomes the Fixed Charge Network Design Problem. • If the coverage radius and construction cost are equal to zero and the location of the secondary servers (antennae) is known, the problem becomes the p-median problem. • If p=1, the location of the antennae is known and the coverage radius is equal to zero, the problem becomes the cable trench problem. • If the coverage radius is zero and location of the antennae is known, it becomes the p-cable trench problem. • If p=1 and the cost of distance is zero, it becomes the covering tree problem. We propose a linear integer optimization model based on multicommodity flow, which we solve using two different Lagrangian relaxations, and a heuristic based on a modified set covering. We solve instances of up to 200 nodes, and also an application for locating WiFi antennas in Viña del Mar, Chile.
dc.languageeng
dc.relationinstname: Conicyt
dc.relationreponame: Repositorio Digital RI2.0
dc.relationEURO Working Group on Locational Analysis
dc.relation22
dc.relationinfo:eu-repo/grantAgreement//1130878
dc.relationinfo:eu-repo/semantics/dataset/hdl.handle.net/10533/93486
dc.rightsinfo:eu-repo/semantics/openAccess
dc.rightsAttribution-NonCommercial-NoDerivs 3.0 Chile
dc.rightshttp://creativecommons.org/licenses/by-nc-nd/3.0/cl/
dc.titlep-Cable Trench Problem with Covering
dc.typePonencia
dc.typeinfo:eu-repo/semantics/lecture
dc.coverageBudapest


Este ítem pertenece a la siguiente institución