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

Line Blander Reinhardt, David Pisinger

    Research output: Contribution to journalJournal articleResearchpeer-review

    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 to 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
    JournalComputers & Operations Research
    Volume38
    Issue number3
    Pages (from-to)605-616
    ISSN0305-0548
    DOIs
    Publication statusPublished - 2011

    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