The Vehicle Routing Problem with Time Windows (VRPTW) is a critical, NP-hard optimization challenge in modern logistics. While metaheuristics like Large Neighborhood Search (LNS) are effective, they often struggle with premature convergence to local optima. This paper proposes a novel hybrid framework where Multi-Agent Actor-Critic (MA2C) learning, incorporating Social Optimization (SO), is used to enhance a Large Neighborhood Search (LNS) algorithm for effectively solving the VRPTW. Our model synergizes two key components: (1) a Multi-Agent Actor-Critic framework inspired by Social Optimization (MRSO), which features an attention mechanism and is trained via reinforcement learning to construct high-quality, feasible routes; and (2) a Large Neighborhood Search (LNS) framework that efficiently explores the solution space by systematically destroying and repairing routes, allowing the search to escape local optima. The algorithm strategically alternates between the MRSO agent’s constructive heuristic and the LNS algorithm’s local search refinement. We evaluated our model on the Solomon RC1 and RC2 benchmark instances, comparing it against standalone LNS and the pure MRSO-based construction. Experimental results demonstrate that our proposed hybrid algorithm significantly outperforms both baselines. On RC1 instances, our model achieved an average distance of 1056.76 with 9.75 vehicles, representing a 32.9% distance improvement over standalone LNS (1574.76, 15.63 vehicles). On RC2 instances, it achieved 1064.71 with 8.75 vehicles, a 21.1% improvement over LNS (1349.33, 10.00 vehicles). The hybrid model consistently finds superior solutions, validating the robust synergy between multi-agent deep learning and metaheuristic search for complex combinatorial optimization problems.