Hybridization of very large neighborhood search for ready-mixed concrete delivery problems

Companies in the concrete industry are facing the following scheduling problem on a daily basis: concrete produced at several plants has to be delivered at customers' construction sites using a heterogeneous fleet of vehicles in a timely, but cost-effective manner. The distribution of ready-mixed concrete (RMC) is a highly complex problem in logistics and combinatorial optimization. This paper proposes two hybrid solution procedures for dealing with this problem. They are based on a combination of an exact algorithm and a variable neighborhood search (VNS) approach. The VNS is used at first to generate feasible solutions and is trying to further improve them. The exact method is based on a mixed integer linear programming (MILD) formulation, which is solved (after an appropriated variable fixing phase) by using a general-purpose MILP solver. An approach based on very large neighborhood search (VLNS) determines which variables are supposed to be fixed. In a sense, the approaches follows a local branching scheme. The hybrid metaheuristics are compared with the pure VNS approach and the conclusion is that the new metaheuristics outperform the VNS if applied solely. (C) 2008 Elsevier Ltd. All rights reserved.