  In this paper we develop two approaches to find minmax robust efficient
solutions for multi-objective combinatorial optimization problems with
cardinality-constrained uncertainty. First, we extend an algorithm of Bertsimas
and Sim (2003) for the single-objective problem to multi-objective
optimization. We propose also an enhancement to accelerate the algorithm, even
for the single-objective case, and we develop a faster version for special
multi-objective instances. Second, we introduce a deterministic multi-objective
problem with sum and bottleneck functions, which provides a superset of the
robust efficient solutions. Based on this, we develop a label setting algorithm
to solve the multi-objective uncertain shortest path problem. We compare both
approaches on instances of the multi-objective uncertain shortest path problem
originating from hazardous material transportation.
