Neural Embedded Optimization for Integrated Location and Routing Problems

We present a novel framework that combines supervised machine learning with integer programming to solve the Capacitated Location-Routing Problem (CLRP). The CLRP is strongly NP-hard and includes two classical combinatorial optimization problems: discrete facility location and vehicle routing. We develop a new solution method that begins by learning a permutation-invariant and sparse neural network that approximates the optimal vehicle routing cost over the sub-graph induced by assigning a subset of customers to any candidate facility. The trained neural network is used as a surrogate within a mixed-integer program (MIP), reformulated using additional variables and constraints, and then solved with an off-the-shelf solver. Computational experiments on large-scale test instances containing up to 200 customers show that our method identifies near-optimal solutions significantly faster than existing problem-specific heuristics. These findings suggest that our neural-embedded framework could be a viable approach for addressing general integrated planning and scheduling problems.