Search papers, labs, and topics across Lattice.
This paper reformulates the Vehicle Routing Problem (VRP) as a Graph Edit Distance (GED) maximization problem, allowing for a novel edge-level analysis of routing solutions. By establishing a merge-decomposition theorem and an approximation-transfer theorem, the authors demonstrate that minimizing route costs corresponds to maximizing deleted edge weights in the complete instance graph. Their analysis of 90 CVRP benchmark instances reveals that optimal routing graphs utilize only 5.5% of available edges, highlighting significant gaps in heuristic methods like Clarke-Wright.
Optimal vehicle routing solutions leverage only a fraction of available edges, exposing critical limitations in traditional heuristics that could reshape routing algorithm design.
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.
