Using Metaheuristic Algorithms Combined with Clustering Approach to Solve a Sustainable Waste Collection Problem

Document Type : Research Paper

Authors

1 School of Industrial Engineering, College of Engineering, University of Tehran

2 School of Industrial Engineering, Iran University of Science & Technology, Tehran, Iran

Abstract

Sustainability is a monumental issue that should be considered in designing a logistics system. In order to incorporate sustainability concepts in our study, a waste collection problem with economic, environmental, and social objective functions was addressed. The first objective function minimized overall costs of the system, including establishment of depots and treatment facilities. Addressing environmental concerns, greenhouse gases emission was minimized by the second objective function and the third one maximized distances between each customer and treatment facilities. Treatment facility is noxious for human health and should be located in the maximum distance from the urban area. Initially, the locations of depots and treatment facilities were determined. Then, heterogeneous vehicles started to collect waste from the location of each customer and take it to treatment facilities. The problem included two types of open and close routes. Moreover, each vehicle had a capacity restriction, servicing time, and route length. There were different types of waste and each vehicle had a different capacity for them. Three metaheuristic algorithms combined with clustering approach were proposed to look for the best solutions in rational time. The Non-dominated Sorting Genetic Algorithm-II (NSGA-II), improved Strength Pareto Evolutionary Algorithm (SPEA-II), and Multi-Objective Evolutionary Algorithm based on Decomposition (MOEA/D) were compared in terms of performance metrics. According to the results, NSGA-II outweighed other algorithms in the presented model.

Keywords


