Author: José de Jesús Cáceres Cruz
Programme: Doctoral Programme on the Information and Knowledge Society
Language: English
Supervisor: Dr Ángel Alejandro Juan Pérez
Faculty / Institute: Internet Interdisciplinary Institute (IN3), Faculty of Computer Science, Multimedia and Telecommunications
Subjects: Computer Science, Analysis, General Theory of Combined Analysis, Graph Theory, Engineering. Technology, Land Transport Engineering, Transport Vehicles Engineering
Key words: Rich vehicle routing problems, Biased randomized heuristics, Metaheuristics, Real-life applications, Optimization, Logistics
Area of knowledge: Computation Science and Artificial Intelligence
+ Link to project
Summary
The vehicle routing problem (VRP) is a well-known domain in the 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 and distributed computing techniques, and constraint programming. The proposed approaches are tested for solving some variants of VRPs, 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 centred 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.