Repositorio de producción científica de la Universidad de Sevilla

The bi-criteria doubly weighted center-median path problem on a tree


Advanced Search

Show simple item record

dc.creator Puerto Albandoz, Justo es
dc.creator Rodríguez Chía, Antonio Manuel es
dc.creator Tamir, Arie es
dc.creator Pérez Brito, Dionisio es 2016-10-20T10:37:32Z 2016-10-20T10:37:32Z 2006-07
dc.identifier.citation Puerto Albandoz, J., Rodríguez Chía, A.M., Tamir, A. y Pérez Brito, D. (2006). The bi-criteria doubly weighted center-median path problem on a tree. Networks, 47 (4), 237-247.
dc.identifier.issn 0028-3045 es
dc.identifier.issn 1097-0037 es
dc.description.abstract Given a tree network T with n nodes, let PL be the subset of all discrete paths whose length is bounded above by a prespecified value L. We consider the location of a path-shaped facility P ∈ PL, where customers are represented by the nodes of the tree. We use a bi-criteria model to represent the total transportation cost of the customers to the facility. Each node is associated with a pair of nonnegative weights: the center-weightand the median-weight. In this doubly weighted model, a path P is assigned a pair of values (MAX (P ), SUM (P )),which are, respectively, the maximum center-weighted distance and the sum of the median-weighted distances from P to the nodes of the tree. Viewing PL and the planar set {(MAX (P), SUM (P )) : P ∈ PL} as the decisionspace and the bi-criteria or outcome space respectively,we focus on finding all the nondominated points of the bi-criteria space. We prove that there are at most 2n non-dominated outcomes, even though the total number of efficient paths can be Ω(n2), and they can all be generated in O(n log n) optimal time. We apply this result to solve the cent-dian model, whose objective is a convex combination of the weighted center and weighted median functions. We also solve the restricted models, where the goal is to minimize one of the two functions MAX or SUM, subject to an upper bound on the other one, both withand without a constraint on the length of the path. All these problems are solved in linear time, once the set of non dominated outcomes has been obtained, which in turn, results in an overall complexity of O(n log n). The latter bounds improve upon the best known results by a factor of O(log n). es
dc.description.sponsorship Ministerio de Ciencia y Tecnología es
dc.format application/pdf es
dc.language.iso eng es
dc.publisher Wiley es
dc.relation.ispartof Networks, 47 (4), 237-247.
dc.rights Attribution-NonCommercial-NoDerivatives 4.0 Internacional *
dc.rights.uri *
dc.subject Location on trees es
dc.subject Bi-criteria location es
dc.subject Center-median paths es
dc.subject Length constrained paths es
dc.title The bi-criteria doubly weighted center-median path problem on a tree es
dc.type info:eu-repo/semantics/article es
dc.type.version info:eu-repo/semantics/submittedVersion es
dc.rights.accessrights info:eu-repo/semantics/openAccess es
dc.contributor.affiliation Universidad de Sevilla. Departamento de Estadística e Investigación Operativa es
dc.relation.projectID BFM2001-2378 es
dc.relation.projectID BFM2001-4028 es
dc.relation.projectID BFM2004-0909 es
dc.relation.projectID HA2003-0121 es
dc.relation.publisherversion es
dc.identifier.doi 10.1002/net.20112 es Universidad de Sevilla. FQM331: Métodos y Modelos de la Estadística y la Investigación Operativa es
idus.format.extent 29 p. es
dc.journaltitle Networks es
dc.publication.volumen 47 es
dc.publication.issue 4 es
dc.publication.initialPage 237 es
dc.publication.endPage 247 es
dc.contributor.funder Ministerio de Ciencia y Tecnología (MCYT). España
Size: 262.4Kb
Format: PDF

This item appears in the following Collection(s)

Show simple item record