Exact and heuristic methods for the risk-constrained cash-in-transit vehicle routing problem

This paper investigates the risk-constrained cash-in-transit vehicle routing problem (RCTVRP), in which each customer is visited by a vehicle that collects a predetermined amount of cash. The risk associated with a route is defined as the product of the distance traveled and the amount of cash being transported. The objective is to minimize the total distance traveled while ensuring that the risk on each route does not exceed a predefined threshold. To tackle the RCTVRP, we propose two approaches: an exact branch-cut-and-price (BCP) algorithm and a metaheuristic that combines iterated local search, randomized variable neighborhood descent, and a set partitioning model. Computational experiments conducted on benchmark instances with up to 337 nodes demonstrate that both the proposed exact and heuristic approaches outperform the best existing methods in the literature, in terms of both solution quality and computational time. The proposed exact method optimally solved 87 out of 123 tested instances, while the proposed heuristic matched or improved the best known solution in 117 out of 138 instances.