A New Heuristic Method for the Classical Transportation Problem's First Viable Solution

Abstract

The transportation problem is a classic optimization issue in linear programming that focuses on determining the most cost-effective way to allocate resources from multiple supply points to various demand points while meeting specific constraints. Traditionally, methods like the North-West Corner Rule (NWCR), Least Cost Method (LCM), and Vogel’s Approximation Method (VAM) have been employed to generate an initial feasible solution (IFS). However, these approaches often overlook key factors such as supply-demand dynamics or cost balance, which may result in suboptimal starting solutions and longer optimization time. To address these limitations, this paper introduces a novel heuristic approach known as the Weighted Cost Distribution Method (WCDM). This method enhances the initial solution process by calculating a weighted cost matrix that takes into account both the unit transportation cost and the relative size of supply and demand. By sorting and allocating based on this weighted measure, WCDM identifies more efficient routes for early allocations. Comparative analysis demonstrates that WCDM frequently yields better or equivalent initial solutions than conventional methods, thereby reducing the number of iterations needed in final optimization procedures like the Modified Distribution (MODI) method or the stepping-stone method. This leads to faster convergence to the optimal solution and improved computational efficiency.