Bi-objective robust optimisation

doi:10.1016/j.ejor.2016.01.015

European Journal of Operational Research

Volume 252, Issue 2, 16 July 2016, Pages 418-431

https://doi.org/10.1016/j.ejor.2016.01.015 Get rights and content

Highlights

•
Study bi-objective robust optimsation for problems with one uncertain objective.
•
Introduce and analyse four different robustness concepts.
•
Focus on proposing approach to derive a meaningful robust Pareto front.
•
Develop algorithm to compute robust solutions for discrete optimisation problems.
•
Application of concepts to aircraft route guidance and hazardous materials routing problems.

Abstract

It is important, in practice, to find robust solutions to optimisation problems. This issue has been the subject of extensive research focusing on single-objective problems. Recently, researchers also acknowledged the need to find robust solutions to multi-objective problems and presented some first results on this topic. In this paper, we deal with bi-objective optimisation problems in which only one objective function is uncertain. The contribution of our paper is three-fold. Firstly, we introduce and analyse four different robustness concepts for bi-objective optimisation problems with one uncertain objective function, and we propose an approach for defining a meaningful robust Pareto front for these types of problems. Secondly, we develop an algorithm for computing robust solutions with respect to these four concepts for the case of discrete optimisation problems. This algorithm works for finite and for polyhedral uncertainty sets using a transformation to a multi-objective (deterministic) optimisation problem and the recently published concept of Pareto robust optimal solutions (Iancu & Trichakis, 2014). Finally, we apply our algorithm to two real-world examples, namely aircraft route guidance and the shipping of hazardous materials, illustrating the four robustness concepts and their solutions in practical applications.

Introduction

Many real-world optimisation problems are modelled as bi- or multi-objective optimisation problems (MOP) acknowledging that many decisions are based on multiple conflicting objectives (Ehrgott, 2005). On the other hand, real-world optimisation problems often depend on uncertain parameters, such as weather conditions, uncertain processing times, or delays in public transportation systems. To deal with this uncertainty, different approaches such as stochastic optimisation (Birge & Louveaux, 1997) and robust optimisation (Ben-Tal, Ghaoui, & Nemirovski, 2009) have been developed.

As much attention has been given to both MOPs and robust optimisation, a natural next step is the combination of the two concepts. In this paper we analyse such a combination for bi-objective optimisation problems with one uncertain objective: $\min_{x \in X} z (x, ξ) : = (\begin{matrix} z_{1} (x) \\ z_{2} (x, ξ) \end{matrix}),$ where $X$ is the feasible set, the first objective is z₁ and the second uncertain objective is z₂(x, ξ) which depends on an uncertain parameter ξ, see Section 4. Such problems arise in many application areas, e.g., in the aircraft route guidance problem or when shipping hazardous materials; see Section 8 for details.

Section snippets

Related work

The need to combine robust and multi-objective optimisation has been recognised in the literature and has led to the development of different concepts of efficiency under uncertainty. This issue has been described recently in the survey by Ide and Schöbel (2016). Also see the overview given by Goberna, Jeyakumar, Li, and Vicente-Prez (2015). We review the relevant parts.

There are two rather straightforward ways for defining robust efficient (RE) solutions for multi-objective optimisation. The

Background

In Section 4 we define a robust solution to an uncertain optimisation problem such as (1), i.e., we combine robust and multi-objective optimisation. Before doing so, we discuss basic concepts of both fields in Sections 3.1 and 3.2.

Problem definition

We consider an uncertain bi-objective optimisation problem $P$ where a solution x has to be chosen from a given set of feasible solutions $X$ . Every $x \in X$ is assigned an objective value $z_{1} (x) \in I R$ and a second objective value $z_{2} (x, ξ) \in I R$ which is uncertain, since the parameter ξ is not known. We assume that $ξ \in U$ for some uncertainty set $U$ which is a subset of some vector space.

In this paper we make the following assumptions:

•
$z_{1} : X \to I R$ is continuous,
•
$z_{2} : X \times U \to I R$ is continuous for every fixed $x \in X$ and for every

Extension to PRO RE solutions and related multi-objective problems

Iancu and Trichakis (2014) deal with single-objective robust optimisation problems and use the concept of efficiency to refine the definition of (single-objective) strict robustness. Their idea is as follows. The ‘traditional’ set of strictly RE solutions $X_{sc}^{RO}$ contains all solutions which minimise the objective value in the worst case; however, some of these solutions would not be considered reasonable in any practical setting. Consider a solution x which is not better than another solution y

