A p-step formulation for the capacitated vehicle routing problem

Twan Dollevoet, Pedro Munari and Remy Spliet

No EI2020-01, Econometric Institute Research Papers from Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute

Abstract: We introduce a _p_-step formulation for the capacitated vehicle routing problem (CVRP). The parameter _p_ indicates the length of partial paths corresponding to the used variables. This provides a family of formulations including both the traditional arc-based and path-based formulations. Hence, it is a generalization which unifies arc-based and path-based formulations, while also providing new formulations. We show that the LP bound of the _p_-step formulation is increasing in _p_, although not monotonically. Furthermore, we prove that computing the set partitioning bound is NP-hard. This is a meaningful result in itself, but combined with the _p_-step formulation this also allows us to show that there does not exist a strongest compact formulation for the CVRP, if _P ≠ NP_. While ending the search for a strongest compact formulation, we propose the search for the strongest formulation of the CVRP with a number of variables and constraints limited by a polynomial of fixed degree. We provide new strongest such formulations of degree three and higher by using a corresponding _p_-step formulation. Furthermore, the results of our experiments suggest that there are computational advantages from using the _p_-step formulation, instead of traditional arc-based and path-based formulations.

Pages: 48
Date: 2020-01-01
New Economics Papers: this item is included in nep-cmp
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
https://repub.eur.nl/pub/123411/EI-2020-01.pdf (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:ems:eureir:123411

Access Statistics for this paper

More papers in Econometric Institute Research Papers from Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute Contact information at EDIRC.
Bibliographic data for series maintained by RePub ( this e-mail address is bad, please contact ).