Algorithms for Variants of Routing Problems

Contreras Bolton, Carlos Emilio (2019) Algorithms for Variants of Routing Problems, [Dissertation thesis], Alma Mater Studiorum Università di Bologna. Dottorato di ricerca in Ingegneria biomedica, elettrica e dei sistemi, 31 Ciclo. DOI 10.6092/unibo/amsdottorato/8173.
Documenti full-text disponibili:
[img] Documento PDF (English) - Richiede un lettore di PDF come Xpdf o Adobe Acrobat Reader
Disponibile con Licenza: Creative Commons Attribution Non-commercial Share Alike 3.0 (CC BY-NC-SA 3.0) .
Download (781kB)


In this thesis, we propose mathematical optimization models and algorithms for variants of routing problems. The first contribution consists of models and algorithms for the Traveling Salesman Problem with Time-dependent Service times (TSP-TS). We propose a new Mixed Integer Programming model and develop a multi-operator genetic algorithm and two Branch-and-Cut methods, based on the proposed model. The algorithms are tested on benchmark symmetric and asymmetric instances from the literature, and compared with an existing approach, showing the effectiveness of the proposed algorithms. The second work concerns the Pollution Traveling Salesman Problem (PTSP). We present a Mixed Integer Programming model for the PTSP and two mataheuristic algorithms: an Iterated Local Search algorithm and a Multi-operator Genetic algorithm. We performed extensive computational experiments on benchmark instances. The last contribution considers a rich version of the Waste Collection Problem (WCP) with multiple depots and stochastic demands using Horizontal Cooperation strategies. We developed a hybrid algorithm combining metaheuristics with simulation. We tested the proposed algorithm on a set of large-sized WCP instances in non-cooperative scenarios and cooperative scenarios.

Tipologia del documento
Tesi di dottorato
Contreras Bolton, Carlos Emilio
Dottorato di ricerca
Settore disciplinare
Settore concorsuale
Parole chiave
Travelling Salesman Problem, Multi-depot Vehicle Routing Problem, Time-dependent Service times, Pollution Traveling Salesman Problem, Waste Collection Management, Mathematical Model, Branch-and-Cut Algorithm, Genetic Algorithm, Iterated Local Search, Simheuristics
Data di discussione
28 Marzo 2019

Altri metadati

Statistica sui download

Gestione del documento: Visualizza la tesi