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

Line Blander Reinhardt, David Pisinger

    Research output: Contribution to journalJournal articleResearchpeer-review


    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 and Operations Research
    Issue number3
    Pages (from-to)605-616
    Publication statusPublished - 2011


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


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

    Cite this