Back to Search
Start Over
An Exact Algorithm for the Elementary Shortest Path Problem with Resource Constraints.
- Source :
-
Transportation Science . Feb2016, Vol. 50 Issue 1, p248-257. 10p. - Publication Year :
- 2016
-
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. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 00411655
- Volume :
- 50
- Issue :
- 1
- Database :
- Academic Search Index
- Journal :
- Transportation Science
- Publication Type :
- Academic Journal
- Accession number :
- 113938340
- Full Text :
- https://doi.org/10.1287/trsc.2014.0582