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

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

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

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

基于设施选址问题的费用分配问题的近似算法

许多有着重要理论和应用价值的最优化问题在算法复杂性上都是NP-hard的,其解决方法之一是近似算法。论文研究了与设施选址问题密切相关的费用分配问题,并利用原始与对偶线性规划的思想和无容量设施选址问题的一个1.52-近似算法[1]给出了该问题的一个更好的近似算法。     

二级垃圾回收中转设施选址问题的降阶回溯算法

随着我国城市化进程的加快和经济的高速发展,城市中因生产生活所产生的垃圾废料量日益增加,如何有效地建立回收中转设施是当前社会需要解决的问题。对二级垃圾回收设施选址问题进行研究,其实质为组合优化中的NP-hard问题。首先根据实际情况对二级垃圾回收中转设施选址问题进行数学建模,研究该问题的数学性质并给予证明,利用这些性质减小问题规模,降低求解难度;然后设计符合该问题的分配子算法、上下界子算法,基于以上算法提出一种可以在减小问题规模的同时得到精确解的降阶回溯算法;最后通过分析和模拟若干个示例进一步阐述该算法的原理及执行过程,结果表明该算法能通过减小问题规模,降低问题求解的难度。     

考虑逆向物流第三方配送的选址路径问题研究

针对电子商务退货的大量产生,提出一种送取一体化的配送方式,第三方物流和自建物流结合的逆向物流配送策略。选址和路径问题LRP（Location Routing Problem）成为了很多物流配送企业正在面对和急需解决的难题。为了降低配送方式成本以及提高客户满意度,利用改进的遗传算法,首先在自建物流成本中加入时间窗惩罚函数,偏远地区的配送采用第三方物流配送方式,建立送取货为一体的逆向物流选址路径模型;然后针对问题的复杂性设计一种改进的遗传算法对模型进行求解,采用时间分布思想初始化种群,引入局部搜索算法,设计自适应的改进遗传算法;最后采用实验进行数据分析,通过物流成本的降低、运行时间的减少、运行效率的提高等数据验证了模型的可行性以及算法的有效性。     

一个带收集点的逆向物流模型设计

从绿色供应链管理（GSCM）的思想出发,提出了一个分布式逆向物流的数学规划模型,主要研究逆向物流网络中带有收集点的物流成本优化问题,同时为了简化模型,给出了解决这个问题的启发式算法。该方法通过启发式的集中过程,可以减少子问题的决策变量集以及迭代次数而达到最优,并对容量受限的选址运输问题（CPLP）进行了改进。测试结果表明,该方法可以通过适中的计算工作量而得到较高质量的结果。     

最小费用充电站选址问题的分支定界算法

电动汽车的充电站选址问题是当前社会的热点问题,其实质是组合优化中经典的NP-hard问题。基于最小开设费用对充电站选址问题进行研究,首先对该问题进行了数学建模,进而研究了该问题的数学性质并给予相应的证明,利用这些性质减小问题的规模,从而降低问题的求解难度;然后设计了上下界子算法以及降阶子算法,基于这些子算法提出了一种可以快速缩小问题规模同时得到最优解的分支定界算法,降低了时间复杂度,同时可以对解空间进行大量剪枝加快求解速度;最后通过分析和求解一个示例来进一步阐述所提算法的原理和执行过程。     

疫情期间生活物资集散点选址问题的降阶回溯算法

疫情爆发后,封控区内居民的生活物资发放问题成为亟待解决的焦点问题之一,该问题可抽象为疫情期间生活物资集散点选址问题,其实质为组合优化中的NP-hard问题。基于疫情封控期间的应急生活物资集散点选址问题的精确算法进行研究,首先得出一些可以降低问题规模的数学性质并证明利用这些性质可以减小问题规模,降低问题的求解难度;然后设计出分配子算法、上下界子算法以及降阶子算法;基于这些子算法提出一种可以减小问题规模同时得到最优解的降阶回溯算法;最后通过分析和求解若干个示例进一步阐述该算法的原理和执行过程,结果表明该算法能通过减小问题规模来降低问题求解的难度。     

多约束选址—路径问题的改进混合遗传算法研究

选址—路径问题(LRP)同时解决设施选址和车辆路径问题,使物流系统总成本达到最小,在集成化物流配送网络规划中具有重要意义。针对带仓库容量约束和路径容量约束的选址—路径(CLRP)问题,提出了一种结合模拟退火算法的混合遗传算法进行整体求解。改进混合遗传算法分别对初始种群生成方式、遗传操作和重组策略进行改进,并实现了模拟退火的良好局部搜索能力与遗传算法的全局搜索能力的有效结合。运用一组Barreto Benchmark算例进行数值实验测试其性能,并将求解结果与国外文献中的启发式算法进行比较,验证了改进混合算法的有效性和可行性。     

基于进化计算的洒水车路径优化问题的求解

