The elementary shortest path with resource constraints have commonly been solved with dynamic programming algorithms. Assuming an undirected graph, we present a compact formulation of this problem and a branch-and-cut algorithm to solve it. Two types of resources are discussed: a capacity and a fixed charge resource. The former is the subproblem of the capacitated vehicle routing problem and the latter is from the split delivery version. Computational results are presented and compared to dynamic programming algorithms.
|Publication status||Published - 2010|
|Event||24th European Conference on Operational Research - Lisbon, Portugal|
Duration: 11 Jul 2010 → 14 Jul 2010
Conference number: 24
|Conference||24th European Conference on Operational Research|
|Period||11/07/2010 → 14/07/2010|