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

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.

We design three initial solution methods, namely the Adapted Sweep, the Adapted Nearest Neighbour and the Parallel Clustering method. They are motivated by the real attributes of the Vehicle Routing Problem under research and show a very good performance in terms of reaching a good initial solution quality as compared to other famous initial solution methods in the literature. Moreover, the Adapted Sweep and the Adapted Nearest Neighbour have computational times of less than one second.

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 later extend the Population Variable Neighbourhood Search with Adaptive Memory Procedure (PVNS_AMP) and hybridize it with aspects from Tabu Search in order to create the second new hybrid metaheuristic method, namely the Population Variable Neighbourhood Search with Adaptive Memory Procedure and Tabu Search principles (TS_PVNS_AMP). The TS_PVNS_AMP was found to have better performance on the RVRP without overtime, and superior performance on the RVRP with overtime as compared to the PVNS_AMP. Moreover, the TS_PVNS_AMP showed a better performance than the PVNS_AMP on the relevant literature benchmark instances reaching Best Known Solutions in the literature with less than 0.5 % deviation from the Best Known Solutions on average.

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.