An algorithm for bi-objective combinatorial optimisation problems with finite uncertainty set

We can use the insights gained in Observations 1 and 2 to compute the sets of flimsily, highly, strictly, and ε-representative lightly PRO RE solutions in two steps.

1.
Solve a deterministic MOP w.r.t. ζ and obtain a complete set of efficient solutions,
2.
Filter among the efficient solutions found in Step 1 for flimsily/highly/strictly/ε-representative lightly PRO RE solutions.

The applicability and efficiency of this approach depends on the algorithms available for the two steps. For the first step,

Bi-objective optimisation problems with polyhedral uncertainty sets

In this section we turn our attention to the second type of uncertainty set, namely to the case in which $U$ is a polytope, i.e., $\begin{matrix} U & = & c o n v {ξ^{1}, \dots, ξ^{N}} \\ = & {ξ : \exists α \in {[0, 1]}^{N} with \sum_{i = 1}^{N} α_{i} = 1 s.t. ξ = \sum_{i = 1}^{N} α_{i} ξ^{i}} . \end{matrix}$ Note that the assumption of a polyhedral uncertainty set is not unrealistic. As a special case it includes interval-based uncertainty which is (apart from finite uncertainty sets) probably the most considered case in uncertain single-objective optimisation (e.g. Bertsimas, Sim, 2004, Ben-Tal, Nemirovski, 2000).

Applications and experimental results

We present two real-world applications which are modelled as bi-objective robust optimisation problems with one uncertain objective.

Conclusions

We compare four different robustness concepts for bi-objective optimisation with one uncertain objective function and propose an algorithm for the most common case of finite or polyhedral uncertainty sets. From our experience with two real-world applications we conclude that robust efficient solutions to such problems can be computed in a reasonable time, and that different types of robust solutions can be identified. Comparing the four concepts, representative light robustness turns out to be

Acknowledgment

This research has been partially supported by the European Union Seventh Framework Programme (FP7-PEOPLE-2009-IRSES) under grant agreement no 246647 and by the New Zealand Government (grant 649378 v2) as part of the OptALI project. Furthermore, Andrea Raith has been partially supported by the Marsden Fund under grant number UOA1008, Marie Schmidt by grant SCHO 1140/3-2 of DFG, and Kenneth Kuhn by NASA grant NNA14AB47C.

References (44)

EhrgottM. et al.
Minmax robustness for multi-objective optimization problems
European Journal of Operational Research
(2014)
ErkutE. et al.
Hazardous materials transportation
GeorgievP. et al.
Robust aspects of solutions in deterministic multiple objective linear programming
European Journal of Operational Research
(2013)
GobernaM. et al.
Robust solutions to multi-objective linear programs with uncertain data
European Journal of Operational Research
(2015)
Müller-HannemannM. et al.
On the cardinality of the Pareto set in bicriteria shortest path problems
Annals of Operations Research
(2006)
SoysterA.
Convex programming with set-inclusive constraints and applications to inexact linear programming
Operations Research
(1973)
Bar-Gera, H. last visited june 2013. transportation network test problems. Online....
BarricoC. et al.
Robustness analysis in multi-objective optimization using a degree of robustness concept
IEEE congress on evolutionary computation. CEC 2006.
(2006)
BellG.
Mixed route strategies for the risk-averse shipment of hazardous materials
Networks and Spatial Economics
(2006)
Ben-TalA. et al.
Robust Optimization
(2009)

Ben-TalA. et al.

Robust convex optimization

Mathematics of Operations Research

(1998)

Ben-TalA. et al.

Robust solutions of linear programming problems contaminated with uncertain data

Mathematical Programming A

(2000)

BertsimasD. et al.

The price of robustness

Operations Research

(2004)

BirgeJ. et al.

Introduction to Stochastic Programming

(1997)

BitranG.R.

Linear multiple objective problems with interval coefficients

Management Science

(1980)

BrankeJ.

Creating robust solutions by means of evolutionary algorithms

ChenW. et al.

Including robustness in multi-criteria optimization for intensity-modulated proton therapy

Physics in Medicine and Biology

(2012)

DebK. et al.

Introducing robustness in multi-objective optimization

Evolutionary Computation

(2006)

DebK. et al.

Searching for robust pareto-optimal solutions in multi-objective optimization

DoolittleE. et al.

A robust multiobjective optimization problem with application to internet routing

