Comparison between LP bound of the Two-Index and the Three-Index Vehicle Flow Formulation for the Capacitated Vehicle Routing Problem

M.N. Pham (Minh Ngoc)

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

Abstract: This paper looks into the Two-Index Vehicle Flow Formulation and the Three-Index Vehicle Flow For- mulation for the Capacitated Vehicle Routing Problem. Aside from comparing the number of variables and constraints, we also compare the strength of the LP bound of each formulation. As a result, we found that the Two-Index Vehicle Flow Formulation produces stronger LP bound than the Three-Index Formulation. Furthermore, we also found that these formulation deals with slightly dierent problems. Thus, we adjusted the two formulations so that they solve the same problem, while also prove that the LP bound of the Two-Index Formulation is at least that of the Three-Index Formulation.

Keywords: Vehicle Routing Problem; Formulations; LP bounds (search for similar items in EconPapers)
Pages: 16
Date: 2021-05-01
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://repub.eur.nl/pub/135594/EI2021-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:135594

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