Dual hybrid frameworks combining graph convolutional network with decoding for covering location problem

Abstract

The Covering Location Problem (CLP) is widely used for the efficient facility distribution. However, existing algorithms for this problem suffer from long computation times or suboptimal solutions. To address this, we propose two methods based on graph convolutional networks (GCN) to solve two types of covering location problems: the location set covering problem and the maximum covering location problem. The first method, GCN-Greedy, is a supervised algorithm that synergized with the Greedy algorithm as decoder. It designs a specialized loss function to train the model, tailored to the characteristics of the two covering location problems. The second method, reinforcement learning based on GCN with auto-regressive decoder (GCN-AR-RL), represents a reinforcement learning framework that integrates a GCN encoder with an auto-regressive decoder. The experimental results of these models demonstrate the remarkable accuracy and performance advantages. Additionally, we apply these two models to the realistic dataset and achieve good performance.

Keywords: Computer science; applied sciences; natural sciences.