RouteExplainer: An Explanation Framework for Vehicle Routing Problem
Daisuke Kikuta Hiroki Ikeuchi Kengo Tajiri Yuusuke Nakano
The Vehicle Routing Problem (VRP) is a widely studied combinatorial
optimization problem and has been applied to various practical problems. While
the explainability for VRP is significant for improving the reliability and
interactivity in practical VRP applications, it remains unexplored. In this
paper, we propose RouteExplainer, a post-hoc explanation framework that
explains the influence of each edge in a generated route. Our framework
realizes this by rethinking a route as the sequence of actions and extending
counterfactual explanations based on the action influence model to VRP. To
enhance the explanation, we additionally propose an edge classifier that infers
the intentions of each edge, a loss function to train the edge classifier, and
explanation-text generation by Large Language Models (LLMs). We quantitatively
evaluate our edge classifier on four different VRPs. The results demonstrate
its rapid computation while maintaining reasonable accuracy, thereby
highlighting its potential for deployment in practical applications. Moreover,
on the subject of a tourist route, we qualitatively evaluate explanations
generated by our framework. This evaluation not only validates our framework
but also shows the synergy between explanation frameworks and LLMs. See
https://ntt-dkiku.github.io/xai-vrp for our code, datasets, models, and demo.