Hybrid methodologies for symmetric and asymmetric vehicle routing problems

dc.contributor
Universitat Autònoma de Barcelona. Departament de Telecomunicació i Enginyeria de Sistemes
dc.contributor.author
Herrero Antón, Rosa
dc.date.accessioned
2016-04-06T13:50:03Z
dc.date.available
2016-04-06T13:50:03Z
dc.date.issued
2016-01-25
dc.identifier.isbn
9788449060595
cat
dc.identifier.uri
http://hdl.handle.net/10803/369581
dc.description.abstract
En las últimas décadas, la globalización ha impulsado la adaptación del sector del Transporte y la Logística a las nuevas demandas sociales. Al mismo tiempo, el transporte ha sido la columna vertebral de la globalización. Esta necesidad social crea consumidores ambiciosos que necesitan sus productos de forma rápida y a un precio asequible muchas veces sin ser conscientes de su origen, el transporte o los aspectos medioambientales, entre otros factores. Sin embargo, para satisfacer las demandas del cliente, es necesario encontrar el modo de transporte más barato, que significa la mejora de la logística del transporte de estos productos. Por lo tanto, estas demandas requieren un servicio cada vez más flexible para satisfacer las necesidades del cliente, y, además, las empresas quieren un transporte eficiente y productivo. Traveling Salesman Problems (TSP) and Vehicle Routing Problems (VRP) proporcionan el marco teórico para tratar este tipo de problemas logísticos relacionados con la distribución física de mercancías desde un almacén central hasta los clientes. Son dos de los problemas más desafiantes e investigados debido a su complejidad y aplicabilidad. El objetivo principal de esta tesis doctoral es la introducción de metodologías híbridas que integran varias técnicas para resolver de manera eficiente rich VRPs con restricciones realistas. Esta tesis comienza con problemas teóricos y evoluciona hacia escenarios más realistas abordando un total de seis problemas combinatorios relacionados con el transporte por carretera. Una metaheurística llamada Tailored Lagrangian Metaheuristic (TLM) se ha desarrollado para abordar el TSP. Está basa en la relajación de Lagrange que se utiliza para explotar la estructura del problema que reduce considerablemente su complejidad moviendo restricciones difíciles de satisfacer a la función objetivo, asociando una penalización en caso de que no se cumplen. La metaheurística desarrollada para el TSP se ha integrado en dos metodologías híbridas combinadas con Constraint Programming para hacer frente a problemas más complejos. En primer lugar, el Capacitated Vehicle Routing Problem (CVRP), cuyos los vehículos tienen limitaciones de capacidad de carga de las mercancías que deben ser entregadas, es abordado. En segundo lugar, se ha abordado un problema real, Home Health Care (HHC), del servicio de Salud en el municipio de Ferrara, Italia. Este consiste en la asignación de los tratamientos de los pacientes a las enfermeras que viajan a las casas de los pacientes. Investigaciones teóricas suelen asumir la simetría de los costes basados en la distancia de viajar de un lugar a otro y la existencia de una flota homogénea de vehículos con una misma capacidad. Esta tesis estudia diferentes variantes centradas en el impacto que causa la asimetría de los costes y la heterogeneidad de la flota. Para estos estudios, se abordan la versión con costes asimétricos del TSP y del CVRP -el Asymmetric Traveling Salesman Problem (ATSP) y el Asymmetric Capacitated Vehicle Routing Problem (ACVRP)- y la versión con flota heterogénea del ACVRP –el Asymmetric and Heterogeneous Vehicle Routing Problem (AHVRP).
spa
dc.description.abstract
Over the last decades, globalization has driven the adaptation of the Transport and Logistics sector to new social demands. At the same time, transport has been the backbone of globalization. This social need creates ambitious consumers who need their products quickly and an affordable price often unaware of their origin, transport mode or environmental aspects, among other factors. Nevertheless, to satisfy customer demands, it is needed to find the cheapest transport mode, which in turn means the improvement of transport logistics of the products. Therefore, these demands require an increasingly flexible service to meet customer requirements, and in addition companies want an efficient and productive transport. The so called Traveling Salesman Problems (TSP) and Vehicle Routing Problems (VRP) provide the theoretical framework for approaching this class of logistic problems associated with the physical distribution of goods from a central depot to customers. They are two of the most challenging and researched problems because of their complexity and applicability. The main goal of this PhD thesis is to introduce hybrid methodologies that integrate several techniques to efficiently solve rich VRPs with realistic constraints. It starts with theoretical problems and evolves into more realistic scenarios tackling six combinatorial problems related to road transport. A metaheuristic named Tailored Lagrangian Metaheuristic (TLM) has been developed to tackle the TSP. It is based on the Lagrangian Relaxation which is used to exploit the structure of the problem reducing considerably its complexity by moving hard-to-satisfy constraints into the objective function, associating a penalty in case the constraints are not satisfied. The developed metaheuristic for the TSP has been integrated into two hybrid methodologies combined with Constraint Programming to tackle more complex problems. First of all, it is addressed the Capacitated Vehicle Routing Problem (CVRP), whose vehicles have limited loading capacity of the goods that must be delivered. Secondly, it has been addressed a real problem of the Home Health Care (HHC) service in the municipality of Ferrara, Italy. It consists on assigning patients' services to nurses which travel to each patient’s home. Theoretical researches typically assume the symmetry of the distance-based costs associated with traveling from one place to another as well as the existence of a homogeneous fleet of vehicles with limited capacity. This thesis studies different variants focusing on the impact that causes the asymmetry of the costs and the heterogeneity of the fleet. For these purpose, the Asymmetric Traveling Salesman Problem (ATSP), the Asymmetric Capacitated Vehicle Routing Problem (ACVRP) and the Asymmetric and Heterogeneous Vehicle Routing Problem (AHVRP) are addressed.
eng
dc.format.extent
182 p.
cat
dc.format.mimetype
application/pdf
dc.language.iso
eng
cat
dc.publisher
Universitat Autònoma de Barcelona
dc.rights.license
L'accés als continguts d'aquesta tesi queda condicionat a l'acceptació de les condicions d'ús establertes per la següent llicència Creative Commons: http://creativecommons.org/licenses/by-nc-nd/3.0/es/
dc.rights.uri
http://creativecommons.org/licenses/by-nc-nd/3.0/es/
*
dc.source
TDX (Tesis Doctorals en Xarxa)
dc.subject
Metaheuristics
cat
dc.subject
Metaheuristicas
cat
dc.subject
Metaheuristiques
cat
dc.subject
Traveling salesman problem
cat
dc.subject
Problema del agente viajero
cat
dc.subject
Problema del viatjant de comerç
cat
dc.subject
Asymmetric costs
cat
dc.subject
Costes asimétricos
cat
dc.subject
Costos asimètrics
cat
dc.subject.other
Tecnologies
cat
dc.title
Hybrid methodologies for symmetric and asymmetric vehicle routing problems
cat
dc.type
info:eu-repo/semantics/doctoralThesis
dc.type
info:eu-repo/semantics/publishedVersion
dc.subject.udc
519.1
cat
dc.contributor.authoremail
rherrero.math@gmail.com
cat
dc.contributor.director
Ramos González, Juan José
dc.embargo.terms
cap
cat
dc.rights.accessLevel
info:eu-repo/semantics/openAccess


Documents

rha1de1.pdf

9.411Mb PDF

Aquest element apareix en la col·lecció o col·leccions següent(s)