考虑设施失效的选址问题、模型与算法

发布时间：2018-09-13 21:33

【摘要】：设施选址问题是供应链网络、后勤网络和服务网络设计的基础性问题,合理地确定设施的位置有利于高效、经济地为客户提供产品、信息或服务。在现实生活中,设施因为自然或人为原因,如地震、恐怖袭击等,而无法正常工作的情况常有发生,这种情况被称为设施失效或设施中断(facility disruption)。设施失效的危害很大,它导致供应中断、服务中断、显著提高设施系统的服务成本、延迟客户需求满足、导致客户流失,甚至可能对供应链或服务网络造成全局性和灾难性的影响。设施选址规划是战略决策,设施网络建立后难以在短时间内重建和调整。当设施失效发生后,补救措施往往很有限,且恢复时间较长。因此,决策者在建立设施网络之初就需要考虑到设施失效的可能性,采用各种手段提高设施系统可靠性。此外,设施选址问题是NP难问题。随着整数规划理论的发展,很多大规模商业优化软件可以比较快速地求解大规模的经典选址问题,但对于考虑设施失效可能性的模型,这些商业软件仍然只能有效求解小到中等规模的问题,随着问题规模增加其求解效率显著下降,甚至无法求解。因此,需要针对具体的模型设计特定的算法,使之能又好又快地求解大规模问题。针对这些问题,论文首先研究了一个考虑设施失效和保护的选址问题,该问题通过对设施进行保护和为需求节点分配备份设施来提高设施网络的可靠性。我们指出针对该问题的已有模型只适合处理所有设施失效概率都相同的情况,进而提出了一种简洁的、可以处理不同设施具有不同失效概率的扩展模型,并基于扩展模型分析了问题最优解的结构性质。由于当前最好的数学规划软件CPLEX不能直接求解该模型的大规模实例。因此,我们提出了一种结合拉格朗日松弛和局部搜索启发式求解算法,通过分析原问题的结构特点,把原问题松弛并分解为多个独立子问题分别求解。另一方面,采用了基于贪婪策略的局部搜索启发式方法对可行解进行改进。通过对标准数据集的计算实验证明了所提算法收敛速度快,求解效率和求解质量都非常高。考虑到在现实中加固资金和资源往往是有限的,并且决策者对设施失效风险的态度也会影响对加固的投入。论文继而提出了考虑加固预算约束的选址和加固问题。给出了预算约束下的选址和加固模型,并给出了一个多阶段加固模型,指出两者的联系与区别。提出了三个结合拉格朗日松弛和局部搜索的求解算法。三个算法松弛了不同的约束,采用不同的方法求解松弛问题和构造可行解。通过大量计算实验对三个算法的求解效率和求解质量进行了对比,分析了三个算法各自的特点,证明了所提算法在求解中等到大规模问题时相对CPLEX有非常明显的优势。最后,论文提出了考虑设施能力受限和单源分配约束的可靠性选址问题。该问题考虑到现实中设施能力往往有限,并且在正常情况下客户一般由某特定设施单源服务的情况,通过合理地决定设施的数目和位置,将系统的冗余能力用于需求备份。提出了一个期望值模型和一个两阶段随机规划模型,讨论了两个模型的异同。分析了模型的结构性质并提出了一个拉格朗日松弛求解算法。通过对松弛问题结构的分析,对变量进行了约减,降低松弛问题的求解难度,并提出了构造可行解的启发式方法。通过对上百组标准数据集的计算,证明了所提算法对各种规模的算例都可以求得高质量的解。对上述三个模型,都基于湖南省的一个具体选址案例进行了深入分析。通过对模型各重要参数的灵敏度分析深入剖析了模型的性质,揭示了一些符合直觉和反直觉的规律,并给出了合理的分析与解释,这些为决策者科学决策提供了管理上的启示。
[Abstract]:Facility location is a fundamental problem in the design of supply chain network, logistics network and service network. Reasonable location of facilities is conducive to efficient and economical provision of products, information or services to customers. This is called facility disruption. Facility failure is very harmful. It can lead to supply disruption, service disruption, significantly increase the service cost of the facility system, delay customer demand satisfaction, lead to customer churn, and may even have a global and catastrophic impact on the supply chain or service network. Facility location planning is a strategic decision, and it is difficult to reconstruct and adjust the facility network in a short time after its establishment. When the facility failure occurs, the remedial measures are often limited and the recovery time is long. Therefore, decision makers need to consider the possibility of facility failure at the beginning of the establishment of the facility network, and adopt various means to improve the reliability of the facility system. In addition, facility location problem is NP-hard. With the development of integer programming theory, many large-scale commercial optimization software can solve large-scale classical location problem more quickly, but for the model considering the possibility of facility failure, these commercial software can only effectively solve small to medium-scale problems, with the problem planning. In order to solve large-scale problems quickly and efficiently, we need to design specific algorithms for specific models. To solve these problems, we first study a site selection problem considering facilities failure and protection, which protects facilities and serves as demand section. We point out that the existing models for this problem are only suitable for all facilities with the same failure probability, and then we propose a simple extended model which can handle different facilities with different failure probability. Because the best mathematical programming software CPLEX can not directly solve large-scale examples of the model, we propose a heuristic algorithm combining Lagrange relaxation and local search. By analyzing the structural characteristics of the original problem, the original problem is relaxed and decomposed into several independent sub-problems to solve respectively. A greedy strategy based local search heuristic method is used to improve the feasible solution. Experiments on standard data sets show that the proposed algorithm has fast convergence speed, high efficiency and high quality. This paper then proposes a location and reinforcement problem with budget constraints. A multi-stage reinforcement model is presented, and the relationship and difference between the two models are pointed out. The three algorithms relax different constraints and use different methods to solve relaxation problems and construct feasible solutions. The efficiency and quality of the three algorithms are compared through a large number of computational experiments. The characteristics of the three algorithms are analyzed. It is proved that the proposed algorithm is very good compared with CPLEX in solving medium to large scale problems. Finally, the paper proposes a reliability location problem considering the limitation of facility capacity and single-source allocation constraints. Considering the fact that facility capacity is often limited in reality and that customers are usually served by a single-source facility under normal circumstances, the system is redundant by reasonably determining the number and location of facilities. An expected value model and a two-stage stochastic programming model are proposed. The similarities and differences between the two models are discussed. The structural properties of the model are analyzed and a Lagrange relaxation algorithm is proposed. By calculating hundreds of sets of standard data sets, it is proved that the proposed algorithm can obtain high-quality solutions for all kinds of numerical examples. The above three models are all based on a specific location case in Hunan Province. Degree analysis deeply analyzes the nature of the model, reveals some intuitive and counter-intuitive laws, and gives reasonable analysis and explanation, which provides management inspiration for decision makers in scientific decision-making.
【学位授予单位】：国防科学技术大学
【学位级别】：博士
【学位授予年份】：2016
【分类号】：TP301.6

【相似文献】