Fugaro, Serena (2021) Optimizing and Reoptimizing: tackling static and dynamic combinatorial problems. [Tesi di dottorato]

Preview

Text Serena_Fugaro_33.pdf Download (3MB) | Preview

[error in script] [error in script]

Item Type:	Tesi di dottorato
Resource language:	English
Title:	Optimizing and Reoptimizing: tackling static and dynamic combinatorial problems
Creators:	Creators Email Fugaro, Serena serena.fugaro@unina.it
Date:	14 July 2021
Number of Pages:	181
Institution:	Università degli Studi di Napoli Federico II
Department:	Matematica e Applicazioni "Renato Caccioppoli"
Dottorato:	Matematica e applicazioni
Ciclo di dottorato:	33
Coordinatore del Corso di dottorato:	nome email Moscariello, Gioconda gmoscari@unina.it
Tutor:	nome email Festa, Paola UNSPECIFIED
Date:	14 July 2021
Number of Pages:	181
Keywords:	Shortest Paths, Constrained Shortest Path, Additive Manufacturing Machine Scheduling, Meta-heuristic, Exact Method
Settori scientifico-disciplinari del MIUR:	Area 01 - Scienze matematiche e informatiche > MAT/09 - Ricerca operativa
Date Deposited:	20 Jul 2021 07:56
Last Modified:	07 Jun 2023 11:16
URI:	http://www.fedoa.unina.it/id/eprint/13815

Collection description

As suggested by the title, in this thesis both static and dynamic problems of Operations Research will be addressed by either designing new procedures or adapting well-known algorithmic schemes. Specifically, the first part of the thesis is devoted to the discussion of three variants of the widely studied Shortest Path Problem, one of which is defined on dynamic graphs. Namely, first the Reoptimization of Shortest Paths in case of multiple and generic cost changes is dealt with an exact algorithm whose performance is compared with Dijkstra's label setting procedure in order to detect which approach has to be preferred. Secondly, the k-Color Shortest Path Problem is tackled. It is a recent problem, defined on an edge-constrained graph, for which a Dynamic Programming algorithm is proposed here; its performance is compared with the state of the art solution approach, namely a Branch & Bound procedure. Finally, the Resource Constrained Clustered Shortest Path Tree Problem is presented. It is a newly defined problem for which both a mathematical model and a Branch & Price procedure are detailed here. Moreover, the performance of this solution approach is compared with that of CPLEX solver. Furthermore, in the first part of the thesis, also the Path Planning in Urban Air Mobility, is discussed by considering both the definition of the Free-Space Maps and the computation of the trajectories. For the former purpose, three different but correlated discretization methods are described; as for the latter, a two steps resolution, offline and online, of the resulting shortest path problems is performed. In addition, it is checked whether the reoptimization algorithm can be used in the online step. In the second part of this thesis, the recently studied Additive Manufacturing Machine Scheduling Problem with not identical machines is presented. Specifically, a Reinforcement Learning Iterated Local Search meta-heuristic featuring a Q-learning Variable Neighbourhood Search is described to solve this problem and its performance is compared with the one of CPLEX solver. It is worthwhile mentioning that, for each of the proposed approaches, a thorough experimentation is performed and each Chapter is equipped with a detailed analysis of the results in order to appraise the performance of the method and to detect its limits.

Downloads

Actions (login required)

View Item