• Título:  HYBRID ALGORITHMS FOR SOLVING ROUTING PROBLEMS
• Autor:  Guimarans Serrano, Daniel
• Universidad:  Universidad Autónoma de Barcelona
• Departamento:  TELECOMUNIACION E INGENIERIA DE SISTEMAS
• Fecha de Lectura:  27/07/2012
• Programa de doctorado:  Informática Industrial. Técnicas avanzadas de produccion
• Dirección: 
  • RIERA TERRÉN, DANIEL (CODIRECTOR)
  • RAMOS GONZÁLEZ, JUAN JOSE (CODIRECTOR)
• Tribunal: 
  • Piera Eroles, Miquel Angel  (PRESIDENTE)
  • Gavanelli, Marco (SECRETARIO)
  • Hirsch, Patrick (VOCAL)
• Descriptores: 
  • INVESTIGACION OPERATIVA
  • INTELIGENCIA ARTIFICIAL
  • HEURISTICA
• Localización:  BIBLIOTECA DE COMUNICACIÓN Y HEMEROTECA GENERAL UAB
• 2012guimahybri.pdf
• Resumen:
  An important component of many distribution systems is routing vehicles to serve customers. The Vehicle Routing Problem (VRP) provides a theoretical framework for approaching this class of logistics problems dealing with physical distribution. Because of its complexity and applicability, this class of logistics problems is among the most popular research areas in combinatorial optimization. This PhD. Thesis is aimed to introduce three different yet related hybrid methodologies to solve the VRP. These methodologies have been especially designed for being flexible in the sense that they can be used, with minor adaptations, for solving different variants of the VRP present in industrial application cases. In the three methodologies described in this work, different technologies are used to achieve the desired flexibility, efficiency, and robustness. Constraint Programming (CP) has been chosen as the modeling paradigm to describe the main constraints involved in the VRP. CP provides the pursued flexibility for the three methodologies, since adding side constraints present in most real application cases becomes a modeling issue and does not affect the search algorithm definition. In the first two hybrid methodologies, the CP model is used to check solution's feasibility during search. The third methodology presents a richer model for the VRP capable of tackling different problem variants. In this case, the search is performed and controlled from a CP perspective. Lagrangian Relaxation (LR) and a probabilistic version of the Clarke and Wright Savings (CWS) heuristic are used for specific purposes within the proposed methodologies. The former is used for minimizing the total traveled distance and the latter to provide a good initial solution. Both methods provide an efficient approach to the respectively faced problems. Moreover, the use of LR permits reducing the computational complexity of the performed local search processes and therefore reduces the required computational time to solve the VRP. All methodologies are based on the so-called Variable Neighborhood Search (VNS) metaheuristic. The VNS is formed by a family of algorithms that exploits systematically the idea of neighborhood changes both in the search phase to find a local minimum, and in perturbation phase, to escape from the corresponding valley. Although it is an extended method, there are few examples of its application to the VRP. However, interesting results have been obtained even applying the simplest VNS algorithms to this problem. The present thesis is aimed to contribute to the current research on the application of the VNS metaheuristic to the VRP. It has been chosen as the framework where the mentioned techniques are embedded. Hence, the metaheuristic is used to guide the search, while the desired efficiency is provided by the composing methods. On the other hand, using CP as the modeling paradigm provides the required flexibility. This characteristic is enhanced in the last described methodology. In this case, the CP search is guided by a combination of the VNS and the Large Neighborhood Search (LNS) metaheuristics. This methodology represents an initial approach for tackling efficiently more complex and richer VRP, similar to real application cases.