软容量限制设施选址问题的竞争决策算法

软容量设施选址问题是NP-Hard问题之一,具有广泛的应用价值。为了求解软容量设施选址问题,提出一种基于数学性质的竞争决策算法。首先研究该问题的数学性质,运用这些数学性质不仅可以确定某些设施必定开设或关闭,还可以确定部分顾客由哪个设施提供服务,从而缩小问题的规模,加快求解速度。在此基础上设计了求解该问题的竞争决策算法,最后经过一个小规模的算例测试并与精确算法的结果比较,得出了最优解;针对大规模的问题快速地求出了可行解,得到了令人满意的结果。     

求解无容量设施选址问题的混合蝙蝠算法

无容量设施选址（Un-capacitated Facility Location,UFL）问题是可以运用于不同领域的经典优化难题。蝙蝠算法（Bat Algorithm,BA）是一种新的群智能优化算法,目前还未被应用到无容量设施选址问题的求解中。针对蝙蝠算法易陷入局部最优、收敛精度低、后期收敛速度慢的缺点,并结合无容量设施选址问题的具体特征,将三种局部搜索策略、和声搜索机制与基本蝙蝠算法相结合,使用一种新的随机游走法则公式改善蝙蝠的搜索能力,设计了求解无容量设施选址问题的混合蝙蝠算法。通过实例测试将混合蝙蝠算法与其他算法进行比较,验证了该算法求解无容量设施选址问题的有效性与可行性。     

带惩罚的无容量设施选址问题的降阶回溯算法

无容量设施选址问题（Uncapacitated Facility Location Problem;UFLP）是组合优化中经典的NP-Hard问题之一。针对UFLP的变形问题之一;即带惩罚的无容量设施选址问题（Uncapacitated Facility Location Problem With Penalties;UFLPWP）;研究了UFLPWP的数学性质;其中包括可以批量确定某些设施一定关闭的性质;并进行了数学证明;利用这些数学性质可以对问题进行降阶;进而缩小问题的规模。在此基础上设计了基于上、下界的回溯算法来求解UFLPWP。通过一个示例分析;进一步阐述该算法的原理。     

多周期竞争性设施选址问题优化研究

市场的复杂多变给企业服务设施的选址带来新的挑战,设施选址决策需考虑市场的动态特性进行多周期维度的决策优化。文章构建了一个多周期的设施竞争选址模型,以覆盖需求最大化为目标,对设施位置与进行决策优化,并选用NSGA算法对双目标模型进行求解,算例结果验证了算法与模型的有效性。     

农垦系统应急物资设施选址问题研究磁

论文对农垦系统应急物资储备库选址问题进行研究,综合了 P-中值模型、P-中心模型、覆盖模型等一般选址模型的优缺点,同时考虑到应急设施选址的效率性、公平性和成本等多方面因素,建立了一个多目标决策模型。该模型采用线性加权和法求解,得出应急设施的最优选址点。经齐齐哈尔垦区应急行动检验,多目标决策模型的计算结果科学合理、经济可行,为应急设施选址决策提供了有效依据。     

应急设施选址问题研究综述

合理的应急设施选址能够显著提高应急服务的质量和效率,在医疗、救灾和人道主义物流等领域具有重要的研究意义。根据时效性和应用领域对应急设施进行分类,从不同设施种类的角度阐述国内外研究的主要区别。按照基本选址问题、动态选址问题、随机选址问题、鲁棒选址问题和其他选址问题5种类型论述应急设施选址模型的研究现状,从求解方式、优化算法、测试用例3个角度对模型优化求解方法进行对比分析,指出当前研究存在的不足,并对应急设施选址问题的未来研究方向进行展望。     

基于混合需求的设施选址问题研究

研究网络中设施的需求一部分来自于网络节点, 一部分来自于过往流量的基于混合需求的设施选址问题。引入引力模型, 以新建设施获得总利润最大为目标建立非线性整数规划模型, 并构造启发式算法, 通过MATLAB进行仿真实验, 将求解结果与GPAH算法及精确算法的结果进行比较。比较结果表明, 提出的算法求解质量高、运行速度快, 可用于大中型网络设施的选址问题。     

基于竞争环境的截流设施选址与车辆路径问题

研究竞争环境下截流设施选址与带时间窗的多中心车辆路径问题。首先,在考虑设施覆盖范围衰退的情况下,利用阶梯型效用函数和偏离距离描述消费者的选择行为,并确定截流设施的需求量;然后,采用基于聚集度的启发式算法对门店进行分类,借助双层规划法,建立门店选址与车辆路径安排的多目标整数规划模型;最后,采用改进的蚁群算法进行求解。通过分析对比实验结果,验证了模型的有效性和可行性。     

CoSTUR: 面向用户评级的空间文本竞争选址

