A hybrid algorithm for a class of vehicle routing problems

In this work we propose a hybrid algorithm for a class of Vehicle Routing Problems with homogeneous fleet. A sequence of Set Partitioning (SP) models, with columns corresponding to routes found by a metaheuristic approach, are solved, not necessarily to optimality, using a Mixed Integer Programming (MIP) solver, that may interact with the metaheuristic during its execution. Moreover, we developed a reactive mechanism that dynamically controls the dimension of the SP models when dealing with large size instances. The algorithm was extensively tested on benchmark instances of the following Vechicle Routing Problem (VRP) variants: (i) Capacitated VRP; (ii) Asymmetric VRP; (iii) Open VRP; (iv) VRP with Simultaneous Pickup and Delivery; (v) VRP with Mixed Pickup and Delivery; (vi) Multi-depot VRP; (vii) Multi-depot VRP with Mixed Pickup and Delivery. The results obtained were quite competitive with those found by heuristics devoted to specific variants. A number of new best solutions were obtained.