<p>Inefficient distribution planning of building materials in Morocco leads to higher costs, increased workload, and greater carbon emissions, making optimization essential from both economic and environmental perspectives. We modeled this distribution problem as a multi-depot vehicle routing problem. In this formulation, multiple depots represent production or distribution facilities that must serve a large number of construction sites while operating with limited fleet capacity. To address this issue, we present a novel implementation of adaptive large neighborhood search that uses relative operators. Our method starts by generating an initial solution using the cheapest insertion heuristic. The solution is then optimized by iteratively destroying and repairing portions of it using weighted operators. We evaluated our algorithm using the Cordeau benchmark instances, and the results show that our approach outperforms classical adaptive large neighborhood search and achieves competitive performance compared to state-of-the-art algorithms, reaching an average gap of 0.47% from the best-known solutions.</p>