随着GPS定位技术和移动互联网的发展,各类LBS(location-based service)应用积累了大量带有位置和文本标记的空间文本数据,这些数据广泛应用于市场营销、城市规划等设施选址决策中.空间文本选址的目标是从候选位置集合中挖掘最佳地点新建设施,以期影响最多空间文本对象,如用户或车辆等,其中空间距离越接近且文本越相似则影响力越大.现有方案未考虑现实普遍存在的同行竞争,也忽略了用户对设施的评价因素.为更合理地在同行竞争环境结合用户评级进行选址决策,本文提出新的空间文本竞争选址问题CoSTUR.通过引入权衡影响的确定性和数量的阈值,解决传统模型中对象只能被单一设施影响的局限,建模了用户可能同时受多个设施影响的真实情况.借鉴经典的竞争均分模型,实现了不同评级设施间竞争量化.为降低大规模数据导致的高昂计算代价,构建了新型空间文本索引结构TaR-tree,并结合阈值设计基于影响范围的两个剪枝策略,实现基于分支定界思想的空间连接和范围查询两种方案.在真实和合成数据集上的实验结果显示,相比基线算法计算效率能够提升近一个量级,说明提出方法的有效性.     

基于设施选址的Steiner问题的算法

在设施选址问题的基础上给出了广义Steiner树-星问题的两个近似比分别为3．55和3．582的近似算法,并在问题转化的基础上研究了其他若干特殊情形的Steiner树问题的近似算法。     

Facility location dynamics: An overview of classifications and applications

In order to modify the current facility or develop a new facility, the dynamics of facility location problems (FLPs) ought to be taken into account so as to efficiently deal with changing parameters such as market demand, internal and external factors, and populations. Since FLPs have a strategic or long-term essence, the inherited uncertainty of future parameters must be incorporated in relevant models, so these models can be considered applicable and ready to implement. Furthermore, due to largely capital outlaid, location or relocation of facilities is basically considered as a long-term planning. Hence, regarding the way in which relevant criteria will change over time, decision makers not only are concerned about the operability and profitability of facilities for an extended period, but also seek to robust locations fitting well with variable demands. Concerning this fact, a trade-off should be set between benefits brought by facility location changes and costs incurred by possible modifications. This review reports on literature pointing out some aspects and characteristics of the dynamics of FLPs. In fact, this paper aims not only to review most variants of these problems, but also to provide a broad overview of their mathematical formulations as well as case studies that have been studied by the literature. Finally, based on classified research works and available gaps in the literature, some possible research trends will be pointed out.     

The multi-period incremental service facility location problem

In this paper we introduce the multi-period incremental service facility location problem where the goal is to set a number of new facilities over a finite time horizon so as to cover dynamically the demand of a given set of customers. We prove that the coefficient matrix of the allocation subproblem that results when fixing the set of facilities to open is totally unimodular. This allows to solve efficiently the Lagrangean problem that relaxes constraints requiring customers to be assigned to open facilities. We propose a solution approach that provides both lower and upper bounds by combining subgradient optimization to solve a Lagrangean dual with an ad hoc heuristic that uses information from the Lagrangean subproblem to generate feasible solutions. Numerical results obtained in the computational experiments show that the obtained solutions are very good. In general, we get very small percent gaps between upper and lower bounds with little computation effort.     

School location methodology in urban areas of developing countries

This study is concerned with the location of primary public schools. The public system should have the capacity to satisfy all the demand, although students may choose between public and private schools if they can afford the corresponding costs. A number of factors, such as questionable education quality, limited capacity, poor location and social preferences, secure a participation of about 30% to the private school system. The purpose of this study is both the evaluation of the existing public school network and a relocation proposal. The result of the former was the identification of areas with shortage and excess in school offer. The latter suggests school relocation using capacitated and uncapacitated models. ArcView, a software of the geographic information system (GIS) family, was employed, allowing the efficient handling of large problems and improving the presentation and evaluation of the findings. This methodology was applied to the primary public school network in the area of Vitoria, a state capital located in the southeast region of Brazil with about 300,000 inhabitants. Finally, the practical use of this study and its importance for planning purposes are discussed.     

Lower and upper bounds for the two-echelon capacitated location-routing problem

In this paper, we introduce two algorithms to address the two-echelon capacitated location-routing problem (2E-CLRP). We introduce a branch-and-cut algorithm based on the solution of a new two-index vehicle-flow formulation, which is strengthened with several families of valid inequalities. We also propose an adaptive large-neighbourhood search (ALNS) meta-heuristic with the objective of finding good-quality solutions quickly. The computational results on a large set of instances from the literature show that the ALNS outperforms existing heuristics. Furthermore, the branch-and-cut method provides tight lower bounds and is able to solve small- and medium-size instances to optimality within reasonable computing times.     

一个关于求解k-种产品选址问题的近似算法

对于k-种产品工厂选址问题,有如下描述：存在一组客户和一组可以建立工厂的厂址。现在有k种不同的产品,要求每一个客户必须由k个不同的工厂来提供k种不同的产品,其中每个工厂都只能为客户提供唯一的一种产品。在该问题中,假定建厂费用以及任意两个结点之间的运输费用都为非负,并且任意两个结点之间的运输费用都满足对称和三角不等式关系的性质。问题的要求是要从若干厂址中选择一组厂址来建立工厂,给每个工厂指定一种需要生产的产品,并且给每一个客户提供一组指派使每个客户都能有k个工厂来为其供应这k种不同的产品。对于此类问题,优化目标是最小化建厂费用以及运输费用。论文在假设建厂费用为零的前提下,提出了求解该类问题的一种最坏性能比为3k/2-1的近似算法。