Abstract

Most real-life problems involve the simultaneous optimisation of two or more, 
usually conflicting, objectives. Researchers have put a continuous effort into 
solving these problems in many different areas, such as engineering, finance 
and computer science. Over time, thanks to the increase in processing power, 
researchers have created methods which have become increasingly sophisticated. 
Most of these methods have been based on the notion of Pareto dominance, which 
assumes, sometimes erroneously, that the objectives have no known ranking of 
importance.

The Vehicle Routing Problem with Time Windows (VRPTW) is a logistics problem 
which in real-life applications appears to be multi-objective. This problem 
consists of designing the optimal set of routes to serve a number of customers 
within certain time slots. Despite this problem’s high applicability to real-life 
domains (e.g. waste collection, fast-food delivery), most research in this area 
has been conducted with hand-made datasets. These datasets sometimes have a number 
of unrealistic features (e.g. the assumption that one unit of travel time 
corresponds to one unit of travel distance) and are therefore not adequate for 
the assessment of optimisers. Furthermore, very few studies have focused on the 
multi-objective nature of the VRPTW. That is, very few have studied how the 
optimisation of one objective affects the others.

This thesis proposes a number of novel tools (methods + dataset) to address the 
above-mentioned challenges: 1) an agent-based framework for cooperative search, 
2) a novel multi-objective ranking approach, 3) a new dataset for the VRPTW, 
4) a study of the pair-wise relationships between five common objectives in VRPTW, 
and 5) a simplified Multi-objective Discrete Particle Swarm Optimisation for the 
VRPTW.