Tech. Rep. R2012-11-DKW, Clemson University

(2012)

EhrgottM.

Multicriteria optimization

(2005)

EhrgottM. et al.

Multiobjective combinatorial optimization – theory, methodology, and applications

Cited by (48)

Smart charging and discharging of electric vehicles based on multi-objective robust optimization in smart cities
2023, Applied Energy
The combination of low-carbon electricity and electric vehicles brings considerable economic and environmental benefits but also introduces challenges due to the complexity and uncertainty of system synergies in smart cities. To fully exploit the advantages of photovoltaic power generation and electric vehicles and to release the potential of electric vehicles as distributed energy storage facilities, this paper develops a multi-objective robust optimization framework that accounts for the benefits of multiple parties of smart charging and discharging systems and depicts a bounded uncertainty set based on partial statistical information from real data. The original model is scalarized and linearized using efficient methods such as max-ordering scalarization and the robust augmented weighted Tchebycheff to facilitate the solution. Moreover, a smart charging and discharging scheduling strategy based on a convergent demand response strategy is proposed to achieve better demand-side management. A case study, based on real data from Car2go and the solar radiation intensity in Portland, Oregon, shows that (1) The methodological framework effectively addresses the smart scheduling issue that considers the interests of multiple parties in complex systems with uncertainty, in contrast to conventional methods. (2) The designed convergent demand response strategy promotes photovoltaic power generation and charging demand synergy and achieves regulation effects such as peak shaving and valley filling. (3) The proposed method and strategy yield good results in multiple aspects, such as charging costs, load regulation, and clean energy utilization, while enhancing the economic and environmental benefits.
Bi-objective scenario-guided swarm intelligent algorithms based on reinforcement learning for robust unrelated parallel machines scheduling with setup times
2023, Swarm and Evolutionary Computation
This paper addresses an uncertain unrelated parallel machine scheduling problem (UPMSP) with setup times, which is referred to the scenario UPMSP since uncertain processing times are described by a set of discrete scenarios. The bi-objective robust optimization formulation is established. Two objectives are to minimize the mean makespan and the worst-case makespan across all scenarios, which reflect solution optimality and solution robustness respectively. The contribution of this paper is three-fold. First, we propose the bi-objective robust optimization formulation under discrete scenarios for uncertain UPMSP. Second, two versions of swarm intelligent algorithms are developed by combining fruit fly optimization algorithm (FOA) framework and scenario-guided local search, which are performed based on two problem-specific neighborhood structures. The learning-scenario neighborhood structure is constructed by selecting single scenario using reinforcement learning. The united-scenario neighborhood structure is constructed by collecting all discrete scenarios. Third, an experiment was conducted to compare two developed algorithms with the state-of-the-art alternative algorithms. The computational results show that the developed algorithms are identically better than possible alternatives in terms of multi-objective metrics. Moreover, it is shown that the FOA algorithm with learning-scenario-neighborhood smell search is advantageous for the discussed problem.
A pareto-based multi-objective network design approach for mitigating the risk of hazardous materials transportation
2022, Process Safety and Environmental Protection
Hazardous materials (HazMat) transportation is one of the indispensable links in the chemical process industry and is closely related to safety, security, and environmental concerns. HazMat transportation routing is a major proactive risk management measure. Most related studies focus on diminishing the transportation risk for one single HazMat shipment. This work addresses a global perspective on the problem where the correlations of multiple simultaneous HazMat shipments are considered. A multi-objective transportation network design model is defined to optimize the objectives of the transportation risk and the transportation cost. A well-designed Pareto-based hybrid heuristic algorithm is proposed for model solving, which integrates a linear decomposition procedure for initial population construction, a Pareto-based scatter search procedure for population evolution, and a variable neighborhood search procedure for solution improvement. Computational results indicate that the proposed algorithm is competitive in solving large-scale instances since it is able to strike a great balance between effectiveness and efficiency. The detailed solution analysis shows that the proposed approach can effectively coordinate multiple simultaneous HazMat transportation processes. Moreover, we find that performing multiple short-distance shipments would significantly reduce the total transportation risk, but results in the higher transportation cost. This work can provide a set of Pareto optimal transportation networks for different industrial application scenarios to achieve the trade-off between economic and safety.
Multiobjective optimization under uncertainty: A multiobjective robust (relative) regret approach
2022, European Journal of Operational Research
Consider a multiobjective decision problem with uncertainty in the objective functions, given as a set of scenarios. In the single-criterion case, robust optimization methodology helps to identify solutions which remain feasible and of good quality for all possible scenarios. A well-known alternative method in the single-objective case is to compare possible decisions under uncertainty with the optimal decision with the benefit of hindsight, i.e. to minimize the (possibly scaled) regret of not having chosen the optimal decision. In this contribution, we extend the concept of regret from the single-objective case to the multiobjective setting and introduce a proper definition of multivariate (robust) (relative) regret. In contrast to the few existing ideas that mix scalarization and optimization, we clearly separate the modelling of multiobjective (robust) regret from its numerical solution. Moreover, our approach is not limited to a finite uncertainty set or interval uncertainty and furthermore, computations or at least approximations remain tractable in several important special cases. We illustrate all approaches based on a biobjective shortest path problem under uncertainty.
Multi-scenario multi-objective robust optimization under deep uncertainty: A posteriori approach
2021, Environmental Modelling and Software
This paper proposes a novel optimization approach for multi-scenario multi-objective robust decision making, as well as an alternative way for scenario discovery and identifying vulnerable scenarios even before any solution generation. To demonstrate and test the novel approach, we use the classic shallow lake problem. We compare the results obtained with the novel approach to those obtained with previously used approaches. We show that the novel approach guarantees the feasibility and robust efficiency of the produced solutions under all selected scenarios, while decreasing computation cost, addresses the scenario-dependency issues, and enables the decision-makers to explore the trade-off between optimality/feasibility in any selected scenario and robustness across a broader range of scenarios. We also find that the lake problem is ill-suited for reflecting trade-offs in robust performance over the set of scenarios and Pareto optimality in any specific scenario, highlighting the need for novel benchmark problems to properly evaluate novel approaches.
Analysis of different risk models for the hazardous materials vehicle routing problem in urban areas
2021, Cleaner Environmental Systems
The distribution of hazardous materials in urban areas is an important tactical and strategic decision problem. Reducing the transportation risk and increasing the traffic safety is also an important indicator for a sustainable transportation. For the last four decades, a multitude of approaches for risk assessment and modelling have been proposed. However, the majority of these approaches are focusing on different adaptations of shortest path problems. Risk modelling for routing and distributions problems, like the vehicle routing problem (VRP) have received far less attention, especially when the vehicle load is varying during a trip. This paper investigates how different factors are influencing the risk values and the outcomes of the hazardous materials vehicle routing problem (HMVRP). As foundation for the HMVRP, the path generation between the customer and the depot nodes in realistic urban road networks is considered. The influence of the fleet size is investigated. Different risk models are compared, with a special focus on the comparison of classical load-independent risk models with load-dependent risk models. Additionally, the tradeoff between risk minimization and the minimization of travelled distance is investigated. The results show, that these factors can have strong impact on the outcomes and lead to different “optimal” solutions.

