期刊
DISCRETE APPLIED MATHEMATICS
卷 133, 期 1-3, 页码 3-28出版社
ELSEVIER SCIENCE BV
DOI: 10.1016/S0166-218X(03)00431-1
关键词
obnoxious location-routing; Lagrangean heuristic; branch-and-bound
The problem of simultaneously locating obnoxious facilities and routing obnoxious materials between a set of built-up areas and the facilities is addressed. Obnoxious facilities are those facilities which cause exposure to people as well as to the environment i.e. dump sites, chemical industrial plants, electric power supplier networks, nuclear reactors and so on. A discrete combined location-routing model, which we refer to as Obnoxious Facility Location and Routing model (OFLR), is defined. OFLR is a NP-hard problem for which a Lagrangean heuristic approach is presented. The Lagrangean relaxation proposed allows to decompose OFLR into a Location subproblem and a Routing subproblem; such subproblems are then strengthened by adding suitable inequalities. Based on this Lagrangean relaxation two simple Lagrangean heuristics are provided. An effective Branch and Bound algorithm is then presented, which aims at reducing the gap between the above mentioned lower and upper bounds. Our Branch and Bound exploits the information gathered while going down in the enumeration tree in order to solve efficiently the subproblems related to other nodes. This is accomplished by using a bundle method to solve at each node the Lagrangean dual. Some variants of the proposed Branch and Bound method are defined in order to identify the best strategy for different classes of instances. A comparison of computational results relative to these variants is presented. (C) 2003 Elsevier B.V. All rights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据