Skip to main content

Heuristic approaches for the Vehicle Routing Problem with Heterogeneous Fleet and Real Life Attributes

Simeonova, Lina (2016) Heuristic approaches for the Vehicle Routing Problem with Heterogeneous Fleet and Real Life Attributes. Doctor of Philosophy (PhD) thesis, University of Kent,. (KAR id:61258)

Language: English
Download (2MB) Preview
[thumbnail of 125Lina_Simeonova_PhD_Thesis_Deposition.pdf]
This file may not be suitable for users of assistive technology.
Request an accessible format


The Vehicle Routing Problem with all its variants and richness is still one of the most challenging Combinatorial Optimization problems in the Management Science / Operations Research arena since its introduction in the 1950s. In this research we introduce a real life Vehicle Routing Problem, inspired by the Gas Delivery industry in the UK. It has various real life attributes which have not been researched in the past, such as demand-dependant service times, light load requirements and allowable overtime coupled with unlimited vehicle fleet. A Mixed Integer formulation of the problem is presented and the problem is solved to optimality, reporting optimal solutions and lower and upper bounds. After solving the real life routing problem, both optimally and heuristically some interesting observations and practical implications are reported, relating to better fleet utilization and better working time utilization.

Two new hybrid metaheuristic methods are designed in order to address the real life Vehicle Routing Problem. A Population Variable Neighbourhood Search with Adaptive Memory Procedure is the first method, which aims to incorporate and hybridize the learning principles of Adaptive Memory into a method which does not make use of memory structures in its original form, namely the Variable Neighbourhood Search. Moreover, we use a Population version of the Variable Neighbourhood Search in order to provide diversification to the method and to aid the learning aspect of the method. The Population Variable Neighbourhood Search with Adaptive Memory Procedure was tested extensively on the real life Vehicle Routing Problem, as well as relevant literature benchmark instances and it was found to perform well in comparison with the optimal solutions we generated. Moreover, the method shows a good performance on the benchmark instances with less than 1% deviation from the Best Known Solutions in the literature.

We have also tested our proposed algorithms on other VRP problems, such as the Heterogeneous Fleet VRP with imposed fleet and the School Bus Routing Problem. We have done this experimentation in order to test the generalizability of the methods and their flexibility in addressing other problems from the Vehicle Routing family. Our methodology showed good performance on the literature benchmarks for both problems in terms of solution quality and computational time, as well as a good degree of flexibility in terms of finding good heuristic solutions.

Item Type: Thesis (Doctor of Philosophy (PhD))
Thesis advisor: Wassan, Niaz
Thesis advisor: Nagy, Gabor
Uncontrolled keywords: Real Life Vehicle Routing Problem; Population Variable Neighborhood Search; Adaptive Memory Procedure
Subjects: H Social Sciences > HD Industries. Land use. Labor
H Social Sciences > HF Commerce
Divisions: Divisions > Kent Business School - Division > Kent Business School (do not use)
Depositing User: Users 1 not found.
Date Deposited: 06 Apr 2017 17:00 UTC
Last Modified: 16 Feb 2021 13:44 UTC
Resource URI: (The current URI for this page, for reference purposes)
  • Depositors only (login required):