Article
The bicriteria doubly weighted centermedian path problem on a tree
Author/s  Puerto Albandoz, Justo
Rodríguez Chía, Antonio Manuel Tamir, Arie Pérez Brito, Dionisio 
Department  Universidad de Sevilla. Departamento de Estadística e Investigación Operativa 
Publication Date  200607 
Deposit Date  20161020 
Published in 

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 prespeciﬁed value L. We consider the location of a pathshaped facility P ∈ PL, where customers are represented ... Given a tree network T with n nodes, let PL be the subset of all discrete paths whose length is bounded above by a prespeciﬁed value L. We consider the location of a pathshaped facility P ∈ PL, where customers are represented by the nodes of the tree. We use a bicriteria model to represent the total transportation cost of the customers to the facility. Each node is associated with a pair of nonnegative weights: the centerweightand the medianweight. In this doubly weighted model, a path P is assigned a pair of values (MAX (P ), SUM (P )),which are, respectively, the maximum centerweighted distance and the sum of the medianweighted 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 bicriteria or outcome space respectively,we focus on ﬁnding all the nondominated points of the bicriteria space. We prove that there are at most 2n nondominated outcomes, even though the total number of efﬁcient paths can be Ω(n2), and they can all be generated in O(n log n) optimal time. We apply this result to solve the centdian 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). 
Funding agencies  Ministerio de Ciencia y Tecnología (MCYT). España 
Project ID.  BFM20012378
BFM20014028 BFM20040909 HA20030121 
Citation  Puerto Albandoz, J., Rodríguez Chía, A.M., Tamir, A. y Pérez Brito, D. (2006). The bicriteria doubly weighted centermedian path problem on a tree. Networks, 47 (4), 237247. 
Files  Size  Format  View  Description 

The bicriteria doubly weighted ...  262.4Kb  [PDF]  View/  