A new dual based procedure for the transportation problem

We pose the transportation problem in a slightly different form to obtain a dual problem that has a special structure. We exploit the structure of the dual problem to give a new heuristic that runs in O(cn²) time (n is the number of nodes in the network and c is a constant) to improve the dual solution. Our heuristic obtained the optimal solutions to several small sized transportation problems that we attempted; and for large sized problems it obtained solutions that were within 82% of the optimal solution on average. Our approach gives good starting solutions for dual based approaches used for solving transportation problems and thus is expected to enhance their computational performance.