JavaScript is disabled for your browser. Some features of this site may not work without it.

    Listar

    Todo RIUMAComunidades & ColeccionesPor fecha de publicaciónAutoresTítulosMateriasTipo de publicaciónCentrosEsta colecciónPor fecha de publicaciónAutoresTítulosMateriasTipo de publicaciónCentros

    Mi cuenta

    AccederRegistro

    Estadísticas

    Ver Estadísticas de uso

    DE INTERÉS

    Datos de investigaciónPolítica institucional UMAPolítica de RIUMAPolitica de datos de investigación en RIUMASHERPA/RoMEODulcinea
    Preguntas frecuentesManual de usoDerechos de autorContacto/Sugerencias
    Ver ítem 
    •   RIUMA Principal
    • Investigación
    • Lenguajes y Ciencias de la Computación - (LCC)
    • LCC - Tesis
    • Ver ítem
    •   RIUMA Principal
    • Investigación
    • Lenguajes y Ciencias de la Computación - (LCC)
    • LCC - Tesis
    • Ver ítem

    New Techniques and Algorithms for Multiobjective and Lexicographic Goal-Based Shortest Path Problems

    • Autor
      Pulido Arrebola, Francisco Javier
    • Director/es
      Mandow-Andaluz, LorenzoAutoridad Universidad de Málaga
    • Fecha
      2015
    • Editorial/Editor
      Servicio de Publicaciones y Divulgación Científica
    • Departamento
      Lenguajes y Ciencias de la Computación
    • Palabras clave
      Optimización combinatoria - Tesis doctorales; Inteligencia artificial - Tesis doctorales
    • Resumen
      Shortest Path Problems (SPP) are one of the most extensively studied problems in the fields of Artificial Intelligence (AI) and Operations Research (OR). It consists in finding the shortest path between two given nodes in a graph such that the sum of the weights of its constituent arcs is minimized. However, real life problems frequently involve the consideration of multiple, and often conflicting, criteria. When multiple objectives must be simultaneously optimized, the concept of a single optimal solution is no longer valid. Instead, a set of efficient or Pareto-optimal solutions define the optimal trade-off between the objectives under consideration. The Multicriteria Search Problem (MSP), or Multiobjective Shortest Path Problem, is the natural extension to the SPP when more than one criterion are considered. The MSP is computationally harder than the single objective one. The number of label expansions can grow exponentially with solution depth, even for the two objective case. However, with the assumption of bounded integer costs and a fixed number of objectives the problem becomes tractable for polynomially sized graphs. A wide variety of practical application in different fields can be identified for the MSP, like robot path planning, hazardous material transportation, route planning, optimization of public transportation, QoS in networks, or routing in multimedia networks. Goal programming is one of the most successful Multicriteria Decision Making (MCDM) techniques used in Multicriteria Optimization. In this thesis we explore one of its variants in the MSP. Thus, we aim to solve the Multicriteria Search Problem with lexicographic goal-based preferences. To do so, we build on previous work on algorithm NAMOA*, a successful extension of the A* algorithm to the multiobjective case. More precisely, we provide a new algorithm called LEXGO*, an exact label-setting algorithm that returns the subset of Pareto-optimal paths that satisfy a set of lexicographic goals, or the subset that minimizes deviation from goals if these cannot be fully satisfied. Moreover, LEXGO* is proved to be admissible and expands only a subset of the labels expanded by an optimal algorithm like NAMOA*, which performs a full Multiobjective Search. Since time rather than memory is the limiting factor in the performance of multicriteria search algorithms, we also propose a new technique called t-discarding to speed up dominance checks in the process of discarding new alternatives during the search. The application of t-discarding to the algorithms studied previously, NAMOA* and LEXGO*, leads to the introduction of two new time-efficient algorithms named NAMOA*dr and LEXGO*dr , respectively. All the algorithmic alternatives are tested in two scenarios, random grids and realistic road maps problems. The experimental evaluation shows the effectiveness of LEXGO* in both benchmarks, as well as the dramatic reductions of time requirements experienced by the t-discarding versions of the algorithms, with respect to the ones with traditional pruning.
    • URI
      http://hdl.handle.net/10630/10204
    • Compartir
      RefworksMendeley
    Mostrar el registro completo del ítem
    Ficheros
    TD_Pulido_Arrebola.pdf (8.878Mb)
    Colecciones
    • LCC - Tesis

    Estadísticas

    Ver Estadísticas de uso
    Academic Search
    Buscar en Dimension
    REPOSITORIO INSTITUCIONAL UNIVERSIDAD DE MÁLAGA
    REPOSITORIO INSTITUCIONAL UNIVERSIDAD DE MÁLAGA
     

     

    REPOSITORIO INSTITUCIONAL UNIVERSIDAD DE MÁLAGA
    REPOSITORIO INSTITUCIONAL UNIVERSIDAD DE MÁLAGA