Distributing cash with KPI considerations: the capacitated routing problem with profits and service level requirements

Inspired by a problem arising in cash logistics, we propose the Capacitated Routing Problem with Profits and Service Level Requirements (CRPPSLR). The CRPPSLR extends the class of Routing Problems with Profits by considering customers requesting deliveries to their (possibly multiple) service points. Moreover, each customer imposes a service level requirement specifying a minimum-acceptable bound on the fraction of its service points being delivered. A customer-specific financial penalty is incurred by the logistics service provider when this requirement is not met. The CRPPSLR consists of finding vehicle routes maximizing the difference between the collected revenues and the incurred transportation and penalty costs in such a way that vehicle capacity and route duration constraints are met. A fleet of homogeneous vehicles is available for serving the customers. We design a branch-and-cut algorithm and evaluate the usefulness of valid inequalities that have been effectively used for the capacitated vehicle routing problem and, more recently, for other routing problems with profits. Real-life case studies coming from the cash supply chain in the Netherlands highlight the relevance of the problem under consideration. Computational results illustrate the performance of the proposed solution approach under different input parameter settings for the synthetic instances. For the real-life problem instances we distinguish between coin and banknote distribution since vehicle capacities only matter when considering the former case.

Registration to Remy Spliet, spliet@ese.eur.nl is required for availability of lunch.