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

Area of Science:

• Operations Research
• Computer Science
• Artificial Intelligence

Background:

• The Covering Location Problem (CLP) is crucial for efficient facility distribution.
• Existing CLP algorithms often face challenges with long computation times and suboptimal solutions.

Purpose of the Study:

• To develop advanced methods for solving the location set covering problem and the maximum covering location problem.
• To leverage graph convolutional networks (GCN) for enhanced CLP solutions.

Main Methods:

• Proposing GCN-Greedy, a supervised algorithm using a GCN encoder and a Greedy decoder with a specialized loss function.
• Introducing GCN-AR-RL, a reinforcement learning framework combining a GCN encoder and an auto-regressive decoder.
• Training and evaluating models on covering location problem datasets.

Main Results:

• Both GCN-Greedy and GCN-AR-RL demonstrated significant accuracy and performance advantages.
• The models achieved good performance when applied to realistic datasets.
• The proposed GCN-based methods address limitations of existing CLP algorithms.

Conclusions:

• Graph convolutional networks offer a powerful approach to solving complex covering location problems.
• The developed GCN-Greedy and GCN-AR-RL methods provide efficient and accurate solutions for facility distribution.
• These findings have practical implications for optimizing facility placement in real-world scenarios.