区间图上可带负权的2-中位选址问题（英文）

Abstract本文研究了区间图上可带负权的2-中位选址问题.根据目标函数的不同,可带负权的p-中位选址问题（p≥2）可分为两类：即MWD和WMD模型;前者是所有顶点与服务该顶点的设施之间的最小权重距离之和,后者是所有顶点与相应设施之间的权重最小距离之和.在本篇论文中,我们讨论了区间图上可带负权2-中位选址问题的两类模型,并分别设计时间复杂度为O（n~2）的多项式时间算法.     

带时间窗偏好的同时配集货且需求可拆分车辆路径问题

针对带时间窗偏好的同时配集货且需求可拆分车辆路径问题,最小化派遣成本、理货成本、时间窗惩罚成本以及油耗成本之和,建立数学模型。设计混合遗传变邻域搜索算法求解问题,在算法中引入时空距离的理念,首先用最近邻插入法和Logistic映射方程生成初始种群;然后利用变邻域搜索算法的深度搜索能力优化算法;提出自适应搜索策略,平衡种群进化所需的广度和深度;设计拆分准则,为各客户设置不同的拆分服务量;提出确定车辆最优出发时间的时差推移法,减少车辆在客户处的等待时间;最后通过多组算例验证本文模型和算法的有效性。     

一类带单源约束的选址运输问题算法研究

带单源约束的选址运输问题是在经典的选址运输问题基础上考虑每个顾客需求的产品仅由一家工厂供应的情况。所建立的模型是整数规划，是NP难的。本文先考虑了开办费用为零的带单源约束的选址运输问题，即带单源约束的运输问题。松弛其中一种变量约束，借鉴求解运输问题的表上作业法，给出了一种修正的表上作业法，然后将算法推广。最后给出了将算法应用在Excel随机生成的测试问题上所得到的结果，与LINDO求得的最优解相比，差距很小。由此得出结论：对规模较小的带单源约束的选址运输问题，本文提出的算法是简便且行之有效的。     

Heisenberg群上带不确定权的p-次Laplacian特征值问题(英文)

本文讨论Heisenberg群上带不确定权的p-次Laplacian特征值问题解的存在性,并且证明相应的非负特征函数的第一特征值是单重的,孤立的和唯一的.     

主通道位置不固定的设施布局问题多目标优化模型及算法

以物流中心设施布局问题为对象,提出了考虑出入口及主通道位置不固定情况下的设施布局问题的多目标优化模型并设计了其改进的遗传算法。首先,以物料搬运成本最小、活动关系密切度最大和面积利用率最大为目标,构建了考虑出入口位置不固定条件下的具有I型主通道的设施布局多目标优化数学模型。然后,设计了一种改进的遗传算法,包括:改进的编码、解码方法,追加了解码修正操作,基于惩罚函数策略的适应度函数等。实例测试表明,本算法的执行效率高而且结果稳定,优化效果好,布局结果紧凑适用。     

一种改进的禁忌搜索算法及其在选址问题中的应用

本文研究了选址问题中无容量限制的p-中值问题,在Rolland等人提出的有效禁忌搜索算法基础上,提出了一种以目标函数变化量作为评价函数的改进禁忌搜索算法,并进行了理论分析,然后将其与有效禁忌搜索算法作了性能比较.通过比较三个公共测试数据集的计算结果,验证了本文提出的禁忌搜索算法的可行性和有效性.     

A modified variable neighborhood search for the discrete ordered median problem

This paper presents a modified Variable Neighborhood Search (VNS) heuristic algorithm for solving the Discrete Ordered Median Problem (DOMP). This heuristic is based on new neighborhoods’ structures that allow an efficient encoding of the solutions of the DOMP avoiding sorting in the evaluation of the objective function at each considered solution. The algorithm is based on a data structure, computed in preprocessing, that organizes the minimal necessary information to update and evaluate solutions in linear time without sorting. In order to investigate the performance, the new algorithm is compared with other heuristic algorithms previously available in the literature for solving DOMP. We report on some computational experiments based on the well-known N-median instances of the ORLIB with up to 900 nodes. The obtained results are comparable or superior to existing algorithms in the literature, both in running times and number of best solutions found.     

An approximation algorithm for the dynamic facility location problem with submodular penalties

In this paper, we study the dynamic facility location problem with submodular penalties （DFLPSP）. We present a combinatorial primal-dual 3-approximation algorithm for the DFLPSP.     

Fault-tolerant concave facility location problem with uniform requirements

In this paper, we consider the fault-tolerant concave facility location problem (FTCFL) with uni- form requirements. By investigating the structure of the FTCFL, we obtain a modified dual-fitting bifactor approximation algorithm. Combining the scaling and greedy argumentation technique, the approximation fac- tor is proved to be 1.52.     

平方度量动态设施选址问题的近似算法

研究了单阶段度量设施选址问题的推广问题平方度量动态设施选址问题. 研究中首先利用原始对偶技巧得到 9-近似算法, 然后利用贪婪增广技巧将近似比改进到2.606, 最后讨论了该问题的相应变形问题.     

遗传规划的改进算法

通过改变遗传规划算法中初始群体的生成方法,改变变异策略和修正适应度函数,对遗传规划算法进行了改进,并通过符号回归数值实验对改进后算法的性能进行了测试,且将改进后的算法与改进前以及其它改进算法进行了比较,数值实验结果表明,改进后的算法有效地提高了遗传规划的效率。     

重大突发事件应急设施多重覆盖选址模型及算法

为了解决应对重大突发事件过程中应急需求的多点同时需求和多次需求问题,本文研究了应对重大突发事件的应急服务设施布局中的覆盖问题:针对重大突发事件应急响应的特点,引入最大临界距离和最小临界距离的概念,在阶梯型覆盖质量水平的基础上,建立了多重数量和质量覆盖模型。模型的优化目标是满足需求点的多次覆盖需求和多需求点同时需求的要求条件下,覆盖的人口期望最大,并用改进的遗传算法进行求解;最后给出的算例证明了模型和算法的有效性,从而应急设施的多重覆盖选址模型能够为有效应对重大突发事件的应急设施选址决策提供参考依据。     

关于可靠性设施布局问题的近似算法

设施布局问题的研究始于20世纪60年代,主要研究选择修建设施的位置和数量,以及与需要得到服务的城市之间的分配关系,使得设施的修建费用和设施与城市之间的连接费用之和达到最小.现实生活中, 受自然灾害、工人罢工、恐怖袭击等因素的影响,修建的设施可能会出现故障, 故连接到它的城市无法得到供应,这就直接影响到了整个系统的可靠性.针对如何以相对较小的代价换取设施布局可靠性的提升,研究人员提出了可靠性设施布局问题.参考经典设施布局问题的贪婪算法、原始对偶算法和容错性问题中分阶段分层次处理的思想,设计了可靠性设施布局问题的一个组合算法.该算法不仅在理论上具有很好的常数近似度,而且还具有运算复杂性低的优点.这对于之前的可靠性设施布局问题只有数值实验算法, 是一个很大的进步.     

A primal-dual approximation algorithm for stochastic facility location problem with service installation costs

We consider the stochastic version of the facility location problem with service installation costs. Using the primal-dual technique, we obtain a 7-approximation algorithm.