Distribution with Quality of Service Considerations: The Capacitated Routing Problem with Profits and Service Level Requirements. (June 2020)

• Record Type: Journal Article
• Authors: Orlis, Christos; Laganá, Demetrio; Dullaert, Wout; Vigo, Daniele
• Is Part Of: Omega. Volume 93(2020)
• Publication Date: 2020-06
• Subjects: Routing with profits -- Cash logistics -- ATM cash replenishment -- Service level requirements -- Branch-and-Cut; Management -- Periodicals; 658.4005
• DOI: 10.1016/j.omega.2019.02.003
• Languages: English
• ISSNs: 0305-0483

Abstract

Highlights: We introduce a new routing problem that incorporates a real-life Key Performance Indicator (KPI). Customers may be represented by multiple service points in the graph modeling of the problem. A branch-and-cut algorithm is developed by incorporating three families of adapted valid inequalities. We present computational results for 180 synthetic instances with up to 30 service point requests. A real-life case study illustrates the trade-off between different KPIs and profitability levels. Abstract: 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 in 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. A real-life case study taken from the cash supply chain in the Netherlands highlights 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 instances of real-life problems, we distinguish between coin and banknote distribution, as vehicle capacities only matter when considering the former. Finally, we report on the effectiveness of the valid inequalities in closing the optimality gap at the root node for both the synthetic and the real-life instances and conclude with a sensitivity analysis on the most significant input parameters of our model.