A HEURISTIC AND LOWER-BOUND FOR A MULTI-DEPOT ROUTING PROBLEM

The multi-depot routing problem considered here deals with a situation where a fleet of tau trucks is used to transport rho different raw ma terials available at sigma sources to tau plants. A heuristic is prese nted for solving this problem. An initial feasible solution is found b y determining the least costly way of supplying each plant with the ma terial demanded, one plant at a time. Then routes are exchanged for ea ch truck if a net cost savings can be realized, while maintaining feas ibility. The heuristic is compared to a lower bound obtained from a re laxed binary formulation. Both methods are applied to four sets of ran domly generated problems with different values for tau, sigma, pi, and for the maximum number of trips allowed. The problems ranged in size from 52 to 609 nodes in the lower bound formulation. The results from the heuristic exceed the bound by 2-4% for problem sets with 52-303 no des. For the larger problems this percentage reaches 8%. The gap is du e partly to the lower bound having a smaller value than the optimal so lution and partly to the heuristic being non-optimal.