The Multi-Depot Vehicle Routing Problem (MDVRP) is a critical challenge in logistics optimization. Most existing heuristic-based algorithms trade off speed and solution quality. It is of great academic significance and application value to study a fast and high-quality algorithm to solve the problem. This work proposes GAMDVRP, the first framework integrating graph neural networks (GNN) with ant colony optimization (ACO) algorithm to address MDVRP. Our key innovation lies in using heuristic information learned from GNN to guide ACO algorithm to solve MDVRP. Experiments demonstrate 16.48%, 23.83%, and 23.97% improvement in solution quality over classical ACO variants across three problem scales (50, 100 and 200 nodes) in synthetic data, achieving 95.5% optimality on real-world benchmarks with greater speedup versus genetic algorithms.