• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesTypeThis CollectionBy Issue DateAuthorsTitlesType

My Account

LoginRegister

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors
Thumbnail - Request a copy

Bidirectional versus Unidirectional Heuristic Search for Multiojective Optimization in State Space Graphs

Galand, Lucie; Ismaili, Anisse; Perny, Patrice; Spanjaard, Olivier (2013), Bidirectional versus Unidirectional Heuristic Search for Multiojective Optimization in State Space Graphs, 22nd International Conference on Multiple Criteria Decision Making (MCDM 2013), Malaga, SPAIN

Type
Communication / Conférence
Date
2013
Conference title
22nd International Conference on Multiple Criteria Decision Making (MCDM 2013)
Conference city
Malaga
Conference country
SPAIN
Metadata
Show full item record
Author(s)
Galand, Lucie
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Ismaili, Anisse
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Perny, Patrice

Spanjaard, Olivier
Abstract (EN)
Multiobjective heuristic search in state space graphs generally aims at determining theexact set of Pareto-optimal cost vectors associated to solution paths or an approximationof this Pareto set. When a preference model is available under the form of scalarizingfunction f, the search effort merely focuses on the direct determination of an f-optimaltradeoff within the Pareto-set. The solution algorithms proposed in this area rely on uni-directional approaches that develop a front of Pareto-optimal labels attached to subpathsfrom the initial node s to the goal nodes. When there is a single goal node t, explicitlyknown, and when search operators are reversible, a bidirectional search approach is possi-ble, interleaving and interacting searches, forward from s and backward from t. Althoughthe respective advantages of unidirectional approaches versus bidirectionnal approacheshave been widely discussed in the singleobjective case, they have not been investigated inthe setting of multiobjective search. The aim of this paper is to propose a first implemen-tation of multiobjective bidirectional heuristic search and to empirically assess his valuecompared to unidirectional search. Our comparison concerns both the determination ofthe entire Pareto set and the determination of OWA-optimal tradeoffs within the Paretoset. We provide results of numerical tests performed on random instances of path-planningproblems, both in terms of number of nodes expanded and in terms of computation times.
Subjects / Keywords
Multiojective Optimization; Bidirectional Heuristic Search; Multi-ObjectiveShortest Path Problem; OWA Operator.

Related items

Showing items related by title and author.

  • Thumbnail
    Bidirectional Preference-based Search for Multiobjective State Space Graph Problems 
    Galand, Lucie; Ismaili, Anisse; Perny, Patrice; Spanjaard, Olivier (2013) Communication / Conférence
  • Thumbnail
    Search for Compromise Solutions in Multiobjective State Space Graphs 
    Galand, Lucie; Perny, Patrice (2006) Communication / Conférence
  • Thumbnail
    OWA-Based Search in State Space Graphs with Multiple Cost Functions 
    Galand, Lucie; Spanjaard, Olivier (2007) Communication / Conférence
  • Thumbnail
    A Branch and Bound Algorithm for Choquet Optimization in Multicriteria Problems 
    Galand, Lucie; Perny, Patrice; Spanjaard, Olivier (2010) Communication / Conférence
  • Thumbnail
    Choquet-based optimisation in multiobjective shortest path and spanning tree problems 
    Galand, Lucie; Perny, Patrice; Spanjaard, Olivier (2010) Article accepté pour publication ou publié
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Phone: 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo