基于元启发式算法的设施选址问题研究

SOLVING FACILITY LOCATION PROBLEMS BASED ON META-HEURISTIC ALGORITHMS

张涵

11849181

硕士

计算机技术领域工程

姚新

2020-05-30

2020-07-20

哈尔滨工业大学

深圳

设施选址问题（Facility Location Problem, FLP），是物流、供应链等行业的基础决策，也是一项至关重要的决策，选址决策质量的好坏将直接影响建造成本、运输成本、存储成本以及货物配送效率乃至总体收益，更会间接影响整个物流链或供应链的其他环节，因此，正确的选址决策对物流业等行业的上下游产业乃至对经济和社会均有着重要的意义。该问题是运筹学的重要研究领域，同时是一类NP-Hard问题，在具有学术价值的同时具有很好的现实应用价值，因而吸引了众多研究人员的关注并积累了众多的研究成果。如今，设施选址问题作为一个庞大的研究领域，已经发展出了众多的子领域，并有着丰硕的研究成果。本文的研究内容是使用元启发式算法解决设施选址问题。本文将研究焦点聚焦在可靠的设施选址问题（Reliable Facility Location Problem）上，并在可靠的设施选址问题的研究基础上，进一步扩展到鲁棒可靠的设施选址问题（Robust and Reliable Facility Location Problems）的研究上。针对所研究的问题，我们在进行了广泛的文献调研的基础上，构建了相应的数学模型，然后在一种经典的元启法式算法——演化算法框架的基础上结合局部搜索方法进行算法设计和改进，提出了结合弱局部搜索的演化算法（Evolutionary Algorithm with Weak Local Search，EAWLS）、结合强局部搜索的演化算法（Evolutionary Algorithm with Strong Local Search，EASLS）以及结合有记忆的局部搜索的演化算法（Evolutionary Algorithm with Memorable Local Search, EAMLS）对模型进行求解。对于两种研究问题（可靠的设施选址问题和鲁棒可靠的设施选址问题），我们均构造了两种不同的模型进行比较，并且对每一个模型都设计了详尽的实验，通过在不同规模的问题实例上与拉格朗日松弛算法和世界上最先进的优化求解器之一——IBM的CPLEX进行比较，以验证我们的算法的有效性。除此之外，我们基于Django框架开发了一个解决设施选址问题的网页Demo，实现了一些基本的功能。在网页上有着对设施选址问题、我们所构建的数学模型以及EAMLS算法的基本介绍，并且可以接收用户输入的参数，生成相应的问题实例，调用EAMLS算法进行求解并向用户展示所做出的选址决策以及选址示意图和算法收敛曲线图。我们的研究的创新性体现在以下几个方面。（1）我们构造了可靠的设施选址问题的新模型，在模型中采用了新的设施分配方法；（2）对可靠的设施选址问题，目前相似的研究工作所尝试解决的问题的最大规模为150个节点，我们所求解的大规模问题的规模远大于已有的研究工作，达到600个节点；（3）我们采用场景规划方法将可靠的设施选址问题的模型拓展为鲁棒可靠的设施选址问题的模型，丰富了该问题下的研究；（4）本文提出了一种新的混合演化算法，可以有效求解小中大规模的设施选址问题；（5）本文提出了种群多样性衡量指标0-HDR和收敛性衡量指标l3-value，用以帮助用户观察演化过程并改进算法；（6）本文开发了一个设施选址问题的网页应用Demo，并实现了一些基本功能。

The facility location problem (FLP) is the basic decision of the logistics industry and the supply chain industry. It is also a crucial decision. The quality of the location decision will not only directly affect the construction cost, transportation cost, storage cost, the efficiency of cargo distribution, and the overall benefits, but also indirectly affect the entire logistics chain or other links in the supply chain. Therefore, the correct location decision has important significance for the upstream and downstream industries of the logistics industry and even the economy and society. The facility location problem is an important research area of operations research. Because of its academic value and application value, this problem has attracted the attention of many researchers and published many research results. Today, as a huge research area, facility location has developed many subfields and had fruitful research results. The research content of the topic is to design metaheuristic algorithms to solve the facility location problem. This dissertation is focused on the reliable facility location problem, and based on the research of reliable facility location problem, it is further extended to the study of the robust and reliable facility location problem. Based on the extensive literature review, we constructed a corresponding appropriate mathematical model for the problem. Combining the local search method with the framework of a kind of classic metaheuristic algorithms, evolutionary algorithms, we proposed some metaheuristic algorithms: Evolutionary Algorithms with Weak Local Search (EAWLS), Evolutionary Algorithms with Strong Local Search (EASLS), and Evolutionary Algorithm with Memorable Local Search (EAMLS) to solve the model. For the two research problems (reliable facility location problem and robust and reliable facility location problem), we have constructed two different models for comparison and designed detailed experiments for each model. We compared our algorithm with the Lagrangian relaxation algorithm and one of the world's most advanced optimization solvers, IBM CPLEX, on different scale problem instances to verify the effectiveness of our algorithm. In addition, we developed a web demo based on the Django framework to solve the facility location problem instances, and implemented some basic functions. On the webpage, there is a basic introduction about the facility location problem, the mathematical models we built, and the EAMLS algorithm, and it can receive parameters entered by the user, generate a corresponding problem instance, call the EAMLS algorithm to solve the instance and show the location decision, location diagram and algorithm convergence curve diagram. The innovation of our research is reflected in the following aspects. (1) We construct a new reliable facility location problem model which adopts a new allocation method; (2) The scale of large-scale problems we solve (600-node) is larger than other literature (maximum 150-node); (3) A robust and reliable facility location problem model is proposed based on the above-mentioned RFLP model by scenarios planning method; (4) A novel hybrid evolutionary algorithm is proposed which performs good on small, mid, and large-scale problems; (5) A population diversity metric 0-HDR and a convergence metric l3-value are proposed to help users observe the evolutionary process, adapt parameters, and analyze and improve the algorithm; (6) A simple web application demo is developed for facility location problem, which has some foundational functions.

可靠的设施选址问题 鲁棒可靠的设施选址问题 元启发式算法 混合演化算法

reliable facility location problem robust and reliable facility location problem meta-heuristic algorithms hybrid evolutionary algorithms

中文

联合培养

南方科技大学

张涵. 基于元启发式算法的设施选址问题研究[D]. 深圳. 哈尔滨工业大学,2020.