Non-linear Integer Programming Model and Algorithms for Connected p-facility Location Problem

Zhu Jianming ()
Additional contact information
Zhu Jianming: College of Engineering and Information Technology, University of Chinese Academy of Sciences, Beijing100049, China

Journal of Systems Science and Information, 2014, vol. 2, issue 5, 451-460

Abstract: In this paper, a new location analysis method is presented. Given a connected graph G = (V, E)with nonnegative edge cost ce for each edge e ∊ E, dij is the cost of the shortest path between vertices i and j in the graph. The Connected p-facility Location Problem (CpLP) is to choose p vertices from V so as to minimize the total cost of shortest path of pair-wise of these p vertices. This problem is proved to be NP-hard and non-linear integer programming is formulated. Then, two algorithms are designed for solving the CpLP. One is a heuristic algorithm based on classical maximum clique approach, while the second one is genetic algorithm. Finally, computational results show the comparison between these two algorithms.

Keywords: connected location; maximum clique; heuristic algorithm; genetic algorithm (search for similar items in EconPapers)
Date: 2014
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://doi.org/10.1515/JSSI-2014-0451 (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:bpj:jossai:v:2:y:2014:i:5:p:451-460:n:6

DOI: 10.1515/JSSI-2014-0451

Access Statistics for this article

Journal of Systems Science and Information is currently edited by Shouyang Wang

More articles in Journal of Systems Science and Information from De Gruyter
Bibliographic data for series maintained by Peter Golla ().