Capacitated replenishment and disposal planning for multiple products with resalable returns

We consider a replenishment and disposal planning problem (RDPP) that arises in settings where customer returns are in as-good-as-new condition. These returns can be placed into inventory to satisfy future demand or can be disposed of, in case they lead to excess inventory. Our focus is on a multi-product setting with dynamic demands and returns over a finite planning horizon with explicit replenishment and disposal capacities. The problem is to determine the timing of replenishment and disposal setups, along with the associated quantities for the products, so as to minimize the total costs of replenishment, disposal, and inventory holding throughout the planning horizon. We examine two variants of the RDPP of interest both of which are specifically motivated by a spare part kitting application. In one variant, the replenishment capacity is shared among multiple products while the disposal capacity is product specific. In the other variant, both the replenishment and disposal capacities are shared among the products. We propose a Lagrangian Relaxation approach that relies on the relaxation of the capacity constraints and develop a smoothing heuristic that uses the solution of the Lagrangian problem to obtain near-optimal solutions. Our computational results demonstrate that the proposed approach is very effective in obtaining high-quality solutions with a reasonable computational effort. Copyright Springer Science+Business Media, LLC 2013