An ILP-based heuristic for the VRP with pickups and deliveries

AGUSTÍN ISMAEL MONTERO; ISABEL MÉNDEZ-DÍAZ; JUAN JOSÉ MIRANDA BRONT

Lisboa

Simposio; 3rd International Symposium on Combinatorial Optimization; 2014

University of Lisboa

We address the Vehicle Routing Problem with pickups and deliveries (VRPPD) with a heuristic approach. We consider the one-to-one problem (see, e.g. Berbeglia et al. (2007)) where a particular precedence must be satisfied by a pair of origin-destination clients. Formally, let G = (V, E) be an undirected complete graph, with 0, 1, . . . , 2n the set of vertices and E the set of edges, where 0 represents the depot. Each edge has an associated positive distance and there is a precedence constraint between vertices i, n + i, for i = 1, . . . , n. The objective is to find a set of at most k routes covering each vertex exactly once at minimum total cost. In this research, we consider the scheme proposed in De Franceschi et al. (2006) for the Distance Constrained Capacitated VRP, which has been successfully applied to other variants of the VRP (see, e.g., Toth and Tramontani (2008), Naji-Azimi et al. (2012)). Starting from a initial feasible solution, this scheme follows the destroy/repair paradigm where a set of vertices is removed from the routes and reinserted by solving heuristically an associated ILP formulation with an exponential number of variables, named Reallocation Model (RM). Given the RM has an exponential number of variables, the standard approach is to heuristically generate columns considering their reduced cost and solve the model by a general purpose ILP solver, such as CPLEX. Our work presents a formulation of the RM that includes the precedence constraints to guarantee the feasibility of the solution. In contrast to the previous cases, the number of rows in the RM is not fixed a priori since precedence constraints have to be included in the formulation depending on the set of variables generated, and the formulation becomes a special case of the column-dependent-rows problem studied, e.g., in Muter et al. (2012). As a result, reduced costs can only be approximated using the current dual information without solving auxiliary subproblems. Therefore, we study the computational behavior of the general scheme and propose some modifications in order to generate good quality variables for the RM. Based on preliminary results, the proposed scheme shows good potential to be applied in practice and a is good starting point to consider more complex versions of the VRPPD.