Project Title: Dynamic Lexicographic Local Search Algorithm for Multi-objective Routing Problem Student: Aigerim Baikenova Course: MSc Management of IT Abstract: The vehicle routing problem with time windows is an important logistics and transportation problem which is also very difficult to solve because of its computational complexity. Most research in this area carried out to solve this problem is done on the single-objective version of the problem where usually the goal is to minimize the cost of transportation by minimizing the travelled distance or minimizing the size of the fleet. However, in real-world scenarios there are other objectives that must be considered simultaneously and then multi-objective optimization methods should be considered. Many of these methods are based on ranking the multiple objectives and it is often difficult for to establish priorities among the objectives in advance. Dynamic lexicographic ordering is a recent technique that dynamically changes the priority of the objectives during the search for solutions. This technique has been used within a population-based search heuristics algorithm, namely particle swarm optimization. This dissertation describes the development of the multi-objective local search heuristic algorithm, based on the dynamic lexicographic ordering, to tackle the multi-objective vehicle routing problem with time windows (MOVRPTW). The objective is to extend a single-solution local search algorithm to a multi-objective version by incorporating the dynamic lexicographic approach. The local search heuristic considered in this project is a hybrid algorithm resulting from combining the nonlinear great deluge algorithm and the tabu search method. Computational experiments are carried out using a recently proposed set of benchmark instances for the MOVRTPW. Three objectives are considered: total travelled distance, number of vehicles and the time spent for the travelling the longest route. The results show that the performance of the proposed hybrid dynamic lexicographic algorithm is better than the performance of the single-objective version of the algorithm.