Iterated local search heuristics for the Vehicle Routing Problem with Cross-Docking

• Published in: Expert systems with applications 2014-11, Vol.41 (16), p.7495-7506
• Main Authors: Morais, Vinicius W.C., Mateus, Geraldo R., Noronha, Thiago F.
• Format: Article
• Language: English
• Subjects: Algorithmics. Computability. Computer arithmetics; Applied sciences; Computer science; control theory; systems; Cross-docking; Exact sciences and technology; Flows in networks. Combinatorial problems; ILS; Logistics; Mathematical programming; Operational research and scientific management; Operational research. Management science; Set Partitioning; Theoretical computing; Vehicle Routing Problem
• ISSN: 0957-4174; 1873-6793
• DOI: 10.1016/j.eswa.2014.06.010

•We address an optimization problem that integrates cross-docking with Vehicle Routing Problem (VRP). The so called Vehicle Routing Problem with Cross-Docking (VRPCD).•We extend a constructive heuristic and local search procedures from the literature of VRP and propose three Iterated Local Search (ILS) heuristics for VRPCD.•Our ILS heuristics are based on an adaptive set of elite feasible solutions.•Our ILS heuristics are based on inter-route, inter-vehicular and intra-route local searches.•The best of our heuristics improved the best solution known for half of the benchmark instances. This work addresses the Vehicle Routing Problem with Cross-Docking (VRPCD). The problem consists in defining a minimum cost set of routes for a fleet of vehicles that meets the demands of products for a set of suppliers and customers. The vehicles leave a single Cross-Dock (CD) towards the suppliers, pick up products and return to the CD, where products can be exchanged before being delivered to their customers. The vehicle routes must respect the vehicle capacity constraints, as well as the time window constraints. We adapted a constructive heuristic and six local search procedures from the literature of VRP, and made them efficient in the presence of the synchronization constraints of VRPCD. Besides, we propose three Iterated Local Search (Lourenço et al., 2010) heuristics for VRPCD. The first heuristic is a standard implementation of ILS, while the second extends the classic ILS framework by keeping a set of elite solutions, instead of a single current solution. The latter set is used in a restart procedure. As far as we can tell, this is the first ILS heuristic in the literature that keeps a population of current elite solutions. The third heuristic is an extension of the second that relies on an intensification procedure based on an Integer Programming formulation for the Set Partitioning problem. The latter allows a neighborhood with an exponential number of neighbors to be efficiently evaluated. We report computational results and comparisons with the best heuristics in the literature. Besides, we also present a new set with the largest instances in the literature of VRPCD, in order to demonstrate that the improvements we propose for the ILS metaheuristic are efficient even for large size instances. Results show that the best of our heuristics is competitive with the best heuristics in the literature of VRPCD. Besides, it improved the best solution known for half of t