A Memetic Algorithm for the Vehicle Routing Problem with Cross Docking

Document Type: Review Paper


University of abdelmalek Essaadi, Mhannech II, Tetouan, Morocco


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. Rummaging through all the work of literature on vehicle routing problems with cross-docking, there is no work that considers that customer will receive its requests from several suppliers; this will be the point of innovation of this work. 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.


Main Subjects

Yang H.L., Sarker B. and Chang C.T. (2013). A two-warehouse partial backlogging inventory model for deteriorating items with permissible delay in payment under inflation. Applied Mathematical Modelling, Vol. 37, pp. 2717–2726.

M.Wen, J.Larsen, J.Clausen, J.F Cordeau, and G Laporte(2008), Vehicle routing with CrossDocking, Journal of Operational Research Society ,vol.60, pp 1708–1718.

Y. H Lee, W. J Jung, and K.M Lee (2006), Vehicle routing scheduling for cross docking in the supply chain.Computer and Industrial Engineering, vol.51, pp.247–256.

F.A Santos,G.R Mateus, and A.S Da Cunha (2011).A novel column generation algorithm for the vehicle routing problem with cross-docking. International conference on Network optimization,5th. pp 412-425.

Solomon. M (1987). Algorithms for the vehicle routing and scheduling problems with time window constraints. Operations Research, vol.35, pp.254–265.

J.H. Holland (1975). Adaptation in natural and artificial systems. The University of Michigan Press, Ann Arbor, MI, USA.

D.E. Goldberg(1989). Genetic Algorithms in Search Optimization and Machine Learning. Addison-Wesley, Reading, MA, USA.

P. Moscato(1999). Memetic algorithms: a short introduction. In D. Corne, M. Dorigo, and F. Glover, editors, New ideas in optimization, pp 219–234: McGraw-Hill.

C. Prins(2004), A simple and effective evolutionary algorithm for the vehicle routing problem, Computer Operations Research, vol.31, pp.1985–2002.

Sung, C.S., Song, S.H., 2003. Integrated service network design for a cross-docking supply chain network, Journal of the Operational Research Society, vol.54, pp.1283-1295.

Lee, Y.H., Jung, J.W., Lee, K.M.(2006). Vehicle routing scheduling for cross-docking in the supply chain, Computers & Industrial Engineering,vol.51, pp.247-256.

Apte,M.U., Viswanathan,S(2000).Effective cross docking for improving distribution efficiencies.International Journal of Logistics: Research and Applications,vol.3, pp.291–302,

N.Labadi ,C.Prins,M.Reghioui(2008). A memetic algorithm for the vehicle routing problem with Time windows , RAIRO Operations Research, vol.42(3), pp.415-431.

Musa R, Arnaout J P, Jung H (2010). Ant colony optimization algorithm to solve for the transportation problem of cross-docking network. Computers &Industrial Engineering, vol.59 (1), pp.85–92.

M.Reghioui(2008). Problèmes de tournées de véhicules avec fenêtres horaires ou préemption des taches. Thèse de doctorat de l’Université de Technologie de Troyes.185 p.