Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
475737 | Computers & Operations Research | 2011 | 12 Pages |
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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computer Science (General)
Authors
Line Blander Reinhardt, David Pisinger,