AI summaryⓘ
The authors show that the Vehicle Routing Problem (VRP), which involves finding the best paths for vehicles delivering goods, can be seen as a problem of editing a graph by deleting edges. They explain that minimizing route costs is the same as maximizing the weight of edges removed from a complete graph representing the problem. This new view allows them to analyze the problem in terms of individual edges, making it easier to understand solution quality and the difference between good and bad routes. They also link their approach to known heuristics and test it on many examples, discovering patterns about which edges are used or missed. Finally, they suggest their edge-focused method could help improve future machine learning models for routing problems.
Vehicle Routing ProblemGraph Edit DistanceEdge-deletion cost modelClarke-Wright savingsHeuristicsGraph Neural NetworksCost gap decompositionRoute optimizationCVRP benchmark
Abstract
We show that the Vehicle Routing Problem (VRP) can be reformulated as a Graph Edit Distance (GED) maximization problem. Under a simple edge-deletion cost model, minimizing total route cost is equivalent to maximizing the total weight of edges deleted from the complete instance graph. This formulation models VRP at the edge level, where solutions are defined by selected edges rather than route sequences, enabling structural analyses that are difficult in classical formulations: per-edge attribution of solution quality, decomposition of the optimality gap, characterization of solution sparsity, and identification of edges that are hard to reach by greedy construction. Theoretically, we establish a merge-decomposition theorem showing that Clarke-Wright savings equal per-merge GED increments, and an approximation-transfer theorem that turns GED approximation ratios into VRP cost bounds. Using this reformulation, we analyze 90 CVRP benchmark instances with known optimal solutions. We find that optimal routing graphs use only 5.5% of available edges, that approximately 3.0% of optimal edges are consistently not found by Clarke-Wright heuristics under repeated restarts, and that the cost gap decomposes into missed optimal edges and substituted non-optimal edges of comparable total weight. The edge-additive objective provides a natural per-edge supervision signal for future graph neural network approaches to edge prediction, suggesting a potential connection to graph neural network approaches that we leave for follow-up work.