Non-linear Integer Programming Model and Algorithms for Connected p-facility Location Problem
作者机构: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.