Akhtar, M., Hannan, M., A., Begum, R., A., Basri, H., & Scavino, E. (2017). Backtracking search algorithm in CVRP models for efficient solid waste collection and route optimization. Waste Management, 61, 117-128.
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.
Barreto, S., Ferreira, C., Paixao, J., & Santos, B., S. (2007). Using clustering analysis in a capacitated location-routing problem. European Journal of Operational Research, 179(3), 968-977.
Barth, M., Younglove, T., & Scora, G. (2005). Development of a Heavy-Duty Diesel Modal Emissions and Fuel Consumption Model. California Partners for Advanced Transportation Technology. UC Berkeley.
Braekers, K., Ramaekers, K., & Van Nieuwenhuyse, I. (2016). The vehicle routing problem: State of the art classification and review. Computers & Industrial Engineering, 99, 300-313.
Bula, G., A., Prodhon, C., F., Gonzalez, A., Afsar, H., M., & Velasco, N. (2017). Variable neighborhood search to solve the vehicle routing problem for hazardous materials transportation. Journal of Hazardous Materials, 324 (B), 472-480.
Ceselli, A., Righini, G., & Tresoldi, E. (2014). Combined location and routing problems for drug distribution. Discrete Applied Mathematics, 165, 130-145.
Chen, P., Golden, B., Wang, X., & Wasil, E. (2017). A novel approach to solve the split delivery vehicle routing problem. International Transactions in Operational Research, 24(1-2), 27-41.
Cheng, C., Yang, P., Qi, M., & Rousseau, L., M. (2017). Modeling a green inventory routing problem with a heterogeneous fleet. Transportation Research Part E: Logistics and Transportation Review, 97, 97-112.
Davis, P., & Ray, T. (1969). A branch‐bound algorithm for the capacitated facilities location problem. Naval Research Logistics (NRL), 16(3), 331-344.
Deb, K., Pratap, A., Agarwal, S., & Meyarivan, T. (2002). A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation, 6(2). 182-197.
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.
Gambella, C., Maggioni, F., & Vigo, D. (2019). A stochastic programming model for a tactical solid waste management problem. European Journal of Operational Research, 273(2), 684-694.
He, Z., G., Li, Q., & Fang, J. (2016). The Solutions and Recommendations for Logistics Problems in the Collection of Medical Waste in China. Procedia Environmental Sciences, 31, 447-456.
Kara, I., Laporte, G., & Bektas, T. (2004). A note on the lifted Miller–Tucker–Zemlin subtour elimination constraints for the capacitated vehicle routing problem. European Journal of Operational Research, 158(3): 793-795.
Kumar, R. S., Kondapaneni, K., Dixit, V., Goswami, A., Thakur, L., S., & Tiwari, M., K. (2016). Multi-objective modeling of production and pollution routing problem with time window: A self-learning particle swarm optimization approach. Computers & Industrial Engineering, 99, 29-40.
Laporte, G. (1992). The vehicle routing problem: An overview of exact and approximate algorithms. European Journal of Operational Research, 59(3), 345-358.
Mahmoudi, M., & Zhou, X. (2016). Finding optimal solutions for vehicle routing problem with pickup and delivery services with time windows: A dynamic programming approach based on state–space–time network representations. Transportation Research Part B: Methodological, 89, 19-42.
Mahmoudsoltani, F., Shahbandarzadeh, H., & Moghdani, R. (2018). Using Pareto-based multi-objective Evolution algorithms in decision structure to transfer the hazardous materials to safety storage centre. Journal of Cleaner Production, 184, 893-911.
Pecin, D., Contardo, C., Desaulniers, G., & Uchoa, E. (2017). New enhancements for the exact solution of the vehicle routing problem with time windows. INFORMS Journal on Computing, 29(3), 489-502.
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., Farrokhi-asl, H., & Rafiei, H. (2016). A hybrid genetic algorithm for waste collection problem by heterogeneous fleet of vehicles with multiple separated compartments. Journal of Intelligent & Fuzzy Systems, 30(3), 1817-1830.
Rabbani, M., Montazeri, M., Farrokhi-Asl, H., & Rafiei, H. (2016). A multi-objective genetic algorithm for a mixed-model assembly U-line balancing type-I problem considering human-related issues, training, and learning. Journal of Industrial Engineering International, 12(4), 485-497.
Samanlioglu, F. (2013). A multi-objective mathematical model for the industrial hazardous waste location-routing problem. European Journal of Operational Research, 226(2), 332-340.
Silvestrin, P., V., & Ritt, M., (2017). An iterated tabu search for the multi-compartment vehicle routing problem. Computers & Operations Research, 81, 192-202.
Todosijević, R., Hanafi, S., Urošević, D., Jarboui, B. & Gendron, B. (2017). A general variable neighborhood search for the swap-body vehicle routing problem. Computers & Operations Research, 78, 468-479.
Uchoa, E., Pecin, D., Pessoa, A., Poggi, M., Vidal, T., & Subramanian, A. (2017). New benchmark instances for the capacitated vehicle routing problem. European Journal of Operational Research, 257(3), 845-858.
Vincent, F., Y., Redi, A., P., Jewpanya, P., Lathifah, A., Maghfiroh, M., F., & Masruroh, N., A. (2019). A Simulated Annealing Heuristic for the Heterogeneous Fleet Pollution Routing Problem. In Environmental Sustainability in Asian Logistics and Supply Chains (pp. 171-204). Singapore: Springer.
Yin, P., Y., & Chuang, Y., L. (2016). Adaptive memory artificial bee colony algorithm for green vehicle routing with cross-docking. Applied Mathematical Modelling, 40(21–22), 9302-9315.
Yu, V., F., Redi, A., A., N., P., Hidayat, Y., A., & Wibowo, O., J. (2017). A simulated annealing heuristic for the hybrid vehicle routing problem. Applied Soft Computing, 53, 119-132.
Yu, V., F., Redi, A., A., N., P., Yang, C., L., Ruskartina, E., & Santosa, B. (2017). Symbiotic organisms search and two solution representations for solving the capacitated vehicle routing problem. Applied Soft Computing, 52, 657-672.
Zhang, Q., & Li, H. (2007). MOEA/D: A multiobjective evolutionary algorithm based on decomposition. IEEE Transactions on Evolutionary Computation, 11(6), 712-731.
Zhao, J., & Verter, V. (2015). A bi-objective model for the used oil location-routing problem. Computers & Operations Research, 62, 157-168.
Zitzler, E., Laumanns, M., and Thiele, L., (2001). SPEA2: Improving the strength Pareto evolutionary algorithm, Tik-report.