Please use this identifier to cite or link to this item: https://scholarbank.nus.edu.sg/handle/10635/87030
DC FieldValue
dc.titleHeuristic algorithms for general k-level facility location problems
dc.contributor.authorLi, R.
dc.contributor.authorHuang, H.-C.
dc.contributor.authorHuang, J.
dc.date.accessioned2014-10-07T10:23:28Z
dc.date.available2014-10-07T10:23:28Z
dc.date.issued2013-01
dc.identifier.citationLi, R., Huang, H.-C., Huang, J. (2013-01). Heuristic algorithms for general k-level facility location problems. Journal of the Operational Research Society 64 (1) : 106-113. ScholarBank@NUS Repository.
dc.identifier.issn01605682
dc.identifier.urihttp://scholarbank.nus.edu.sg/handle/10635/87030
dc.description.abstractIn a general k-level uncapacitated facility location problem (k-GLUFLP), we are given a set of demand points, denoted by D, where clients are located. Facilities have to be located at a given set of potential sites, which is denoted by F in order to serve the clients. Each client needs to be served by a chain of k different facilities. The problem is to determine some sites of F to be set up and to find an assignment of each client to a chain of k facilities so that the sum of the setup costs and the shipping costs is minimized. In this paper, for a fixed k, an approximation algorithm within a factor of 3 of the optimum cost is presented for k-GLUFLP under the assumption that the shipping costs satisfy the properties of metric space. In addition, when no fixed cost is charged for setting up the facilities and k2, we show that the problem is strong NP-complete and the constant approximation factor is further sharpen to be 3/2 by a simple algorithm. Furthermore, it is shown that this ratio analysis is tight. © 2013 Operational Research Society Ltd. All rights reserved.
dc.description.urihttp://libproxy1.nus.edu.sg/login?url=http://dx.doi.org/10.1057/jors.2012.31
dc.sourceScopus
dc.subjectcomputational complexity
dc.subjectfacility location
dc.subjectheuristic
dc.subjectlinear programming
dc.subjectNP-complete
dc.subjectoptimization
dc.typeArticle
dc.contributor.departmentINDUSTRIAL & SYSTEMS ENGINEERING
dc.description.sourcetitleJournal of the Operational Research Society
dc.description.volume64
dc.description.issue1
dc.description.page106-113
dc.description.codenJORSD
dc.identifier.isiut000314086100009
Appears in Collections:Staff Publications

Show simple item record
Files in This Item:
There are no files associated with this item.

Page view(s)

46
checked on Mar 29, 2020

Google ScholarTM

Check


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.