A variable MIP neighborhood descent algorithm for managing inventory and distribution of cash in automated teller machines

Abstract

In this paper we propose a new hybrid algorithm to solve mixed-integer programming (MIP) models called Variable MIP Neighborhood Search (VMND). The VMND relies on an existing mathematical formulation of the problem and significantly accelerates its resolution compared to standalone MIP solvers. Using this algorithm, we solve a practical problem arising in the ATM management and replenishment in Santiago, Chile. This rich and challenging problem, which we call the inventory-routing problem with cassettes and stockouts, shares much of its structure with the inventory-routing problem, but some features make it unique. We exploit the structure of the problem to derive neighborhoods implemented in our VMND, be it over routes, locations, periods or quantities delivered. Based on extensive computational experiments, our VMND is shown to significantly outperform benchmark solutions from a branch-and-cut algorithm. A sensitivity analysis is performed to confirm the robustness and effectiveness of our method.