Please use this identifier to cite or link to this item:
Title: Randomized Algorithms for Rich Vehicle Routing Problems: From a Specialized Approach to a Generic Methodology
Author: Cáceres Cruz, José de Jesús
Director: Juan Pérez, Ángel Alejandro
Riera Terrén, Daniel  
Others: Universitat Oberta de Catalunya. Internet Interdisciplinary Institute (IN3)
Keywords: rich vehicle routing problems
biased randomized heuristics
real-life applications
Issue Date: 22-Nov-2013
Publisher: Universitat Oberta de Catalunya. Internet Interdisciplinary Institute (IN3)
Abstract: The Vehicle Routing Problem (VRP) is a well known domain in optimization research community. Its different basic variants have been widely explored in the literature. Some studies have considered specific combinations of real-life constraints to define the emerging Rich VRP scopes. This work deals with the integration of heuristics, biased probability, simulation, parallel & distributed computing techniques, and constraint programming. The proposed approaches are tested for solving some variants of VRPs, namely, first, the deterministic families: Heterogeneous VRP (HVRP), Heterogeneous VRP with Variable cost (HVRP-V), Heterogeneous fleet VRP with Multi-trips (HVRPM), Asymmetric cost matrix VRP (AVRP), Heterogeneous fleet with Asymmetric cost matrix VRP (HAVRP), VRP with Time Windows (VRPTW), and Distance-Constrained VRP (DCVRP); second, the stochastic nature families: VRP with Stochastic Demands (VRPSD), and Inventory Routing Problem with Stochastic Demands (IRPSD). An extensive literature review is performed for all these variants, focusing on the main contributions of each work. A first approach proposes a biased-randomization of classical heuristics for solving the deterministic problems addressed here. A second approach is centered on the combination of randomized heuristics with simulation (Simheuristics) to be applied on the commented stochastic problems. Finally, a third approach based on the joined work of randomized heuristics with constraint programming is proposed to solve several types of routing problems. The developed heuristic algorithms are tested in several benchmark instances --between these, two real-life case studies in Spain are considered-- and the results obtained are, on average, highly promising and useful for decision makers.
Language: English
Appears in Collections:Doctoral Thesis

Files in This Item:
File Description SizeFormat 
thesisJoseCaceres2013.pdf7.51 MBAdobe PDFView/Open

This item is licensed under a Creative Commons License Creative Commons