Multi-objective and multi-constrained non-additive shortest path problems

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 thi...

Full description

Saved in:
Bibliographic Details
Published in:Computers & operations research 2011-03, Vol.38 (3), p.605-616
Main Authors: Reinhardt, Line Blander, Pisinger, David
Format: Article
Language:English
Subjects:
Applied sciences
Criteria
Decision theory. Utility theory
Dominance
Dynamic programming
Exact sciences and technology
Mathematical programming
Multi objective programming
Multiple objective
Non-additive objective
Operational research and scientific management
Operational research. Management science
Operations research
Optimization
Shortest path problem
Shortest-path problems
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0305-0548
1873-765X
DOI:10.1016/j.cor.2010.08.003