Template-Type: ReDIF-Paper 1.0
Author-Name: Dollevoet, T.A.B.
Author-Name-Last: Dollevoet
Author-Name-First: Twan
Author-Name: Munari, P.
Author-Name-Last: Munari
Author-Name-First: Pedro
Author-Name: Spliet, R.
Author-Name-Last: Spliet
Author-Name-First: Remy
Title: A p-step formulation for the capacitated vehicle routing problem
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.
Length: 48
Creation-Date: 2020-01-01
File-URL: https://repub.eur.nl/pub/123411/EI-2020-01.pdf
File-Format: application/pdf
Series: RePEc:ems:eureir
Number: EI2020-01
Handle: RePEc:ems:eureir:123411