Exact separation of the rounded capacity inequalities for the capacitated vehicle routing problem

Konstantin Pavlikov*, Niels Christian Petersen, Jon Lilholt Sørensen

*Corresponding author for this work

Research output: Contribution to journalJournal articleResearchpeer-review

36 Downloads (Pure)

Abstract

The family of Rounded Capacity (RC) inequalities is one of the most important sets of valid inequalities for the Capacitated Vehicle Routing Problem (CVRP). This paper considers the problem of separation of violated RC inequalities and develops an exact procedure employing mixed integer linear programming. The developed routine is demonstrated to be very efficient for small and medium sized problem instances. For larger-scale problem instances, an iterative approach for exact separation of RC inequalities is developed, based upon a selective variable pricing strategy. The approach combines column and row generation and allows us to introduce variables only when they are needed, which is essential when dealing with large-scale problem instances. A computational study demonstrates scalability of the proposed separation routines and provides exact RC-based lower bounds to some of the publicly available unsolved CVRP instances. The same computational study provides RC-based lower bounds for very large-scale CVRP instances with more than 3000 locations obtained within appropriate computational time limits.
Original languageEnglish
JournalNetworks
Volume83
Issue number1
Pages (from-to)197-209
ISSN0028-3045
DOIs
Publication statusPublished - Jan 2024

Keywords

  • capacitated vehicle routing
  • rounded capacity inequalities

Fingerprint

Dive into the research topics of 'Exact separation of the rounded capacity inequalities for the capacitated vehicle routing problem'. Together they form a unique fingerprint.

Cite this