A multi-objective Two-Echelon Capacitated Vehicle Routing Problem for perishable products

Document Type : Research Paper


Industrial Engineering Department, College of Engineering, Shahed University, Tehran, Iran


This article addresses a general tri-objective two-echelon capacitated vehicle routing problem (2E-CVRP) to minimize the total travel cost, customers waiting times and carbon dioxide emissions simultaneously in distributing perishable products. In distributing perishable products, customers’ satisfaction is very important and is inversely proportional to the customers waiting times. The proposed model is a mixed integer non-linear programming (MINLP). By applying some linearization methods, the MINLP model exchanged to a mixed integer linear programming (MILP). This paper uses a non-dominated sorting genetic (NSGA-II) algorithm to solve the presented mathematical model. The related results would be compared with Lp-metric results in small-sized test problems and with multi objective particle swarm optimization (MOPSO) algorithm in medium and large sized test problems. In order to evaluate the quality of the solution sets, the results of two metaheuristic algorithms are compared based on four comparison metrics in medium sized problems. The obtained results indicate the efficiency of the NSGA-II algorithm. 


Main Subjects

Angel-Bello, F., Martínez-Salazar, I., & Alvarez, A. (2013). Minimizing waiting times in a route design problem with multiple use of a single vehicle. Electronic Notes in Discrete Mathematics, 41, 269-276.
Afshar-Nadjafi, B., & Razmi-Farooji, A. (2014). A Comparison of NSGA II and MOSA for Solving Multi-depots Time-dependent Vehicle Routing Problem with Heterogeneous Fleet. Journal of Optimization in Industrial Engineering, 7(16), 65-73.
Baldacci, R., Mingozzi, A., Roberti, R., & Calvo, R. W. (2013). An exact algorithm for the two-echelon capacitated vehicle routing problem. Operations Research, 61(2), 298-314.
Christofides, N., & Eilon, S. (1969). An algorithm for the vehicle-dispatching problem. Or, 309-318.
Crainic, T. G., Ricciardi, N., & Storchi, G. (2009). Models for evaluating and planning city logistics systems. Transportation science43(4), 432-454.
Crainic, T. G., Perboli, G., Mancini, S., & Tadei, R. (2010). Two-echelon vehicle routing problem: a satellite location analysis. Procedia-Social and Behavioral Sciences, 2(3), 5944-5955.
Chen, H. K., Hsueh, C. F., & Chang, M. S. (2009). Production scheduling and vehicle routing with time windows for perishable food products. Computers & Operations Research, 36(7), 2311-2319.
Cuda, R., Guastaroba, G., & Speranza, M. G. (2015). A survey on two-echelon routing problems. Computers & Operations Research, 55, 185-199.
Deb, K., Pratap, A., Agarwal, S., & Meyarivan, T. A. M. T. (2002). A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE transactions on evolutionary computation6(2), 182-197.
Eberhart, R., & Kennedy, J. (1995, October). A new optimizer using particle swarm theory. In Micro Machine and Human Science, 1995. MHS'95., Proceedings of the Sixth International Symposium on (pp. 39-43). IEEE.
Mirzapour Al-e-hashem, S. M. J., & Rekik, Y. (2014). Multi-product multi-period Inventory Routing Problem with a transshipment option: A green approach. International Journal of Production Economics157, 80-88.
Mahmoodjanloo, M., Esmaili, M., & Hajiaghaei-Keshteli, M. (2016). A Tri-objective model for the school bus routing problem with a new approach in network design. 2nd International Conference on Industrial & Systems Engineering, (ICISE), 14, 15 Sep. 2016, Mashhad.
Esmaili, M., & Sahraeian, R. (2017). A new Bi-objective model for a Two-echelon Capacitated Vehicle Routing Problem for Perishable Products with the Environmental Factor.International Journal of Engineering, (30)4, 523-531.
Fan, J. (2011). The vehicle routing problem with simultaneous pickup and delivery based on customer satisfaction. Procedia Engineering, 15, 5284-5289.
Glover, F., & Woolsey, E. (1974). Converting the 0-1 polynomial programming problem to a 0-1 linear program. Operations research22(1), 180-182.
Govindan, K., Devika, K., Jafarian, A., & Khodaverdi, R. (2013). Two-echelon multiple-vehicle location–routing problem with time windows for optimization of sustainable supply chain network of perishable food. International Journal of Production Economics, 152, 9-28.
Holland, J. H. (1975). Adaptation in natural and artificial systems. University of Michigan Press. Ann Arbor1(975), 1.
Hemmelmayer, V. C., Cordeau, J. F., & Crainic, T. G. (2012). An adaptive large neighborhood search heuristic for two-echelon vehicle routing problems arising in city logistics. Computers & operations research, 39(12), 3215-3228.
Jepsen, M., Spoorendonk, S., & Ropke, S. (2013). A branch-and-cut algorithm for the symmetric two-echelon capacitated vehicle routing problem. Transportation Science, 47(1), 23-37.
Lin, C., Choy, K. L., Ho, G. T., Chung, S. H., & Lam, H. Y. (2014). Survey of green vehicle routing problem: past and future trends. Expert Systems with Applications, 41(4), 1118-1138.
Maghsoudlou, H., Kahag, M. R., Niaki, S. T. A., & Pourvaziri, H. (2016). Bi-objective optimization of a three-echelon multi-server supply-chain problem in congested systems: Modeling and solution. Computers & Industrial Engineering99, 41-62.
Perboli, G., Tadei, R., & Vigo, D. (2011). The two-echelon capacitated vehicle routing problem: models and math-based heuristics. Transportation Science, 45(3), 364-380.
Rabbani, M., Ramezankhani, M. J., Farrokhi-Asl, H., & Farshbaf-Geranmayeh, A. (2015). Vehicle routing with time windows and customer selection for perishable goods. International Journal of Supply and Operations Management, 2(2), 700.
Rabbani, M., Farrokhi-Asl, H., & Asgarian, B. (2017). Solving a bi-objective location routing problem by a NSGA-II combined with clustering approach: application in waste collection problem. Journal of Industrial Engineering International, 13(1), 13-27.
Santos, F. A., Mateus, G. R., & da Cunha, A. S. (2014). A branch-and-cut-and-price algorithm for the two-echelon capacitated vehicle routing problem. Transportation Science, 49(2), 355-368.
Soysal, M., Bloemhof-Ruwaard, J. M., & Bektaş, T. (2015). The time-dependent two-echelon capacitated vehicle routing problem with environmental considerations. International Journal of Production Economics, 164, 366-378.
Song, B. D., & Ko, Y. D. (2016). A vehicle routing problem of both refrigerated-and general-type vehicles for perishable food products delivery. Journal of Food Engineering, 169, 61-71.
Wang, X., Wang, M., Ruan, J., & Zhan, H. (2016). The multi-objective optimization for perishable food distribution route considering temporal-spatial distance. Procedia Computer Science, 96, 1211-1220.
Zeng, Z. Y., Xu, W. S., & Xu, Z. Y. (2013, November). A two-phase hybrid heuristic for the two-echelon vehicle routing problem. In Chinese Automation Congress (CAC), 2013 (pp. 625-630). IEEE.