View all citing articles on Scopus

View full text

Discrete OptimizationBi-objective robust optimisation

Highlights

Abstract

Introduction

Section snippets

Related work

Background

Problem definition

Extension to PRO RE solutions and related multi-objective problems

An algorithm for bi-objective combinatorial optimisation problems with finite uncertainty set

Bi-objective optimisation problems with polyhedral uncertainty sets

Applications and experimental results

Conclusions

Acknowledgment

European Journal of Operational Research

European Journal of Operational Research

European Journal of Operational Research

Annals of Operations Research

Operations Research

Robustness analysis in multi-objective optimization using a degree of robustness concept

IEEE congress on evolutionary computation. CEC 2006.

Mixed route strategies for the risk-averse shipment of hazardous materials

Networks and Spatial Economics

Robust Optimization

Robust convex optimization

Mathematics of Operations Research

Robust solutions of linear programming problems contaminated with uncertain data

Mathematical Programming A

The price of robustness

Operations Research

Introduction to Stochastic Programming

Linear multiple objective problems with interval coefficients

Management Science

Creating robust solutions by means of evolutionary algorithms

Including robustness in multi-criteria optimization for intensity-modulated proton therapy

Physics in Medicine and Biology

Introducing robustness in multi-objective optimization

Evolutionary Computation

Searching for robust pareto-optimal solutions in multi-objective optimization

A robust multiobjective optimization problem with application to internet routing

Tech. Rep. R2012-11-DKW, Clemson University

Multicriteria optimization

Multiobjective combinatorial optimization – theory, methodology, and applications

Discrete Optimization
Bi-objective robust optimisation