Problema de roteamento de veículos com coleta e entrega simultânea com dados coletados a partir de aplicativos de mapas

Abstract

In this work, a generalization of the Capacitated Vehicle Routing Problem (CVRP) called Vehicle Routing Problem with Simultaneous Pickup and Delivery (VRPSPD) was addressed. In this variant that generalizes the CVRP, a set of collection demands is added, which must be met simultaneously with the set of delivery demands. The objective of the VRPSPD is to determine routes that meet all collection and delivery demands for all customers, with all vehicles starting at the depot and returning to the depot, minimizing the total distance traveled by all vehicles. This work proposes the use of real data collected from available and free map applications. Throughout the proposed work was to use a heuristic called Ant Colony Optimization Algorithm (ACO) to solve the VRPSPD, along with the ACO two other approaches were used, a solver called Gurobi and a heuristic called Busca Tabu (TS, being the solver and the TS heuristic already exists in the literature and was used as a benchmark. in map applications. The Gurobi solver proved to be very effective in small instances and even in some medium ones, while in large instances the solver did not achieve a good performance with the parameters and averages, but in larger instances they did not show a good performance. The ACO proved to be better in most instances, that is, it was better in time to obtain the solution and in the cost obtained.