A metaheuristic approach for the Vehicle Routing Problem with Backhauls

Despite the vivid research activity in the sector of the exact methods, nowadays many Optimization Problems are classified as Np-Hard and need to be solved by heuristic methods, even in the case of instances of limited size. In this thesis a Vehicle Routing Problem with Backhauls is investigated. A Greedy Randomized Adaptive Search Procedure metaheuristic is proposed for this problem. Several versions of the metaheuristic are tested on symmetric and asymmetric instances. Although the metaheuristic does not outperform the best known solutions, a large number of high-quality routes are determined in several solutions for each instance. Therefore the metaheuristic is a promising approach to generate feasible paths for set-partitioning-based formulations.