Multi-Objective and Multi-Constrained Non-Additive Shortest Path Problems

Line Blander Reinhardt, David Pisinger

    Research output: Book/ReportReportResearch

    487 Downloads (Pure)

    Abstract

    Shortest path problems appear as subproblems in numerous optimization problems. In most papers concerning multiple objective shortest path problems, additivity of the objective is a de-facto assumption, but in many real-life situations objectives and criteria, can be non-additive. The purpose of this paper is to give a general framework for dominance tests for problems involving a number of non-additive criteria. These dominance tests can help eliminate paths in a dynamic programming framework when using multiple objectives. Results on real-life multi-objective problems containing non-additive criteria are reported. We show that in many cases the framework can be used to efficiently reduce the number of generated paths.
    Original languageEnglish
    Place of PublicationKgs. Lyngby
    PublisherDTU Management
    Number of pages22
    ISBN (Print)978-87-90855-61-1
    Publication statusPublished - 2009
    SeriesDTU Management 2009
    Number16

    Keywords

    • non-additive objective
    • shortest path problem
    • dynamic programming
    • multi objective programming

    Fingerprint Dive into the research topics of 'Multi-Objective and Multi-Constrained Non-Additive Shortest Path Problems'. Together they form a unique fingerprint.

    Cite this