A hierarchical flow capturing location problem with demand attraction based on facility size, and its Lagrangian relaxation solution method
A hierarchical flow capturing location problem with demand attraction based on facility size, and its Lagrangian relaxation solution method
复制标题
基于设施规模的需求吸引分层流量捕获选址问题及其拉格朗日松弛求解方法
DOI：
10.1111/j.1538-4632.2011.00837.x
复制
发表时间：
2012
影响因子：
3.6
通讯作者：
K. Tanaka and T. Furuta
中科院分区：
文献类型：
--
作者：
Makoto Yamashita;Katsuki Fujisawa;Mituhiro Fukuda;Kazuhiro Kobayashi;Kazuhide Nakata;Maho Nakata;八木恭子・高嶋隆太;K. Tanaka and T. Furuta
提出了一种分层流捕获选址问题（HFCLP），并提出了一种有效的拉格朗日启发式求解方法。原始的流量捕获选址问题（FCLP）的目的是在网络上找到一个给定数量的设施，以最大限度地提高总流量，可以在设施沿着其预先计划的路线，如每天通勤上班。我们扩展了原来的模型，允许决策者选择m个不同大小的替代品中的设施的大小。大型设施被认为更具吸引力，因此可以吸引更多的客户，但它们的建设成本高于小型设施。当设施的规模足够大时，客户偏离其预先计划的路线来访问设施的服务。偏离原始路径的程度是通过客户必须到达设施的额外距离来测量的，并且可接受的偏离距离随着设施的大小的增加而变大。本文提出了一个新的问题，在这个问题中，每种规模的设施的数量和它们的位置是同时确定的，以便在可用于定位所有设施的总预算内捕获尽可能多的流量。我们提出了一个整数规划制定的问题，并设计了一个拉格朗日松弛的解决方法。所提出的算法进行了测试，使用道路网络与300和500个节点。结果表明，该方法在相当短的时间内产生高质量的解决方案。
This article presents a hierarchical flow capturing location problem (HFCLP) and proposes an effective Lagrangian heuristic solution method. The original flow capturing location problem (FCLP) aims to locate a given number of facilities on a network to maximize the total flow that can be serviced at facilities along their preplanned routes, such as daily commute to work. We extend the original model to allow a decision maker to select the size of facilities among m different size alternatives. Larger facilities are assumed to be more attractive and, therefore, can attract more customers, but they cost more to construct than smaller ones. Customers deviate from their preplanned routes to access a facility's service when the size of the facility is sufficiently large. The degree of deviation from the original path is measured by the additional distance customers have to go to access facilities, and the acceptable deviation distance becomes larger as the size of a facility increases. This article presents a new problem in which the number of facilities of each size and their locations are simultaneously determined so as to capture as much flow as possible within the total budget available for locating all facilities. We present an integer programming formulation of the problem and devise a Lagrangian relaxation solution method. The proposed algorithm is tested using road networks with 300 and 500 nodes. The results show that the method produces high-quality solutions in a fairly short time.