期刊
APPLIED SOFT COMPUTING
卷 67, 期 -, 页码 261-275出版社
ELSEVIER
DOI: 10.1016/j.asoc.2018.03.008
关键词
p-Median problem; Mixed integer linear programming; Variable neighborhood search metaheuristic; Backbone facility locations
资金
- Proyectos Dicyt Codigos [061713AS, 061513VC_DAS]
- Vicerrectoria de Investigacion, Desarrollo e Innovacion
In this paper, we propose new mixed integer linear programming (MILP) models for the p-Median problem subject to ring, tree and star backbone topology constraints on the facility locations. More precisely, we minimize simultaneously the total connection cost distances between customers and facilities, and cost distances among facilities when connected under a ring, tree or a star network topology. In principle, all our proposed models can be used in any application related with the classical p-Median problem. Application examples include wired and wireless network design, computer networks, transportation, water supply and electrical networks, just to name a few. The proposed models arise as a combination of the classical p-Median problem with the traveling salesman, spanning tree, and star network problems, respectively. We prove the correctness of each proposed model. Then, we further propose variable neighborhood search (VNS) meta-heuristic algorithms, one for each topology. Our numerical results indicate that the ring models are harder to solve with CPLEX than the tree and star ones. Whilst VNS algorithms proved to be highly efficient when compared to the optimal solutions of the problem for small, medium and large size instances. Moreover, we obtain better feasible solutions than CPLEX for the large instances and in significantly less computational cost. (C) 2018 Elsevier B.V. All rights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据