The optimization of transportation problems plays a significant role in supply chain management (SCM), where minimizing costs and improving efficiency are mandatory. The transition from manual methods to advanced computational approaches, such as metaheuristic algorithms, enhances decision-making and consolidates operations within SCM. Malaysia's transportation system has been confronting crucial challenges, characterized by congested roadways, limited rail connectivity and inefficient port operations, which interfere with the fluidity of goods and supply chain efficiency. This highlights the critical need for optimization techniques to enhance competitiveness and efficiency in the evolving SCM landscape. The research aims to explore the application of metaheuristic algorithms, with the Modified Distribution (MODI) method as the benchmark while employing the NorthWest Corner Method (NWCM) to obtain an initial feasible solution, to evaluate their performance in optimizing transportation problems. Metaheuristic algorithms, specifically Simulated Annealing (SA) and Particle Swarm Optimization (PSO), are implemented to explore alternative near-optimal solutions and assess the performance in terms of cost accuracy and computational efficiency. The results indicate that SA achieves a deviation of 12.92% in cost accuracy compared to the optimal MODI method, making it suitable for scenarios where precision is critical, whereas PSO which is 296.92 seconds faster, is ideal for time-sensitive applications. Finally, this study encourages future studies to explore additional algorithms, external factors and broader applications for enhanced real-world relevance and scalability to accentuate the potential of metaheuristic algorithms.