S-WoPEc
 
Scandinavian Working Papers in Economics
HomeAboutSeriesSubject/JEL codesAdvanced Search
Department of Business and Economics, University of Southern Denmark Discussion Papers of Business and Economics
Department of Business and Economics, University of Southern Denmark

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

Troels Martin Range ()

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; (follow links to similar papers)

JEL-Codes: C61; (follow links to similar papers)

23 pages, October 17, 2013

Before downloading any of the electronic versions below you should read our statement on copyright.
Download GhostScript for viewing Postscript files and the Acrobat Reader for viewing and printing pdf files.

Full text versions of the paper:

%7BF94B03F2-40D0-4E96-AD02-86C70DD2B393%7Ddpbe17_2013.pdf    PDF-file
Download Statistics

Questions (including download problems) about the papers in this series should be directed to Lene Holbęk ()
Report other problems with accessing this service to Sune Karlsson () or Helena Lundin ().

Programing by
Design by Joachim Ekebom

Handle: RePEc:hhs:sdueko:2013_017 This page was generated on 2014-12-14 19:26:44