This paper addresses a distribution problem in a multi-product, multi-echelon supply chain. We develop a mixed integer linear programming formulation that considers allocation of vehicles with varying capacities for the transportation of products between the stages of the supply chain. The cost of transportation includes the fixed and variable costs of using the vehicles. The proposed formulations are solved optimally up to certain sizes, and we propose a heuristic based on total opportunity penalty cost method to solve the large sized problems. These proposed solution procedure is tested over a set of hypothetical problem sets. The results indicate that the proposed heuristic algorithm yields solutions within 5% from the optimal solutions. © 2017 Inderscience Enterprises Ltd.