A Lagrangian Relaxation Heuristic (LRH) to solve the integrated distribution planning problem of selecting transportation mediums(conveyances), route selection, load consolidation and location of facilities has been studied in this paper.  The problem is known as Facility Location and Fixed charge Solid Transportation with real life applications of integrating several planning horizons of small, medium and long terms. A numerical example was proposed and solved using two different sets of Lagrange multipliers as starting values for the iterations performed and termed the first and second trial runs respectively. The CPLEX standard optimization software was used as a base for comparing the LRH obtained. A simple infeasibility resolution of the better LRH (second trial) lower bound solution was applied to obtain the CPLEX values. Extensive computations of various problem sizes and instances will however be required to validate the good performance of LRH (second trial) run obtained compared to using standard optimization solvers such as CPLEX.