Solving a bi-objective multi-commodity two-echelon capacitated location routing problem

Document Type : Research Paper


School of Industrial and Systems Engineering, College of Engineering, University of Tehran, Tehran, Iran


Planning the freight flow from the plants to the customer zones is one of the most challenging problems in the field of supply chain management. Because of many traffic regulations, oversize/overweight vehicles often are not permitted to enter city boundaries. Therefore, intermediate facilities (city distribution centers) play a very important role in distribution networks. Accordingly, in this paper, transportation of goods from the plants to the customers is considered an integrated process containing two phases, namely, transportation from plant to distribution centers and distribution from city distribution centers to customers using small and environmentally-friendly vehicles. The Transportation Location Routing Problem (TLRP) studied can be considered as an extension of the two-echelon location routing problem. Minimizing the operational costs, and the workload balancing of the heterogeneous fleet in the distribution phase are considered as the two objective functions. A Mixed Integer Programming (MIP) model, as well as two solution approaches, based on Multi-objective Particle Swarm Optimization Algorithm, and Non-dominated Sorting Genetic Algorithm, is presented for the problem. In order to illustrate the efficacy of the proposed methods, they have been implemented on test problems of different sizes. The results show the methods are able to produce efficient solutions in a reasonable amount of time.


Main Subjects

