The operation of vending machine system presents a decision-making problem which consists of determining the product allocation to vending-machine storage compartments, replenishment intervals of vending machines, and vehicle routes, all of which have critical effects on system profit. Especially, it becomes more difficult to determine the operation variables optimally when demand for a product that is out-of-stock spills over to another product or is lost. In this paper, we propose a heuristic for solving the operation problem of the vending machine system and evaluate it by comparing with Yang's algorithm on various test problems with respect to system profit via a computer simulation. The results of computational experiments show a substantial profit increase of the proposed heuristic over Yang's algorithm. Sensitivity analysis indicates that some input variables impact the profit increase significantly.