ABSTRACT

This PhD thesis shows that the reality of the vehicle routing problems that characterize real-world business is very complex and asymmetric, and this is reflected in the distance matrix (time or cost) between pairs of locations that are basis for all routing problems.
This research quantifies the relationship between the asymmetry degree of the distance matrix and factors such as territory and the customers location. It also underscores the importance of obtaining the real and asymmetric distance matrix.
The main objective of this thesis is to quantify the extent to which the asymmetry has an effect on the efficiency and effectiveness of the main heuristics and meta-heuristics in solving recognized two fundamental cases of routing problems: the TSP and CVRP. Additionally, it also examines the impact of other factors (territory, the location, number of customers, demand and capacity) in the results (computational time and goodness of the solution).
By performing many computational experiments and statistical analysis of results (ANOVA among others) is demonstrated that all the techniques studied are affected by the asymmetry and other factors. The solution to symmetric problems differs from asymmetric ones (either quantitatively or qualitatively).
Therefore we can infer that the asymmetry has a major impact on all vehicle routing problems, and it must be considered as a key factor in any research and development application in the real business context.

Keywords: asymmetry, vehicle routing problems, TSP, CVRP, GIS, matrix