ESTRATEGIA GRASP PARA EL PROBLEMA DE ENRUTAMIENTO DE VEHÍCULOS CON RECOGIDA Y ENTREGA SIMULTÁNEA

Abstract

Vehicle Routing Problem with Simultaneous Pickup and Delivery (VRPSPD) is defined as follows: given a set of customers with pickup and delivery demands, a set of vehicles and a depot, the goal is to design least – cost routes originating and terminating at the depot such that all customers are served in single visits and subject to vehicle capacity constraints. The critical feature of the problem is the fluctuating load on the vehicle, thus a route may be not feasible even if the total delivery and the total pickup loads are both below the vehicle’s maximum capacity. In this paper, a penalization related to the overload in the routes is included in the objective function and a set of GRASP based methods are proposed. At each iteration, local search is performed using Variable Neighborhood Descent, Random Variable Neighborhood Descent and Simulated Annealing. All strategies were tested using Dethloff benchmark. It was obtained competitive results, it has reached 18 best solutions over 40 intances, in the remaining cases the average gap was arround 0.5 percent