We consider a bilevel programming formulation of a freight tariff setting problem where the leader consists in one among a group of competing carriers and the follower is a shipper. At the upper level, the leader's revenue corresponds to the total tariffs levied, while the shipper minimizes its transportation cost, given the tariff schedule set by the leader. We propose for this problem a class of heuristic procedures whose relative efficiencies, on small problem instances, could be validated with respect to optimal solutions obtained from a mixed integer reformulation of the mathematical model. We also present numerical results on large instances that could not be solved to optimality by an exact method.