545 / 2024-04-25 20:44:30

Multiple unreliable knapsack problem

Multiple knapsack problem,vending machine,reliability,assortment and placement

We investigate the unreliable knapsack problem with an application to the assortment and placement problem for unreliable smart vending machines. The complexity of the general problem is exponential because the number of failed knapsacks is combinatorial. For the special case of identical knapsacks, we characterize the optimal solution and develop a polynomial algorithm to find the optimal assortment and placement of items across the unreliable knapsack. Based on the insights obtained from the case of identical knapsacks, we then design a polynomial approximation algorithm for the general case of knapsacks with different capacities, and provide performance bounds on the approximation gap. Numerical experiments show that our algorithm outperforms general solvers and results in a higher revenue than that under strategies without considering knapsack reliability. Using real data from a retail company, we observe a revenue increment more than 7% for vending machines with reliability of 90%. Moreover, we conduct comprehensive analysis on how relevant parameters such as the reliability and size of knapsacks affect the optimal assortment and placement and provide valuable insights for managers.