A multi-product inventory loading problem; a model and a solution method

An operational inventory problem arises during the transportation and delivery of several products, which cannot be mixed, jointly in a single vehicle from a source to a destination. Products are contained in different compartments of the vehicle to prevent mixing. The total inventory costs including holding costs and the joint ordering cost should be minimized under the condition that the delivery quantities of the products should last until the next delivery and only one product can occupy each compartment of the vehicle. We call this a multi-product inventory loading problem. A nonlinear mixed binary model for the multi-product inventory problem is developed. The solution method is based on simultaneously exploring the primal and dual structures derived from the Lagrangian relaxation. Subsetsum problems, a special class of knapsack problems, are obtained as subproblems to the partial Lagrangian. An efficient algorithm with some heuristic rules to find the optimal solution is developed and its convergence in a finite number of steps is proven. Dynamic programming can solve such a problem but proves to be very time consuming. An initial solution finding method is also provided. The model and the solution technique is illustrated on an example problem. Several randomly chosen problems are run to demonstrate the efficiency of the algorithm.