Hybrid methodologies for symmetric and asymmetric vehicle routing problems

The main goal of this PhD thesis is to introduce hybrid methodologies that integrate several techniques to efficiently solve rich Vehicle Routing Problems (VRP)'s 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.


  • English

Media Info

  • Pagination: 182p

Subject/Index Terms

Filing Info

  • Accession Number: 01604788
  • Record Type: Publication
  • Source Agency: ARRB
  • ISBN: 9788449060595
  • Files: ATRI
  • Created Date: Jul 18 2016 4:46PM