Solving multi-depot vehicle routing problem (MDVRP) in centralized setting has known scalability issues. This paper presents an innovative multi-agent and multi-round reinforcement learning procedure over adaptive elitist solutions selected from an evolving population pool, to near optimally solve MDVRP in a distributed setting. The paper contribution is threefold: First, it illustrates an effective solution finding procedure for MDVRP with limited information sharing in a realistic setup of agent’s control over depot and fleet. Second, it elaborates an agent-centric heuristic algorithm to navigate the solution space toward near-optimality based on elitist selection. In this context, a dynamic weighted probability distribution template generator is used to evolve increasingly better representative fractions of the solution population. Finally, it presents noteworthy results by applying the procedure on known MDVRP problem instances. The results are analyzed to assess solution quality.