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

Line Reinhardt, David Pisinger

Publikation: Bidrag til tidsskriftTidsskriftartikelForskningpeer 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
BogserieSeries on Computers and Operations Research
Udgave nummer3
Sider (fra-til)605-616
Antal sider12
StatusUdgivet - mar. 2011
Udgivet eksterntJa

Citer dette