在利用进化计算对容量限制弦路径车辆行驶问题（Capacitated Arc Routing Problem,CARP）进行研究的基础上,对其数学模型、可行化算子进行改进,以适应实际生活中洒水车车辆路径优化问题。针对此问题,设计了局部搜索（Local Search）算子,此算子在染色体进化中有着显著的作用。来自于现实生活中的某市政环卫部门的实验数据真实可靠。通过进化计算对数据的求解,不仅得到了满意的结果,而且证明了该算法的可靠性及稳定性。在把计算后得出的优化路径用于实际洒水车线路安排后,其环卫部门节约了一定的人力物力,取得了一定的经济效益。根据实验分析,该算法能有效求解一定规模的CARP,并且具有一定的实用价值。     

An Approximation Algorithm for a Large-Scale Facility Location Problem

We developed a new practical optimization method that gives approximate solutions for large-scale real instances of the Uncapacitated Facility Location Problem. The optimization consists of two steps: application of the Greedy—Interchange heuristic using a small subset of warehouse candidates, and application of the newly developed heuristic named Balloon Search that takes account of all warehouse candidates, and runs in ( O (3n + 2n log n ) ) expected time (n is the number of nodes of the underlying graph). Our experiments on the spare parts logistics of a Japanese manufacturing company with 6000 customers and 380,000 warehouse candidates led us to conclude that the Greedy heuristic improved the total cost by 9%-11%, that the Interchange heuristic improved the total cost by an additional 0.5%—1.5%, and that Balloon Search improved it by a further 0.5%—1.5%.     

设备定位问题局部搜索算法的实验

讨论设备问题的局部搜索近似算法及其在实际计算中表现出的新性质。主要讨论局部搜索算法中初始解的产生方法,设备价值与服务价值大小对算法求解性能的影响。实验表明：约有99%以上的实例可直接利用局部搜索算法求得最优解;贪心算法产生初始解的局部搜索算法求解时间明显短于随机算法产生初始解的方法,但两者求解质量相当;设备价值和服务价值数值范围越大,局部搜索算法越容易求得最优解。     

An Approximation Algorithm for a Large-Scale Facility Location Problem

We developed a new practical optimization method that gives approximate solutions for large-scale real instances of the Uncapacitated Facility Location Problem. The optimization consists of two steps: application of the Greedy—Interchange heuristic using a small subset of warehouse candidates, and application of the newly developed heuristic named Balloon Search that takes account of all warehouse candidates, and runs in ( O (3n + 2n log n ) ) expected time (n is the number of nodes of the underlying graph). Our experiments on the spare parts logistics of a Japanese manufacturing company with 6000 customers and 380,000 warehouse candidates led us to conclude that the Greedy heuristic improved the total cost by 9%-11%, that the Interchange heuristic improved the total cost by an additional 0.5%—1.5%, and that Balloon Search improved it by a further 0.5%—1.5%.     

Strengthening the reliability fixed-charge location model using clique constraints

The Reliability Fixed-Charge Location Problem is an extension of the Simple Plant Location Problem that considers that some facilities have a probability of failure. In this paper we reformulate the original mathematical programming model of the Reliability Fixed-Charge Location Problem as a set packing problem. We study certain aspects of its polyhedral properties, identifying all the clique facets. We also discuss how to obtain facets of the Reliability Fixed-Charge Location Problem from facets of the Simple Plant Location Problem. Subsequently, we study some conditions for optimal solutions. Finally, we propose an improved compact formulation for the problem and we check its performance by means of an extensive computational study.     

Exact procedures for solving the discrete ordered median problem

The discrete ordered median problem (DOMP) integrates classical discrete location problems, such as the N-median, N-center and Uncapacitated Facility Location problems. It was introduced by Nickel (In: Fleischmann B, Lasch R, Derigs U, Domschke W, Rieder U, editors. Operations Research Proceedings 2000, Berlin: Springer, 2001. p. 71–76), who formulated it as both a nonlinear and a linear integer program. We propose an alternative integer linear programming formulation for the DOMP, discuss relationships between both integer linear programming formulations, and show how properties of optimal solutions can be used to strengthen these formulations. Moreover, we present a specific branch and bound procedure to solve the DOMP more efficiently. We test the integer linear programming formulations and this branch and bound method computationally on randomly generated test problems.     

基于移动代理的应用层主动网络服务部署问题研究

文章将服务部署思想引入基于移动代理的应用层主动网络(MALAN)框架中,从主动节点中选取一部分建立服务,为用户会话提供服务,每个服务将提供给一组用户会话。文章根据MALAN的特点建立服务部署的数学模型,并用混合遗传算法进行求解,在进行了大量模拟试验的基础上,对系统中的关键参数进行了分析。文章使用的建模方法同样适用于主动Overlay网络服务部署、网络代理、镜像放置等问题。     

RAMP algorithms for the capacitated facility location problem

Annals of Mathematics and Artificial Intelligence - In this paper, we address the Capacitated Facility Location Problem (CFLP) in which the assignment of facilities to customers must ensure enough...     

A dual RAMP algorithm for single source capacitated facility location problems

Annals of Mathematics and Artificial Intelligence - In this paper, we address the Single Source Capacitated Facility Location Problem (SSCFLP) which considers a set of possible locations for...