检索结果-内蒙古大学图书馆

A heuristic for BILP problems: The Single Source Capacitated Facility Location Problem

EUROPEAN JOURNAL OF OPERATIONAL REsearch 2014年第2期238卷 438-450页

作者： Guastaroba, G. Speranza, M. G. Univ Brescia Dept Econ & Management Brescia Italy

In the Single Source Capacitated Facility Location Problem (SSCFLP) each customer has to be assigned to one facility that supplies its whole demand. The total demand of customers assigned to each facility cannot exceed its capacity. An opening cost is associated with each facility, and is paid if at least one customer is assigned to it. The objective is to minimize the total cost of opening the facilities and supply all the customers. In this paper we extend the kernel search heuristic framework to general Binary Integer Linear Programming (BILP) problems, and apply it to the SSCFLP. The heuristic is based on the solution to optimality of a sequence of subproblems, where each subproblem is restricted to a subset of the decision variables. The subsets of decision variables are constructed starting from the optimal values of the linear relaxation. Variants based on variable fixing are proposed to improve the efficiency of the kernel search framework. The algorithms are tested on benchmark instances and new very large-scale test problems. Computational results demonstrate the effectiveness of the approach. The kernel search algorithm outperforms the best heuristics for the SSCFLP available in the literature. It found the optimal solution for 165 out of the 170 instances with a proven optimum. The error achieved in the remaining instances is negligible. Moreover, it achieved, on 100 new very large-scale instances, an average gap equal to 0.64% computed with respect to a lower bound or the optimum, when available. The variants based on variable fixing improved the efficiency of the algorithm with minor deteriorations of the solution quality. (c) 2014 Elsevier B.V. All rights reserved.

关键词： Single Source Capacitated Facility Location Problems Binary Integer Linear Programming Heuristic algorithms kernel search framework

来源：评论

学校读者我要写书评

暂无评论

kernel search for the capacitated facility location problem

引用

JOURNAL OF HEURISTICS 2012年第6期18卷 877-917页

作者： Guastaroba, G. Speranza, M. G. Univ Brescia Dept Quantitat Methods Brescia Italy

The Capacitated Facility Location Problem (CFLP) is among the most studied problems in the OR literature. Each customer demand has to be supplied by one or more facilities. Each facility cannot supply more than a given amount of product. The goal is to minimize the total cost to open the facilities and to serve all the customers. The problem is NP-hard. The kernel search is a heuristic framework based on the idea of identifying subsets of variables and in solving a sequence of MILP problems, each problem restricted to one of the identified subsets of variables. In this paper we enhance the kernel search and apply it to the solution of the CFLP. The heuristic is tested on a very large set of benchmark instances and the computational results confirm the effectiveness of the kernel search framework. The optimal solution has been found for all the instances whose optimal solution is known. Most of the best known solutions have been improved for those instances whose optimal solution is still unknown.

关键词： Capacitated facility location problems Mixed-integer linear programming Heuristic algorithm Core algorithm kernel search framework

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：