Metaheuristic approaches for the stochastic capacitated multi-depot vehicle routing problem with pickup and delivery

Ojeda Rios B.H.; Xavier E.C. · Expert Systems with Applications (2025) · DOI: 10.1016/j.eswa.2025.128258

Resumen

The classical Vehicle Routing Problem (VRP) is to determine optimal routes for m identical vehicles that must visit a set of customers, departing from and returning to a depot. The following restrictions must be satisfied: (1) each vehicle begins and ends at the depot and (2) each customer is visited exactly once. We consider a novel variant of the VRP that incorporates multiple depots, vehicle capacity and stochastic information about future incoming of customers. We denote this problem as the stochastic capacitated multi-depot VRP with pickup and delivery (SCMVRPPD). The SCMVRPPD is an extension of the capacitated VRP with pickup and delivery, in which there is a different depot for each vehicle and the pickup and delivery points (each pair associated with a customer) are stochastic. The problem is to compute routes visiting all pairs of pickup and delivery minimizing the expected total cost of routes, since the real occurrence of each pair of pickup/delivery is random. In this case, some of the a priori designed routes can fail. We propose strategies to correct routes with failures. For each different strategy, we propose methods to efficiently compute the expected cost of a solution and, for one particular correction strategy, we propose a closed-form expression. We propose three algorithms to tackle the problem: a Tabu search (TS) heuristic, a Generalized Variable Neighborhood Search (GVNS) and an Iterated Local Search (ILS-VND) method. We used modified instances from a well-known benchmark of instances of the VRP to compare the algorithms. Computational results clearly show the superiority of the proposed ILS heuristic over alternative solution approaches.

Instituciones: Universidad de Ingeniería y Tecnología