A Memetic Algorithm for the Vehicle Routing Problem with Cross Docking

In this paper we address the VRPCD, in which a set of homogeneous vehicles are used to transport products from the suppliers to customers via a cross-dock. The products can be consolidated at the cross-dock but cannot be stored for very long as the cross-dock does not have long-term inventory-holding capabilities. The objective of the VRPCD is to minimize the total traveled distance while respecting time window constraints of suppliers and customers and a time horizon for the whole transportation operation. Following the literature on vehicle routing problems with cross-docking, it seems that few studies consider that customer will receive its requests from several suppliers; therefore, the present study is an attempt to investigate this case. A heuristic and a memetic algorithm are used to solve the problem. The proposed algorithms are implemented and tested on data sets involving up to 200 nodes (customers and suppliers). The first results show that the memetic algorithm can produce high quality solutions. It is able to find the optimal solution for small instances, for the large ones, it is very powerful comparing with the best insertion heuristic, the gap achieved 30%.