A DYNAMIC PROGRAMMING HEURISTIC FOR RETAIL SHELF SPACE ALLOCATION PROBLEM

Shelf space allocation to products greatly impacts the profitability in a retail store. In this paper, we consider a retail shelf-space allocation problem where retailer wishes to allocate the available spaces of different shelves to a large number of products considering direct space elasticity in the product's demand. There is a great interest to develop efficient heuristics due to NP-hard nature of this problem. We propose a dynamic programming heuristic (DPH) to obtain near optimal solution in a reasonable time to solve this problem. The empirical results found that DPH obtained near optimal solutions for randomly generated instances of problems with size (products, shelves) varying from (100, 30) to (200, 50) within a few seconds of CPU time. The performance of DPH is benchmarked against an existing local search heuristic (LSH). It was found that DPH takes substantially less CPU time and attains a solution close to that obtained by LSH. Thus, DPH has great potential to solve the problem of realistic size within reasonable time. The proposed DPH is also applied to a case of an existing retail store.