Neural Embedded Mixed-Integer Optimization for Location-Routing Problems
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866917284531929088 |
|---|---|
| author | Kaleem, Waquar Lee, Doyoung Kwon, Changhyun Subramanyam, Anirudh |
| author_facet | Kaleem, Waquar Lee, Doyoung Kwon, Changhyun Subramanyam, Anirudh |
| contents | We present a novel framework that combines machine learning with mixed-integer optimization to solve the Capacitated Location-Routing Problem (CLRP). The CLRP is a classical NP-hard problem that integrates strategic facility location with operational vehicle routing decisions, aiming to minimize the sum of fixed and variable costs. The proposed method trains a neural network to approximate the optimal cost of a Capacitated Vehicle Routing Problem (CVRP) for serving any subset of customers from a candidate facility. Crucially, the neural network is trained on an independently generated dataset of CVRP instances from the literature, entirely separate from any CLRP test instances, thereby avoiding the overfitting and information leakage that can affect learning-based methods. The trained network is then embedded as a surrogate within a mixed-integer optimization model for location-allocation decisions, which is solved using off-the-shelf solvers, thus leveraging decades of advances in vehicle routing and the availability of mature solvers. Computational experiments across four benchmark sets demonstrate competitive solution quality compared to best-known solutions while providing computational speedups of 2x to 120x over state-of-the-art heuristics. After a one-time training cost of only 6 hours, per-instance solve times range from under a second to under five minutes, even for the largest instances with 600 customers and 30 depots, where the method achieves a 1% median gap compared to over four hours for leading heuristics. Our results demonstrate the value of routing cost approximations from the neural surrogate in informing high-quality location-allocation decisions. Our code and data are publicly available. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_05665 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Neural Embedded Mixed-Integer Optimization for Location-Routing Problems Kaleem, Waquar Lee, Doyoung Kwon, Changhyun Subramanyam, Anirudh Optimization and Control 90C11 We present a novel framework that combines machine learning with mixed-integer optimization to solve the Capacitated Location-Routing Problem (CLRP). The CLRP is a classical NP-hard problem that integrates strategic facility location with operational vehicle routing decisions, aiming to minimize the sum of fixed and variable costs. The proposed method trains a neural network to approximate the optimal cost of a Capacitated Vehicle Routing Problem (CVRP) for serving any subset of customers from a candidate facility. Crucially, the neural network is trained on an independently generated dataset of CVRP instances from the literature, entirely separate from any CLRP test instances, thereby avoiding the overfitting and information leakage that can affect learning-based methods. The trained network is then embedded as a surrogate within a mixed-integer optimization model for location-allocation decisions, which is solved using off-the-shelf solvers, thus leveraging decades of advances in vehicle routing and the availability of mature solvers. Computational experiments across four benchmark sets demonstrate competitive solution quality compared to best-known solutions while providing computational speedups of 2x to 120x over state-of-the-art heuristics. After a one-time training cost of only 6 hours, per-instance solve times range from under a second to under five minutes, even for the largest instances with 600 customers and 30 depots, where the method achieves a 1% median gap compared to over four hours for leading heuristics. Our results demonstrate the value of routing cost approximations from the neural surrogate in informing high-quality location-allocation decisions. Our code and data are publicly available. |
| title | Neural Embedded Mixed-Integer Optimization for Location-Routing Problems |
| topic | Optimization and Control 90C11 |
| url | https://arxiv.org/abs/2412.05665 |