Meta-heurística híbrida para o problema de roteamento de veículos com coleta e entrega e janela de tempo

Abstract

This work addresses the Green Pickup and Delivery Problem with Time Windows, known as Green-PDPTW. This problem consists of constructing routes for a fleet of vehicles in order to serve pickup and delivery requests while respecting capacity constraints, precedence between pickup and delivery, and time windows. In addition to the operational cost, the problem also considers environmental aspects by estimating greenhouse gas emissions generated during vehicle movements. To deal with this problem, a hybrid metaheuristic based on the combination of Differential Evolution and Tabu Search was proposed. Since Differential Evolution was originally developed for continuous optimization problems, an adaptation to the discrete search space of the Green-PDPTW was required, using a route-based representation and an auxiliary pseudo-solution composed of pickup points. The proposed approach uses mutation, crossover, repair operators, and a local improvement step based on Tabu Search. Computational experiments were carried out using lrc1 instances, from lrc101 to lrc108, and the results were compared with known solutions from the dataset and with results reported in the literature. The results indicated that the proposed approach was able to reduce the number of vehicles used when compared to the reference solutions; however, it produced longer distances in some instances and presented limitations related to time window feasibility. Even so, the method showed potential as an alternative for the Green-PDPTW, mainly because it combines operational and environmental criteria in the solution evaluation process.