An inventory-routing problem with pickups and deliveries arising in the replenishment of automated teller machines

摘要

Credit institutions in the Netherlands are gradually replacing regular automated teller machines (ATMs) by recirculation ATMs (RATMs), which are capable of accepting and dispensing banknotes, as well as checking their quality and authenticity. RATMs are beneficial to banks as well as customers and are increased by 41% between 2012 and 2014. When an RATM is empty, a customer can only use it to deposit cash, and when it is full only withdrawals are allowed. The fleet of rented armored trucks, which are very expensive, deliver cash from a depot to some machines, collect cash from some others to bring it back to the depot, or transfer cash between machines. The last operation reduces the routing cost and sometimes allows smaller or fewer trucks to be used. An important feature of the problem is the presence of inventory holding costs because it is insured and incurs lost interest income. To keep RATMs fully operational, that is when customers can use the RATM to both deposit and withdraw cash, one must solve an inventory-routing problem with pickups and deliveries (IRPPD). The IRPPD combines the features of two well-known classes of the vehicle routing problem: the inventory-routing problem (IRP) and the pickup and delivery problem (PDP). The purpose of this paper is to introduce, model, and solve an IRPPD arising in the replenishment of ATMs. The problem is decomposed into several sub-problems through the application of a clustering procedure, and the sub-problems are solved by fixing some variables. The resulting sub-problems are then strengthened through the generation of valid inequalities and solved by branch and cut. The problem is first presented in terms of mathematical formulation, and then a mixed-integer formulation is presented. A real life case is illustrated to show the results of the model. (57 refs.)