制造单元布局问题的双目标模型与算法研究

单元制造系统的布局对于提高系统的效率起着十分重要的作用。以最小化物料周转量和设施面积为目标,建立了一个单元制造系统布局的双目标优化模型,在该模型中不同制造单元的布局、单元内部不同设施的位置与方向这几个问题可以同时进行优化。基于模拟退火邻域解的变尺度生成机制和双目标抽样准则设计了模型的求解算法。算例表明本文算法所得Pareto解集优于经典的NSGA-Ⅱ算法。     

带性能约束的矩形图元布局优化模型及不干涉性算法

本文讨论了以航天卫星仪器舱布局优化设计为背景的、带性能约束的矩形图元布局优化模型及不干涉性判别算法,主要讨论了模型的性质,并将这一模型转化为带反凸约束的凸规划问题。应用文献(4)给出的最优性条件及定界锥分拆算法,可求得带性能约束的矩形图元布局优化问题的全局最优解。     

卫星舱三维布局优化模型及判断不干涉性算法

本以人造卫星仪器舱布局问题为背景。建立了在抛物圆柱体空间中带性能约束的长方体群的布局优化模型。分析模型中不干涉性约束的性质，利用凸集分离定理给出了等价的显式表达式，并构造了判断不干涉性的算法。     

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

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

基于二叉树的遗传算法求解设施平面布局优化

针对设施布局优化问题,使用二叉树的顺序遍历结构,结合设施顺序、相互关系及位置等因素形成新的染色体编码形式.以设施相邻性和随机原则相结合产生初始解,针对染色体的三段编码分别进行遗传操作,运用动态原则和反馈机制改进算法的惩罚函数.通过典型案例验算表明,本论文提出的算法在寻优效果和执行效率上有一定地改善.     

不确定环境下服务资源配置优化

在服务资源配置过程中,按维修状态将服务对象分成三类:完全维修、部分维修及最小维修.由于维修服务的特性,服务成本与服务时间均是一个模糊数,并且维修对象在服务时所处的维修状态也具有一定的不确定性.针对这类情况下的服务资源配置问题,提出了同时考虑模糊服务成本和模糊服务时间及不确定维修状态的最小化服务成本为优化指标的服务资源配置模型.在模型的求解过程中采用多粒子群算法,通过仿真计算表明了该方法的可行性和有效性.     

带性能约束布局问题的全局优化算法

以人造卫星仪器舱布局为例,应用图论,群对集合的作用,轨道与等价关系等刻划各种布局方案的同构,等价类等内在性质,从而首次给出带有性能约束二维布局问题的一个全局优化算法。     

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

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

油田注水系统拓扑布局优化的混合遗传算法

以投资最小为目标函数,建立了注水系统拓扑布局优化数学模型.根据模型特点,将优化问题分为两层,分别采用遗传算法和非线性优化方法进行求解.并对遗传算法的操作过程进行了改进,调整了适应函数,改进了交叉和变异操作,结合了模拟退火算法,在操作过程中使约束条件得到满足,减少了不可行解的产生,使遗传算法的优化性能得到了提高.优化算例说明了该方法的有效性.     

卫星舱布局的半无限优化模型及最优性条件

本文以人造卫星仪器舱布局问题为背景，建立了一个半无限优化模型。应用图论、群对集合的作用、轨道等，把该问题分解为有限多个子问题，在每个子问题中克服了关于优化变量的时断时续性质。针对每个子问题分析了模型中各函数的性质，并构造了一个局部等价于子问题的极大极小问题。利用这个极大极小问题及子问题中各函数的方向可微性给出了子问题的一阶最优性条件。     

竞争环境下截流问题的选址-价格模型

研究了竞争环境下考虑产品定价的截流设施选址问题。连锁企业在市场上新建设施时,市场上已有属于竞争对手的设施存在,在连锁企业新建设施位置确定之后,两个企业关于产品定价进行双寡头完全信息非合作博弈。定义了效用函数,引入Huff模型,以企业利润最大为目标,建立双层规划模型,证明了模型纳什均衡价格的存在性,并构造启发式算法对模型进行求解。算例分析表明,该算法求解结果较为理想,可用于大中型网络的规划选址问题。     

井位不确定环境下的油田仓库选址问题

油田工作中,合理的仓库选址决策不仅能节约物流成本,而且能提高油田作业效率。现有研究通常基于当前的油井位置(简称井位),没有考虑未来井位变化对仓库选址的影响。同时井位受到地下储层条件及油气公司远景规划等因素影响,未来的井位具有很强的不确定性。此外,仓库选址决策属中长期决策,将长期影响油田的物流费用、管理工作甚至开发工作,而且油田生产要求仓库能持续供应物资,所以油田仓库选址应考虑井位的不确定性和仓库服务中断等因素。本文首先根据油田井位分布和钻井规划采用随机模拟方法模拟未来井位,建立并求解考虑设施中断的离散选址模型。然后以鄂南油区物资仓库选址问题为例,模拟井位并求解仓库选址问题,从8个候选点中选出3个建库/租库。最后,分析井位和需求量变化对仓库选址结果的影响。井位不确定环境下油田物资仓库选址问题的研究,不仅对油田物流系统管理的研究具有一定的理论意义,也对油田的物流决策有重要的现实意义。     

两阶段选址优化问题研究

