Premium
Minisum multipurpose trip location problem on trees
Author(s) -
Araghi Mojtaba,
Berman Oded,
Averbakh Igor
Publication year - 2014
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.21531
Subject(s) - facility location problem , type (biology) , computer science , node (physics) , type of service , service (business) , tree (set theory) , mathematical optimization , flow network , transportation theory , 1 center problem , fixed cost , operations research , mathematics , combinatorics , engineering , business , ecology , accounting , structural engineering , marketing , biology
We consider the problem of locating facilities of two types at nodesof a tree network. Customers may need just one type of service, or bothtypes; in the latter case, to minimize transportation costs, the customers visit facilities of both types in a single trip. Each facility incurs a fixed cost that depends on the type of the facility and the node where it is located. It is required to minimize the sum of the total transportation and fixed costs. For the problem with a single facility of each type, we present an O ( n ) exact algorithm, which improves on the O ( n 3 ) algorithm presented in [2]. For the problem with multiple facilities of each type, we present an O ( n 5 ) algorithm. © 2013 Wiley Periodicals, Inc. NETWORKS, Vol. 63(2), 154–159 2014