Formulations and Algorithms for Routing Problems

Salari, Majid (2010) Formulations and Algorithms for Routing Problems, [Dissertation thesis], Alma Mater Studiorum Università di Bologna. Dottorato di ricerca in Automatica e ricerca operativa, 22 Ciclo. DOI 10.6092/unibo/amsdottorato/2700.
Documenti full-text disponibili:
Documento PDF (English) - Richiede un lettore di PDF come Xpdf o Adobe Acrobat Reader
Download (585kB) | Anteprima


Combinatorial Optimization is a branch of optimization that deals with the problems where the set of feasible solutions is discrete. Routing problem is a well studied branch of Combinatorial Optimization that concerns the process of deciding the best way of visiting the nodes (customers) in a network. Routing problems appear in many real world applications including: Transportation, Telephone or Electronic data Networks. During the years, many solution procedures have been introduced for the solution of different Routing problems. Some of them are based on exact approaches to solve the problems to optimality and some others are based on heuristic or metaheuristic search to find optimal or near optimal solutions. There is also a less studied method, which combines both heuristic and exact approaches to face different problems including those in the Combinatorial Optimization area. The aim of this dissertation is to develop some solution procedures based on the combination of heuristic and Integer Linear Programming (ILP) techniques for some important problems in Routing Optimization. In this approach, given an initial feasible solution to be possibly improved, the method follows a destruct-and-repair paradigm, where the given solution is randomly destroyed (i.e., customers are removed in a random way) and repaired by solving an ILP model, in an attempt to find a new improved solution.

Tipologia del documento
Tesi di dottorato
Salari, Majid
Dottorato di ricerca
Scuola di dottorato
Scienze e ingegneria dell'informazione
Settore disciplinare
Settore concorsuale
Parole chiave
Integer Linear Programming Vehicle Routing Problem Network Optimization Column Generation Metaheuristics Local Search Heuristics
Data di discussione
30 Marzo 2010

Altri metadati

Statistica sui download

Gestione del documento: Visualizza la tesi