This paper introduces, models, and solves a rich vehicle routing problem (VRP)motivated by the case study of replenishment of automated teller machines(ATMs) in Turkey. In this practical problem, commodities can be taken fromthe depot, as well as from the branches to efficiently manage the inventoryshortages at ATMs. This rich VRP variant concerns with the joint multiple depots,pickup and delivery, multi-trip, and homogeneous fixed vehicle fleet. Wefirst mathematically formulate the problem as a mixed-integer linear programmingmodel. We then apply a Geographic Information System (GIS)-basedsolution method, which uses a tabu search heuristic optimization method, to areal dataset of one of the major bank. Our numerical results show that we areable to obtain solutions within reasonable solution time for this new and challengingpractical problem. The paper presents computational and managerialresults by analyzing the trade-offs between various constraints.