Dr. Roberto Carballedo

Transportation is an activity that plays a very important role in our modern society. The distribution of goods, transport of people, or the provision of services (such as waste collection), are activities that have a direct impact on our quality of life, economy and environment.

Transportation has also a crucial relevance in the scientific community. A large and wide variety of problems have arisen around this area. All these problems have similar characteristics in terms of computational complexity, which makes them difficult to solve. This leads, in many cases, to serious difficulties in obtaining feasible solutions. For this reason, it is necessary to use approximation techniques that allow to obtain good solutions in a limited time. Thus, a wide range of optimization problems and solving techniques have emerged. To obtain increasingly better solutions and have a lower computational cost, these techniques are based on continuous improvement strategies.

The present research focuses on vehicle routing problems. Although these problems have been extensively studied over the past 50 years, they still have scientific interest. This is because there is no technique capable of solving some problems in a polynomial time. Therefore, it is possible to find and address areas for improvement, which contribute to the optimization of existing resolution techniques.

Therefore, this doctoral thesis focuses on improving the solving process of one of the most widely studied variations of the basic vehicle routing problem: the one that includes time windows (VRPTW). The work focuses on developing improvements in two phases of the solving process: the construction of the initial solution and the iterative improvement of the solution. The main novelty of the proposed approach is related to the purpose of the improvement process. In that sense, the process focuses on minimizing the number of routes (which is a criterion that measures the quality of a solution). The work done includes an extensive experimentation to compare the proposed algorithms and the most representative techniques. Also, with the aim of obtaining fair and objective conclusions, the results have been subjected to a rigorous analysis. With all this, it can be concluded that the new algorithms represent a good complement for any of the heuristics and metaheuristics that obtain the best results for the most representative VRPTW benchmark problems.