Abstract

The Vehicle Routing Problem, which main objective is to find the lowest-cost set
of routes to deliver goods to customers, has many applications in transportation
services. In the past, costs have been mainly associated to the number of routes and
the travel distance, however, in real-world problems there exist additional objectives.

Since there is no known exact method to efficiently solve the problem in polynomial
time, many heuristic techniques have been considered, among which, evolutionary
methods have proved to be suitable for solving the problem. Despite this method
being able to provide a set of solutions that represent the trade-offs between multiple
objectives, very few studies have concentrated on the optimisation of more than one
objective, and even fewer have explicitly considered the diversity of solutions, which
is crucial for the good performance of any evolutionary computation technique.

This thesis proposes a novel Multi-Objective Evolutionary Algorithm to solve two
variants of the Vehicle Routing Problem, regarding the optimisation of at least two
objectives. This approach incorporates a method for measuring the similarity of solutions,
which is used to enhance population diversity, and operators that effectively
explore and exploit the search space. The algorithm is applied to typical benchmark
problems and empirical analyses indicate that it efficiently solves the variants being
studied. Moreover, the proposed method has proved to be competitive with recent
approaches and outperforms the successful multi-objective optimiser NSGA-II.