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(cn2) time (n is number of nodes in the network and c is a constant) to improve the dual solution. Our heuristic obtained the optimal solution 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.
transportation transportation problem distribution