Tesis Doctoral

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

Esta página web contiene la documentación de la tesis titulada "New Techniques and Algorithms for Multiobjective and Lexicographic Goal-Based Shortest Path Problems", presentada por el doctorando Francisco Javier Pulido Arrebola y dirigida por el Doctor Lawrence Mandow Andaluz para optar al grado académico de Doctor en el Programa de Doctorado en Ingeniería del Software e Inteligencia Artificial, Departamento de Lenguajes y Ciencias de la Computación, E.T.S. de Ingeniería Informática. Universidad de Málaga

Documentación

Publicaciones

A continuación se enlazan las publicaciones que avalan la tesis y un resumen de cada una de ellas:

Pulido, F. J., Mandow, L., & Pérez de la Cruz, J. (2014). Multiobjective shortest path problems with lexicographic goal-based preferences. European Journal of Operational Research, 239(1), 89–101.

Multiobjective shortest path problems are computationally harder than single objective ones. In particular, execution time is an important limiting factor in exact multiobjective search algorithms. This paper explores the possibility of improving search performance in those cases where the interesting portion of the Pareto front can be initially bounded. We introduce a new 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. Formal proofs on the correctness of the algorithm are provided. We also show that the algorithm always explores a subset of the labels explored by a full Pareto search. The algorithm is evaluated over a set of problems with three objectives, showing a performance improvement of up to several orders of magnitude as goals become more restrictive.

Pulido, F. J., Mandow, L., & Pérez de la Cruz, J. (2015). Dimensionality reduction in multiobjective shortest path search. Computers & Operations Research. Vol 64, 60-70

One-to-one multiobjective search in graphs deals with the problem of finding all Pareto-optimal solution paths between given start and goal nodes according to a number of distinct noncommensurate objectives. The problem is inherently more complex than single objective graph search. Time requirements are dominated by the facts that: a) many different non-dominated labels may need to be explored for each node; b) each new label under consideration must be checked for dominance against various subsets of previously generated labels. This article describes how a dimensionality reduction technique can be applied to exact label-setting algorithms, reducing the number of dominance checks and allowing for much faster multiobjective search. The technique is applied to NAMOA*, a state of the art exact label-setting multiobjective search algorithm, achieving reductions in time requirements of more than an order of magnitude over problems in random grids and realistic road maps. Tests include problems with three, four, and five objectives.

Contacto