RouteExplainer: An Explanation Framework for Vehicle Routing Problem

#Vehicle Routing Problem

#Explainability

#Counterfactual Explanation

#Large Language Models

PAKDD 2024

We formulate predicting the intentions of each edge as a many-to-many sequential classification, where the edge classifier takes a route (i.e., sequence of edges) and sequentially classifies each edge. We here propose a Transformer-based edge classifier, which consists of a node encoder, edge encoder, and classification decoder (Fig.2). The node encoder first converts input features into higher-dimensional embeddings with a linear projection and the subsequent Transformer encoders [14] (without positional encoding). Then, the edge encoder generates edge embeddings by concatenating three vectors: two node embeddings of the end of the edge and global states (e.g., current time). In the classification decoder, Causal Transformer encoders (without positional encoding) take the edge embeddings arranged in the route order as input tokens, and then generate the final embeddings of each edge. After a linear projection adjusts the dimension of the final embedding to the number of classes (intention types), the decoder finally outputs the probabilities of each class of each edge by applying the Softmax to the adjusted embeddings.

We prepare datasets labeled by a rule-based annotation and train the edge classifier on the datasets in supervised learning. Some of our datasets have step-wise class imbalanceness such that a class (intention) is majority in the early steps, whereas another class becomes majority as the steps progress. Existing class-balanced loss function cannot handle this because they consider only batch-level imbalanceness. To address this, we propose a step-wise class-balanced cross entropy, which considers step-wise class imbalanceness by separately computing balancing weights at each step.

In this work, we propose a rule-based edge annotation. In particular, we here describe the rule for Traveling Salesman Problem with Time Windows (TSPTW), where we assume that each edge is labeled as either "prioritizing route length" or "prioritizing time windows". Fig.3 shows an example of the annotation in a TSPTW route (top of Fig.3) and the general edge annotation algorithm (bottom of Fig.3). Let's consider the example of labeling the red edge in the TSPTW route. A VRP solver first solves VRP that removes constratins (i.e., TSPTW - time windows = TSP) with past edges (i.e., edges before the red edge) fixed. Then, we compare the red edge in the TSPTW route and the edge at the same step in the TSP route (i.e., the green edge). If they are identical, the red edge is labeled as "prioritizing route length", otherwise, "prioritizing time windows". Intuitively, the green edge is optimal when only route length is considered, so if the red edge matches it, the red edge is considered to prioritize route length. Otherwise, the red edge is considered to have changed from the green edge to adhere to time windows, rather than optimizing route length. See rules for other VRPs in our paper.

RouteExplainer justifies the actual edge by comparing the influences of the actual and CF edges. To quantify the influence of an edge while considering its impact on the subsequent edges, we introduce Edge Influence Model (EIM), which is an extension of the actual influence model (AIM) [13] for VRP. AIM is an extension of Structural Causal Model (SCM) [15] for actions in reinforcement learning, which replaces variables and directed edges in a Directed Acycle Graph (DAG) with environmental states and actions, respectively (l.h.s of Fig.4). The authors [13] leverage AIM to generate counterfactual explanation for a specific action taken by a model, where that action is justified by comparing the subsequent states of that action and those of a counterfactual action.

Rethinking a route as the sequence of actions (i.e., edges/movements between two nodes), we extend AIM to EIM, which replaces environmental states and actions in AIM with nodes and edges in a VRP instance (r.h.s of Fig.4 ). Each node in EIM possesses environmental states when it is visited (we name them global states). For TSPTW, the global state is the intermidiate route length/travel time, and the structural equation between the previous and next global state is defined as \(S_{(i, t+1)}=S_{(j, t)}+d(v_{i}, v_{j})\), where \(S_{(i, t)}\) is the global state of the \(i\)-th node when visited at step \(t\) and \(d(v_{i}, v_{j})\) is the route length/travel time of the edge between \(i,j\)-th nodes. The set of causal paths in EIM (red pahts in r.h.s of Fig. ) corresponds to a route.

Based on EIM, we define the influence of the edge at step \(t\) in a route as the tuple of the subsequent global states and edge intentions to that edge: \(\boldsymbol{I}_{e_t} = \left(S_{(\pi_{t+1}, t+1)}, \hat{y}_{t+1}, S_{(\pi_{t+2}, t+2)},\dots, \hat{y}_{T-1}, S_{(\pi_{T}, T)}\right)\), where \(\hat{y}_{t}\) is the intention of the edge at step \(t\). To make this more understandable by humans, we further define the respresentative values that reflects \(\boldsymbol{I}_{e_t}\) at the minimum necessary. For TSPTW, we select four representative values calculated from \(\boldsymbol{I}_{e_t}\): the shor-term effect \(S_{(\pi_{t+1}, t+1)}\), long-term effect \(S_{(\pi_{T}, T)}\), intention ratio, and infeasibility ratio. RouteExplainer explains the influence of the actual edge by comparing (taking difference of) the representative values of the actual and CF edges. See our paper for more detailed formulation. In the next slide, we will describe how to generate the final explanation text with LLMs.

RouteExplainer leverages an LLM for generating the final explanation text. We use GPT-4 without additional finetuning and acomplish the explanation generation by in-context learning. Fig.5 shows the system prompt for generating explanation based on RouteExplainer. The comparion of representative values of the actual and CF edges' influences are embedded to {comparison_results} in the system prompt, of which format is the same as the example in the system prompt. The system prompt first clarifies the task here with the description of RouteExplainer and the terminology. It then instructs the LLM to justify the actual edge while mentioning the pros and cons of the actual and CF edges, which are determined by the comparison of the four representative values of those edges. For example, the smaller short/long-term effect (i.e., intermediate/total travel time) and # unvisited nodes (i.e., infeasibility ratio), the better. Subsequent class ratio (i.e., intention ratio) is basically a neutral metric, but it gives us the insights of the edge infuluence. The supplementary information allows the LLM to make the pros and cons more detail while relating them to that information. Prompt-engineering techniques used here include role-play prompting (clarifying the task), one-shot prompting (showing an example of the expected output), and optimizing the placement of prompts (placing important prompts at the beginning or end of the whole prompt).