Scientific Program > Talks by Speaker > Orlis Christos

The capacitated routing problem with profits and service level requirements
Christos Orlis  1@  , Demetrio Laganà  2@  , Wout Dullaert  3@  , Daniele Vigo  4@  
1 : Vrije University Amsterdam  -  Website
De Boelelaan 1105, 1081 HV Amsterdam -  Netherlands
2 : Università della Calabria [Arcavacata di Rende]  (Unical)  -  Website
Campus di Arcavacata via Pietro Bucci 87036 Arcavacata di Rende (CS) -  Italy
3 : Vrije University Amsterdam  -  Website
De Boelelaan 1105, 1081 HV Amsterdam -  Netherlands
4 : Università di Bologna  (UNIBO)  -  Website
Via Zamboni, 33 - 40126 Bologna -  Italy

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.

Online user: 1 RSS Feed