Graph Neural Networks for Combinatorial Optimization problems

The proposed work investigates the application of deep learning tools, specifically Graph Neural Networks (GNNs), to combinatorial optimization problems within the context of the Stellantis company. The work is divided into three main sections: an in-depth study of combinatorial optimization and GNN architectures, a review of how GNNs can solve such problems, and the implementation of a GNN model on a toy problem inspired by a business scenario of the company. The problem involves organizing orders into loading lists for delivery trucks, optimizing the overall load, minimizing stops, and reducing travel distance, while adhering to specific constraints. This makes the problem a combinatorial optimization problem, which is a class of problems known to be NP-Hard, making exact algorithms that guarantee optimal solutions computationally infeasible at a large scale. The problem naturally induces a graph structure of the data, the proposed solution involves developing a GNN-based heuristic to identify optimal load assignment given a problem instance, which is trained in a supervised way on a dataset generated by simulating various load assignments. Then, given a list of orders, the model can be used iteratively on the orders not assigned by the previous iteration to create the number of loading lists needed to solve the whole business problem. The results demonstrate the model’s effectiveness in learning heuristics for the problem, though further refinement and alternative approaches like reinforcement learning may enhance performance.