A Multi-Objective Imperialist Competitive Algorithm for Vehicle Routing Problem in Cross-docking Networks with Time Windows

Document Type : Research Paper


Faculty of Industrial & Systems Engineering, Tarbiat Modares University, Tehran, Iran


This study addresses the pickup and delivery problem for cross-docking strategy, in which shipments are allowed to be transferred from suppliers to retailers directly as well as through cross-docks. Usual models that investigate vehicle routing in cross-docking networks force all vehicles to stop at the cross-dock even if a shipment is about to a full truckload or the vehicle collects and delivers the same set of products. In order to eliminate unnecessary stops at the dock, and thus reduce transportation costs, the designed model tries to decide about the best approach to deliver orders to retailers in a tailored network. In such a system, two objectives are taken into account: minimization of the total transportation cost and minimization of the total earliness and tardiness of visiting retailers. In order to deal with this problem, three multi-objective algorithms are developed. An evolutionary algorithm based on multi objective imperialist competitive algorithm (MOICA) is proposed, and the associated results are compared with the results obtained by non-dominated sorting genetic algorithm (NSGA-II) and Pareto archived evolution strategy (PAES) in terms of some metrics. The computational results show the superiority of the proposed algorithm compared to other algorithms in some metrics. 


Main Subjects

Atashpas-Gargari, E., Lucas, C., “Imperialist competitive algorithm: An algorithm for optimization inspired by imperialist competitive,” Proceeding IEEE Congress on Evolutionary computation, CEC 2007, Singapore, 2007.
Chen, M-Ch, Hsiao, Y-H, , Reddy, R. H., Tiwari, M. K., “The Self-Learning Particle Swarm Optimization approach for routing pickup and delivery of multiple products with material handling in multiple cross-docks,” Transportation Research Part E: Logistics and Transportation Review, Vol. 91, pp. 208–226, 2016.
Deb, K., Agrawal, S., Pratap, A., and Meyarivan, T., “A fast elitist non-dominated sorting genetic algorithm for multi-objective optimization: NSGA-II,” In M.S. et al. (Ed.), Parallel Problem Solving from Nature – PPSN VI, Berlin, Springer, pp. 849–858, 2000.
Deb, K., Pratap, A., Agarwal, S., and Meyarivan, T., “A fast and elitist multi-objective genetic algorithm: NSGA-II,” IEEE Transaction on Evolutionary Computation, Vol. 6(2), pp. 182–197, 2002.
Dondo, R., Méndez, C. A., Cerdá, J., “The multi-echelon vehicle routing problem with cross docking in supply chain management,” Computers and Chemical Engineering, Vol. 35, pp. 3002– 3024, 2011.
El-Ghazali Talbi, “Metaheuristics from design to implementation”, Wiley, University of Lille – CNRS – INRIA, 2009
Gumus, M, Bookbinder, J. H. “Cross-docking and its implications in location– distribution systems,” Journal of Business Logistics; Vol. 25(2), pp. 199–228, 2004.
Hasani Goodarzi, A., Zegordi, S. H., “A Location- Routing Problem for Cross-docking Networks: A Biogeography-based Optimization Algorithm,” Computers and Industrial Engineering, vol. 102, pp. 132–146, 2016.
Hosseini, S.D., Akbarpour Shirazi, M., & Karimi, B., “Cross-docking and milk run logistics in a consolidation network: A hybrid of harmony search and simulated annealing approach,” Journal of Manufacturing Systems, vol. 33, pp. 567–577, 2014.
Knowles, J.D., and Corne, D.W., “The Pareto archived evolution strategy: A new baseline algorithm for Pareto multi-objective optimization,” Congress on Evolutionary Computation (CEC99), Vol. 1, Piscataway, NJ, IEEE Pres, pp. 98–105. 1999.
Konur, D., Golias, M.M., “Cost-stable truck scheduling at a cross-dock facility with unknown truck arrivals: A meta-heuristic approach,” Transportation Research Part E, Vol. 49, pp. 71–91, 2013.
Ladiera, A-L, Alpan, G., “Cross-docking operations: Current research versus industry practice,” Omega, Vol. 62, pp. 145–162, 2016.
Lee, Y.H., Jung, J.W., and Lee, K.M., “Vehicle routing scheduling for cross-docking in the supply chain,”Computers & Industrial Engineering, Vol. 51, pp. 247–256, 2006.
Liao, C.-J., Lin, Y., and Shih, S.C., “Vehicle routing with cross-docking in the supply chain,” Expert Systems with Applications, Vol. 37, pp. 6868–6873, 2010.
Ma, H., Miao, Z., Lim, A., Rodrigues, B., “Cross docking distribution networks with setup cost and time window constraint,” Omega, Vol. 39, pp. 64–72, 2011.
Marseguerra, M., Zio, E., and Podofillini, L., “Condition-based maintenance optimization by means of genetic algorithms and Monte Carlo simulation,” Reliability Engineering and System Safety, Vol. 77, pp. 151–166, 2002.
Mohammadi, M., Jolai, F. and Tavakkoli-Moghaddam, R., “Solving a new stochastic multi-mode p-hub covering location problem considering risk by a novel multi-objective algorithm,” Applied Mathematical Modelling, Vol. 37 (24), 2013, pp. 10053–10073.
Musa, R., Arnaout, J.P., and Jung, H., “Ant colony optimization algorithm to solve for the transportation problem of cross-docking network,” Computers& Industrial Engineering, Vol. 59(1), pp. 85-92, 2010.
Nikolopoulou, A.I., Repoussis, P.P., Tarantilis, Ch.D., Zachariadis, E. E., “Moving products between location pairs: Cross-docking versus direct-shipping,” European Journal of Operational Research, Vol. 256 (3), pp. 803–819, 2017.
Ombuki, B., Ross, B.J., and Hanshar, F., “Multi-Objective Genetic Algorithms for Vehicle Routing Problem with Time Windows,” Applied Intelligence, Springer, Vol. 24, pp. 17–30, 2006.
Ross, A., and Jayaraman, V., “An evaluation of new heuristics for the location of cross-docks distribution centers in supply chain network design,” Computers & Industrial Engineering, Vol. 55, pp. 64–79, 2008.
Santos, F.A., Mateus, G. R., Salles da Cunha, A., “The Pickup and Delivery Problem with Cross-Docking,” Computers & Operations Research, Vol. 40, pp.1085–1093, 2013.
Santos, F.A., Mateus, G.R., da Cunha, A.S., “A branch-and-price algorithm for a vehicle routing problem with cross docking. In: LAGOS’11—VI Latin American algorithms, graphs and optimization symposium,” Electronic notes in discrete mathematics, Vol. 37, pp. 249–254, 2011.
Santos, F.A., Mateus, G.R., da Cunha, A.S., “A novel column generation algorithm for the vehicle routing problem with cross-docking In: Network optimization,” Lecture notes in computer science, Springer, Vol. 6701, pp. 412–425, 2011.
Shi, W., Liu, Z., Shang, J., Cui, Y., “Multi-criteria robust design of a JIT-based cross-docking distribution center for an auto parts supply chain,” European Journal of Operational Research, Vol. 229, pp. 695–706, 2013.
Tarantilis, Christos D., “Adaptive multi-restart Tabu Search algorithm for the vehicle routing problem with cross-docking,” Optim Lett, Vol. 7, pp. 1583–1596, 2013.
Tavakkoli-Moghaddam, R., Azarkish, M. and Sadeghnejad, A., “A new hybrid multiobjective Pareto archive PSO algorithm for a bi-objective job shop scheduling problem,” Expert System with Applications. Vol. 38(9), pp. 10812-10821, 2011.
Vahdani, B., Tavakkoli-Moghaddam, R., Zandieh, M., and Razmi, J. “Vehicle routing scheduling using an enhanced hybrid optimization approach,” Journal of Intelligent Manufacturing, Vol. 23, pp. 759–774, 2012.
Vasiljevic, D., Stepanovic, M., Manojlovic, O., “Cross docking implementation in distribution of food products,” Economics of Agriculture, Year 60, No. 1 (1-216), pp 91-101, Belgrade, 2013.
Wen, M., Larsen, J., Clausen, J., Cordeau, J.-F., and Laporte, G. “Vehicle routing with cross-docking,” Journal of the Operational Research Society. Vol. 60 (12), pp. 1708-1718, 2008.
Yang, KK., Balakrishnan, J., Cheng, CH. “An analysis of factors affecting cross docking operations,” Journal of Business Logistics, Vol. 31(1), pp.121–48, 2010.
Yin, P-Y, Chuang, Y-L, “Adaptive memory artificial bee colony algorithm for green vehicle routing with cross-docking,” Applied Mathematical Modelling, Vol. 40 (21–22), pp. 9302–9315, 2016.
Yu, V.F., Jewpanya, P., Perwira Redi, A.A.N., “Open vehicle routing problem with cross-docking,” Computers & Industrial Engineering, Vol. 94, pp. 6–17, 2016.