This paper introduces a meta-heuristic enabled multi-agent optimization architecture for dynamic transportation planning in the supply chain procurement (SCP) plans. When multi-agent systems (MAS) are used for real-time dynamic optimization, agents seek the solution using distributed heuristics. However, distributed heuristics based on local information are prone to converge at local optimality. To escape from local optimality toward higher quality solution, we introduce meta-heuristics over agent interactions to advise agents' searching process. In this paper, we mainly propose variable neighborhood search meta-heuristic (VNS-MH) over distributed market based heuristic (DMBH), a distributed heuristic based on market interactions for transportation planning. The numerical results show that VNS-MH performs better on achieving optimality than DMBH.