New Lower Bounds and Exact Method for the m -PVRP

Sandra Ulrich Ngueveu (), Christian Prins () and Roberto Wolfler Calvo ()
Additional contact information
Sandra Ulrich Ngueveu: CNRS, LAAS, F-31400 Toulouse, France; and Univerité de Toulouse, INP, LAAS, F-31400 Toulouse, France
Christian Prins: ICD-LOSI (UMR 6279), Université de Technologie de Troyes, 10010 Troyes Cedex, France
Roberto Wolfler Calvo: LIPN (UMR 7030), Université de Paris-Nord, 93430 Villetaneuse, France

Transportation Science, 2013, vol. 47, issue 1, 38-52

Abstract: This paper presents new lower bounding procedures and an exact method for the m -peripatetic vehicle routing problem ( m -PVRP) based on polyhedral and column generation approaches. The branch-and-cut algorithms use three types of valid cuts on the edge-based formulation. The column-generation-based lower bounding procedure is applied on the dual set partitioning formulation and is composed of dual heuristics that estimate good dual variable values and therefore high lower bounds. Computational results on instances from the literature show that these new lower bounds reach on average 97.5% to 99% of the best known upper bounds and optimality is proven for a third of the instances.

Keywords: lower bounds; exact methods; branch-and-cut; column generation; dual ascent; m-peripatetic vehicle routing problem (search for similar items in EconPapers)
Date: 2013
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.1120.0421 (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:inm:ortrsc:v:47:y:2013:i:1:p:38-52

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().