The facility location problems (FLPs) are a typical class of NP-hard combinatorial optimization problems, which are widely seen in the supply chain and logistics. Many mathematical and heuristic algorithms have been developed for optimizing the FLP. In addition to the transportation cost, there are usually multiple conflicting objectives in realistic applications. It is therefore desirable to design algorithms that find a set of Pareto solutions efficiently without enormous search cost. In this paper, we consider the multi-objective facility location problem (MO-FLP) that simultaneously minimizes the overall cost and maximizes the system reliability. We develop a learning-based approach to predicting the distribution probability of the entire Pareto set for a given problem. To this end, the MO-FLP is modeled as a bipartite graph optimization problem and two graph neural networks are constructed to learn the implicit graph representation on nodes and edges. The network outputs are then converted into the probability distribution of the Pareto set, from which a set of non-dominated solutions can be sampled non-autoregressively. Experimental results on MO-FLP instances of different scales show that the proposed approach achieves a comparable performance to a widely used multi-objective evolutionary algorithm in terms of the solution quality while significantly reducing the computational cost for search.
翻译:设施定位问题(FLPs)是典型的NP硬组合优化问题,在供应链和物流中广为人知。许多数学和超光速算法是为优化FLP而开发的。除了运输成本外,在现实应用中通常存在多重相互矛盾的目标。因此,最好设计一种算法,在不花费巨大搜索成本的情况下,找到一套高效的Pareto解决方案。在本文中,我们认为多目标设施定位问题(MO-FLP)同时最大限度地降低总体成本和系统可靠性。我们开发了一种基于学习的办法来预测为特定问题设定的整个Pareto的分布概率。为此,MO-FLP是模拟成双面图形优化问题的模型,并建立了两个图形神经网络,以学习节点和边缘的隐性图形代表。然后将网络产出转换成Pareto集的概率分布,从中可以抽样展示一组非主控式解决方案,不易反向反向地展示。MO-FLP中为某个特定问题设定的实验性结果。为此,不同规模的M-FLP实例的实验性结果将大大降低了采用可比较的搜索方法。