Distribution with Quality of Service Considerations: The Capacitated Routing Problem with Profits and Service Level Requirements

Research output: Contribution to JournalArticleAcademicpeer-review

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.

Original languageEnglish
JournalOmega (United Kingdom)
DOIs
Publication statusAccepted/In press - 1 Jan 2019

Fingerprint

Quality of service
Profit
Routing
Service levels
Valid inequalities
Penalty
Cash
Logistics service providers
Revenue
Vehicle routing problem
Optimality
Usefulness
Node
Supply chain
The Netherlands
Sensitivity analysis
Logistics
Costs

Keywords

  • ATM cash replenishment
  • Branch-and-Cut
  • Cash logistics
  • Routing with profits
  • Service level requirements

Cite this

@article{39965a58179f4a3f91449bb599960acd,
title = "Distribution with Quality of Service Considerations: The Capacitated Routing Problem with Profits and Service Level Requirements",
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.",
keywords = "ATM cash replenishment, Branch-and-Cut, Cash logistics, Routing with profits, Service level requirements",
author = "Christos Orlis and Demetrio Lagan{\'a} and Wout Dullaert and Daniele Vigo",
year = "2019",
month = "1",
day = "1",
doi = "10.1016/j.omega.2019.02.003",
language = "English",
journal = "Omega",
issn = "0305-0483",
publisher = "Elsevier BV",

}

TY - JOUR

T1 - Distribution with Quality of Service Considerations

T2 - The Capacitated Routing Problem with Profits and Service Level Requirements

AU - Orlis, Christos

AU - Laganá, Demetrio

AU - Dullaert, Wout

AU - Vigo, Daniele

PY - 2019/1/1

Y1 - 2019/1/1

N2 - 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.

AB - 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.

KW - ATM cash replenishment

KW - Branch-and-Cut

KW - Cash logistics

KW - Routing with profits

KW - Service level requirements

UR - http://www.scopus.com/inward/record.url?scp=85062173692&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85062173692&partnerID=8YFLogxK

U2 - 10.1016/j.omega.2019.02.003

DO - 10.1016/j.omega.2019.02.003

M3 - Article

JO - Omega

JF - Omega

SN - 0305-0483

ER -