Ai, T. J., & Kachitvichyanukul, V. (2009). Particle swarm optimization and two solution representations for solving the capacitated vehicle routing problem. Computers & Industrial Engineering, 56(1), 380-387.
Aikens, C. H. (1985). Facility location models for distribution planning. European journal of operational research, 22(3), 263-279.
Ambrosino, D., & Scutella, M. G. (2005). Distribution network design: New problems and related models. European journal of operational research, 165(3), 610-624.
Azadeh, A., & Farrokhi-Asl, H. (2019). The close–open mixed multi depot vehicle routing problem considering internal and external fleet of vehicles. Transportation Letters, 11(2), 78-92.
Bazgan, C., Jamain, F., & Vanderpooten, D. (2015). Approximate Pareto sets of minimal size for multi-objective optimization problems. Operations Research Letters, 43(1), 1-6.
Boccia, M., Crainic, T. G., Sforza, A., & Sterle, C. (2010). A Metaheuristic for a Two Echelon Location-Routing Problem. Paper presented at the SEA.
Chen, C.-T. (2001). A fuzzy approach to select the location of the distribution center. Fuzzy sets and systems, 118(1), 65-73.
Coello Coello, C. A. (2002). MOPSO: A proposal for multiple objective particle swarm optimization. Paper presented at the Proceedings of the 2002 Congress on Evolutionary Computation (CEC 2002).
Crainic, T. G., Mancini, S., Perboli, G., & Tadei, R. (2008). Clustering-based heuristics for the two-echelon vehicle routing problem. Montreal, Canada, Interuniversity Research Centre on Enterprise Networks, Logistics and Transportation, 17, 26.
Crainic, T. G., Sforza, A., & Sterle, C. (2011). Tabu search heuristic for a two-echelon location-routing problem: CIRRELT.
Crainic, T. G., Storchi, G., & Ricciardi, N. (2007). Models for evaluating and planning city logistics transportation systems: CIRRELT.
Dukkanci, O., Kara, B. Y., & Bektaş, T. (2019). The green location-routing problem. Computers & Operations Research, 105, 187-202.
Dalfard, V. M., Kaveh, M., & Nosratian, N. E. (2013). Two meta-heuristic algorithms for two-echelon location-routing problem with vehicle fleet capacity and maximum route length constraints. Neural Computing and Applications, 23(7-8), 2341-2349.
Deb, K., Agrawal, S., Pratap, A., & Meyarivan, T. (2000). A fast elitist non-dominated sorting genetic algorithm for multi-objective optimization: NSGA-II. Paper presented at the International Conference on Parallel Problem Solving From Nature.
Demircan-Yildiz, E. A., Karaoglan, I., & Altiparmak, F. (2016). Two Echelon Location Routing Problem with Simultaneous Pickup and Delivery: Mixed Integer Programming Formulations and Comparative Analysis. Paper presented at the International Conference on Computational Logistics.
Drexl, M., & Schneider, M. (2015). A survey of variants and extensions of the location-routing problem. European journal of operational research, 241(2), 283-308.
Eberhart, R., & Kennedy, J. (1995). A new optimizer using particle swarm theory In: Proceedings of the sixth international symposium on micro machine and human science, vol 43 IEEE. New York.
Eberhart, R., & Kennedy, J. (1995). Particle swarm optimization, proceeding of IEEE International Conference on Neural Network. Perth, Australia, 1942-1948.
Eberhart, R., Simpson, P., & Dobbins, R. (1996). Computational Intelligence PC Tools. In: Academic Press Professional, Inc.
Farham, M. S., Süral, H., & Iyigun, C. (2018). A column generation approach for the location-routing problem with time windows. Computers & Operations Research, 90, 249-263.
Farrokhi-Asl, H., Tavakkoli-Moghaddam, R., Asgarian, B., & Sangari, E. (2017). Metaheuristics for a bi-objective location-routing-problem in waste collection management. Journal of Industrial and Production Engineering, 34(4), 239-252.
Gonzalez-Feliu, J., Perboli, G., Tadei, R., & Vigo, D. (2008). The two-echelon capacitated vehicle routing problem.
Hadian, H., Golmohammadi, A., Hemmati, A., & Mashkani, O. (2019). A multi-depot location routing problem to reduce the differences between the vehicles’ traveled distances; a comparative study of heuristics. Uncertain Supply Chain Management, 7(1), 17-32.
Hassanzadeh, A., Mohseninezhad, L., Tirdad, A., Dadgostari, F., & Zolfagharinia, H. (2009). Location-routing problem. In Facility Location (pp. 395-417): Springer.
Jacobsen, S. K., & Madsen, O. B. (1980). A comparative study of heuristics for a two-level routing-location problem. European journal of operational research, 5(6), 378-387.
Kuhn, H. W. (1955). The Hungarian method for the assignment problem. Naval Research Logistics (NRL), 2(1‐2), 83-97.
Lan, Y.-h., & Li, Y.-s. (2010). The method of cluster and entropy apply in city distribution center location. Paper presented at the Educational and Network Technology (ICENT), 2010 International Conference on.
Laporte, G., & Nobert, Y. (1981). An exact algorithm for minimizing routing and operating costs in depot location. European journal of operational research, 6(2), 224-226.
Martínez-Salazar, I. A., Molina, J., Ángel-Bello, F., Gómez, T., & Caballero, R. (2014). Solving a bi-objective transportation location routing problem by metaheuristic algorithms. European journal of operational research, 234(1), 25-36.
Nagy, G., & Salhi, S. (2007). Location-routing: Issues, models and methods. European journal of operational research, 177(2), 649-672.
Nguyen, V.-P., Prins, C., & Prodhon, C. (2010). A Multi-Start Evolutionary Local Search for the Two-Echelon Location Routing Problem. Hybrid Metaheuristics, 6373, 88-102.
Nikbakhsh, E., & Zegordi, S. (2010). A heuristic algorithm and a lower bound for the two-echelon location-routing problem with soft time window constraints. Scientia Iranica. Transaction E, Industrial Engineering, 17(1), 36.
Or, I., & Pierskalla, W. P. (1979). A transportation location-allocation model for regional blood banking. AIIE transactions, 11(2), 86-95.
Peng, Y. (2008). Integrated Location-Routing Problem Modeling and GA Algorithm Solving. Paper presented at the Intelligent Computation Technology and Automation (ICICTA), 2008 International Conference on.
Perboli, G., & Tadei, R. (2010). New families of valid inequalities for the two-echelon vehicle routing problem. Electronic notes in discrete mathematics, 36, 639-646.
Punyim, P., Karoonsoontawong, A., Unnikrishnan, A., & Xie, C. (2018). Tabu search heuristic for joint location-inventory problem with stochastic inventory capacity and practicality constraints. Networks and Spatial Economics, 18(1), 51-84.
Rabbani, M., Danesh Shahraki, S., Farrokhi-Asl, H., & Lim, F. W. (2018). A new multi-objective mathematical model for hazardous waste management considering social and environmental issues. Iranian Journal of Management Studies, 11(4), 823-859.
Rabbani, M., Farrokhi-Asl, H., & Ameli, M. (2016). Solving a fuzzy multi-objective products and time planning using hybrid meta-heuristic algorithm: Gas refinery case study. Uncertain Supply Chain Management, 4(2), 93-106.
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.
Rabbani, M., Heidari, R., Farrokhi-Asl, H., & Rahimi, N. (2018). Using metaheuristic algorithms to solve a multi-objective industrial hazardous waste location-routing problem considering incompatible waste types. Journal of Cleaner Production170, 227-241.
Rahmani, Y., Cherif-Khettaf, W. R., & Oulamara, A. (2015). A local search approach for the two–echelon multi-products location–routing problem with pickup and delivery. IFAC-PapersOnLine, 48(3), 193-199.
Rahmani, Y., Oulamara, A., & Cherif, W. R. (2013). Multi-products Location-Routing problem with Pickup and Delivery: Two-Echelon model. IFAC Proceedings Volumes, 46(7), 198-203.
Schwengerer, M., Pirkwieser, S., & Raidl, G. R. (2012). A Variable Neighborhood Search Approach for the Two-Echelon Location-Routing Problem. Paper presented at the EvoCOP.
Starkweather, T., McDaniel, S., Mathias, K. E., Whitley, L. D., & Whitley, C. (1991). A Comparison of Genetic Sequencing Operators. Paper presented at the ICGA.
Zitzler, E., Laumanns, M., & Thiele, L. (2001). SPEA2: Improving the strength Pareto evolutionary algorithm.
Zitzler, E., & Thiele, L. (1999). Multiobjective evolutionary algorithms: a comparative case study and the strength Pareto approach. IEEE transactions on Evolutionary Computation, 3(4), 257-271.