本文主要考虑如下实际问题:假设选址决策者需要建设p个设施,但是由于资金等等的影响,实际建设时会被要求先建设q个设施,其次再建设p-q个设施(设p>q),同时要求,在建设p-q个设施的时候,已经建设好的q个设施不被删除。本文建立了一个两阶段优化问题,问题的输出是两个待修建的设施的集合Fq,Fp,|Fp|=p,|Fq|=q,且Fq是Fp的子集,问题的目标是最小化这两个设施集合的费用同对应的最优费用的比值的最大值。本文给出一个近似比为9的近似算法,并对一些特殊的情况进行了讨论。所得结论对实际的选址决策具有理论意义,同时也完善已有相关研究结果。     

Bi-Objective Median Subtree Location Problems

A number of network design problems can be built on the following premise: given an undirected tree network, T, with node set, V, identify a single subtree, t, containing nodes, v, so that the subtree is located optimally with respect to the remaining, subset of unconnected nodes {V–v}. Distances between unconnected nodes and nodes in the subtree t can be defined on paths that are restricted to lie in the larger tree T (the restricted case), or can be defined on paths in an auxiliary complete graph G (the unrestricted case). The unrestricted case represents a class of problems that is not explicitly recognized in the literature, which is of intermediate complexity relative to the widely studied restricted case, and the general problem in which the underlying graph is general. This paper presents the Median Subtree Location Problem (MSLP), formulated as a bicriterion problem that trades off the cost of a subtree, t, against the population-weighted travel distance from the unconnected nodes to nodes on the subtree where both objectives are to be minimized. Integer programs were formulated for the travel restricted and travel unrestricted cases and were tested using linear programming and branch and bound to resolve fractions. Tradeoff curves between cost and travel burden were developed for sample networks.     

Annealing Algorithms for Multisource Absolute Location Problems on Graph

A methodology is presented for applying annealing techniques tomultisource absolute location problems on graph. Two kinds ofobjective functions are considered: barycenters and centers. Aclass of new algorithms is described: its development startsfrom the iterative cluster-and-locate algorithm and reliesupon the relaxation of the integrality constraints onallocation variables. Experimental results are reported.     

多行程车辆路径问题和配送中心定位问题的研究

为了同时解决多行程车辆路径问题和配送中心的定位问题,首先开发了一个以最小化总成本为目标的数学模型,其中总成本包括运输成本和车辆启动成本.然后设计了一个启发式算法解决这个问题,包括三个阶段:第一阶段是找到初始定位并进行路线安排,第二阶段采用模拟退火(SA)的逻辑和交换算法来获得更好的路线,最后阶段是改善由模拟退火算法中当前温度控制的位置.通过标准样例进行的实验结果表明,该算法可以更好地获得一个配送中心定位和有效的相关路线安排.最后,数值实验指出:1)选择不同类型行程的配送方式取决于每辆车的启动成本和单位距离的运输成本;2)使用大容量车辆可以更好地减少运输距离.3)增加服务时间可以有效地减少所需车辆的数量,这三个结果对于多行程车辆路径问题和配送中心的定位问题的管理决策都具有一定的实用价值.     

范数下无容量限制设施选址逆问题的求解方法

一个优化问题的逆问题是这样一类问题,在给定该优化问题的一个可行解时,通过最小化目标函数中参数的改变量(在某个范数下)使得该可行解成为改变参数后的该优化问题的最优解。对于本是NP-难问题的无容量限制设施选址问题,证明了其逆问题仍是NP-难的。研究了使用经典的行生成算法对无容量限制设施选址的逆问题进行计算,并给出了求得逆问题上下界的启发式方法。两种方法分别基于对子问题的线性松弛求解给出上界和利用邻域搜索以及设置迭代循环次数的方式给出下界。数值结果表明线性松弛法得到的上界与最优值差距较小,但求解效率提升不大;而启发式方法得到的下界与最优值差距极小,极大地提高了求解该逆问题的效率。     

最小最大后悔准则下新增设施选址策略研究

基于新增设施选址问题,考虑网络节点权重不确定性,以设施中最大负荷量最小为目标,提出最小最大后悔准则下的新增设施选址问题。在网络节点权重确定时,通过证明将网络图中无穷多个备选点离散为有限个设施候选点,设计了时间复杂度为O(mn²)的多项式算法;在节点权重为区间值时,通过分析最大后悔值对应的最坏情境权重结构,进而确定最大后悔值最小的选址,提出时间复杂度为O(2ⁿm²n³)的求解算法;最后给出数值算例。     

Approximating connected facility location with buy-at-bulk edge costs via random sampling

In the connected facility location problem with buy-at-bulk edge costs we are given a set of clients with positive demands and a set of potential facilities with opening costs in an undirected graph with edge lengths obeying the triangle inequality. Moreover, we are given a set of access cable types, each with a cost per unit length and a capacity such that the cost per capacity decreases from small to large cables, and a core cable type of infinite capacity. The task is to open some facilities and to connect them by a Steiner tree using core cables, and to build a forest network using access cables such that the edge capacities suffice to simultaneously route all client demands unsplit to the open facilities. The objective is to minimize the total cost of opening facilities, building the core Steiner tree, and installing the access cables. In this paper, we devise a constant-factor approximation algorithm for this problem based on a random sampling technique.     

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

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