Neural Embedded Mixed-Integer Optimization for Location-Routing Problems

Research focus

The capacitated location-routing problem asks three questions at once: which depots to open, which customers each depot serves, and which vehicle routes deliver to them. Exact methods give guarantees but do not scale beyond a few hundred customers or about ten candidate facilities. Heuristics reach larger instances without those guarantees, and when a heuristic governs the location and allocation decisions, its search operators have to be redesigned whenever a new application-specific constraint appears at that level.

Approach

NEO-LRP splits the problem into two levels. A neural network is trained once to predict the cost of a single-depot vehicle routing problem, using independently generated routing instances that are disjoint from the location-routing test sets. The prediction does not depend on the order of the customers assigned to a depot, which the architecture respects by design.

The trained model is then embedded in a mixed-integer program with binary variables and linear constraints. A standard solver decides which depots to open and how to assign customers, using the network's estimate in place of explicit routes, so custom constraints can be added as ordinary constraints. The program itself does not produce vehicle routes: a routing solver builds them afterwards for each open depot.

Results

Across four benchmark sets, the authors report solution quality competitive with best-known solutions and computational speedups of 2× to 120× over state-of-the-art heuristics. After a one-time training cost of about six hours, solve times range from under a second to under five minutes per instance. On the largest instances, with 600 customers and 30 depots, they report a 1% median gap, compared with more than four hours for leading heuristics.

Specialized heuristics remain closer to best-known solutions on some sets. On the Prins benchmark, for example, the reported median gap is 1.62% for NEO-LRP and 0.11% for the strongest baseline, with median solution times of 2.2 seconds and 11.3 seconds.

Publication

NeurIPS 2025 DiffCoALG workshop

Kaleem, W., Lee, D., Kwon, C., and Subramanyam, A.