The Resource constrained shortest path problem implemented in a lazy functional language

Pieter H. Hartel, Hugh Glaser

    Research output: Contribution to journalArticleAcademicpeer-review

    806 Downloads (Pure)

    Abstract

    The resource constrained shortest path problem is an NP-hard problem for which many ingenious algorithms have been developed. These algorithms are usually implemented in Fortran or another imperative programming language. We have implemented some of the simpler algorithms in a lazy functional language. Benefits accrue in the software engineering of the implementations. Our implementations have been applied to a standard benchmark of data files, which is available from the Operational Research Library of Imperial College, London. The performance of the lazy functional implementations, even with the comparatively simple algorithms that we have used, is competitive with a reference Fortran implementation.
    Original languageUndefined
    Pages (from-to)29-45
    Number of pages17
    JournalJournal of functional programming
    Volume1
    Issue number1
    DOIs
    Publication statusPublished - Jan 1996

    Keywords

    • IR-55706
    • EWI-1108

    Cite this