Scandinavian Working Papers in Economics

Discussion Papers on Economics,
University of Southern Denmark, Department of Economics

No 17/2013: Exploiting Set-Based Structures to Accelerate Dynamic Programming Algorithms for the Elementary Shortest Path Problem with Resource Constraints

Troels Martin Range ()
Additional contact information
Troels Martin Range: Department of Business and Economics, Postal: University of Southern Denmark, Campusvej 55, DK-5230 Odense M, Denmark

Abstract: In this paper we consider a label-setting dynamic-programming algorithm for the Elementary Shortest Path Problem with Resource Constraints (ESPPRC). We use a pseudo resource to guarantee that labels are permanent. We observe that storing the states based on the subset of nodes visited by the associated path can improve the performance of the algorithm significantly. To this end we use a variant of a prefix tree to store the states and show by computational experiments that the performance of the dynamic programming algorithm is improved significantly when the number of undominated states is large.

Keywords: Elementary shortest path problem; resource constraints; dynamic programming; prefix tree

JEL-codes: C61

23 pages, October 17, 2013

Full text files 

dpbe17_2013.pdf PDF-file Full text

Download statistics

Questions (including download problems) about the papers in this series should be directed to Astrid Holm Nielsen ()
Report other problems with accessing this service to Sune Karlsson ().

This page generated on 2024-02-05 17:13:32.