We address the problem of distributing a limited amount of inventory among customers using a fleet of vehicles so as to maximize profit. Both the inventory allocation and the vehicle routing problems are important logistical decisions. In many practical situations, these two decisions are closely interrelated, and therefore, require a systematic approach to take into account both activities jointly. We formulate the integrated problem as a mixed integer program and develop a Lagrangian-based procedure to generate both good upper bounds and heuristic solutions. Computational results show that the procedure is able to generate solutions with small gaps between the upper and lower bounds for a wide range of cost structures.