Study of Robust Features in Formulating Guidance for Heuristic Algorithms for Solving the Vehicle Routing Problem
This work provides incremental insights for researchers and practitioners in combinatorial optimization by using explainable AI to guide metaheuristic algorithm design for VRP.
The study tackled the Vehicle Routing Problem by analyzing feature importance in machine learning models that predict solution quality, finding that certain features consistently predict well and proposing a framework to rank feature impact across scenarios.
The Vehicle Routing Problem (VRP) is a complex optimization problem with numerous real-world applications, mostly solved using metaheuristic algorithms due to its $\mathcal{NP}$-Hard nature. Traditionally, these metaheuristics rely on human-crafted designs developed through empirical studies. However, recent research shows that machine learning methods can be used the structural characteristics of solutions in combinatorial optimization, thereby aiding in designing more efficient algorithms, particularly for solving VRP. Building on this advancement, this study extends the previous research by conducting a sensitivity analysis using multiple classifier models that are capable of predicting the quality of VRP solutions. Hence, by leveraging explainable AI, this research is able to extend the understanding of how these models make decisions. Finally, our findings indicate that while feature importance varies, certain features consistently emerge as strong predictors. Furthermore, we propose a unified framework able of ranking feature impact across different scenarios to illustrate this finding. These insights highlight the potential of feature importance analysis as a foundation for developing a guidance mechanism of metaheuristic algorithms for solving the VRP.