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

作     者：Jianming ZHU 

作者机构：College of Engineering and Information Technology University of Chinese Academy of Sciences 

出 版 物：《Journal of Systems Science and Information》 (系统科学与信息学报)

年 卷 期：2014年第2卷第5期

页      面：451-460页

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 07[理学] 070105[理学-运筹学与控制论] 0701[理学-数学] 

基　　金：Supported by the National Natural Science Foundation of China(Grant No.91324012 71001099 91024031) 

主　　题：connected location maximum clique heuristic algorithm genetic algorithm 

摘      要：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(Cp LP) is to choose p vertices from V so as to minimize the total cost of shortest path of pair-wise of these p *** problem is proved to be NP-hard and non-linear integer programming is formulated. Then, two algorithms are designed for solving the Cp LP. 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.