An Exact Algorithm for the Elementary Shortest Path Problem with Resource Constraints
Leonardo Lozano (),
Daniel Duque () and
Andrés L. Medaglia ()
Additional contact information
Leonardo Lozano: Centro para la Optimización y Probabilidad Aplicada (COPA), Departamento de Ingeniería Industrial, Universidad de los Andes, Bogotá, Colombia
Daniel Duque: Centro para la Optimización y Probabilidad Aplicada (COPA), Departamento de Ingeniería Industrial, Universidad de los Andes, Bogotá, Colombia
Andrés L. Medaglia: Centro para la Optimización y Probabilidad Aplicada (COPA), Departamento de Ingeniería Industrial, Universidad de los Andes, Bogotá, Colombia
Transportation Science, 2016, vol. 50, issue 1, 348-357
Abstract:
The elementary shortest path problem with resource constraints (ESPPRC) is an NP-hard problem that often arises in the context of column generation for vehicle routing problems. We propose an exact solution method that relies on implicit enumeration with a novel bounding scheme that dramatically narrows the search space. We embedded our algorithm within a column generation to solve the linear relaxation (root node) of the vehicle routing problem with time windows (VRPTW) and found that the proposed algorithm performs well when compared against state-of-the-art algorithms for the ESPPRC on the well-known Solomon’s test bed for the VRPTW.
Keywords: vehicle routing; shortest path problem; column generation; vehicle routing problem with time windows (search for similar items in EconPapers)
Date: 2016
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (16)
Downloads: (external link)
http://dx.doi.org/10.1287/trsc.2014.0582 (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:50:y:2016:i:1:p:348-357
Access Statistics for this article
More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().