Scientific Program > Talks by Speaker > Orlis Christos

Inspired by a real-life case 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 service points. Moreover, each customer imposes a service level requirement (SLR) specifying a minimum bound on the fraction of its service points being delivered. A customer-specific flat-rate financial penalty is incurred by the Logistics Service Provider (LSP) when this requirement is not met. The CRPPSLR consists of finding vehicle routes maximizing the difference between the collected revenues and 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 identify valid inequalities that have been effectively used for the Capacitated Vehicle Routing Problem and for other Routing Problems with Profits. Moreover, a matheuristic which produces promising starting solution structures is developed and used as a pre-processing step of our branch-and-cut solution framework. A real-life case study in cash distribution highlights the relevance of the problem under consideration and computational results illustrate the performance of the proposed solution approach under different input parameter settings.