Solving a bi-objective medicine distribution problem considering delivery to waste center using a hybrid clustering, mathematical modeling and NSGA-II approach

Document Type : Research Paper


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


Proper transportation and distribution of commodities plays a pivotal role in the expenditures of supply chains. In this paper, a clustered vehicle routing problem with pick-up and delivery is studied. A fleet of distinct vehicles is concurrently responsible for distribution of medicines and collection of their wastes. Collected wastes should be sent to a waste center. To solve the problem, a bi-objective mathematical model is presented. Fairness of travelled distances among drivers and transportation expenses are two objective functions considered in the model. Since the proposed problem is NP-hard, a three-step hybrid approach is developed to solve the problem. First, K-medoids clustering algorithm allocates customers to subsets based on their coordinates. Second, a mathematical model is used for routing vehicles within each cluster. Third, NSGA-II is used to produce final result using the outcome of step 2. Extensive numerical results indicate the superiority of the proposed approach against the NSGA-II.


Main Subjects

Abdi, A., Abdi, A., Akbarpour, N., Amiri, A. S., & Hajiaghaei-Keshteli, M. (2020). Innovative approaches to design and address green supply chain network with simultaneous pick-up and split delivery. Journal of Cleaner Production, 250, 119437.
Aguirre-Gonzalez, E. J., & Villegas, J. G., 2017, September. A Two-Phase Heuristic for the Collection of Waste Animal Tissue in a Colombian Rendering Company. In Workshop on Engineering Applications (pp.511-521). Springer, Cham,
Asghari, M., & Al-e, S. M. J. M. (2020). A green delivery-pickup problem for home hemodialysis machines; sharing economy in distributing scarce resources. Transportation Research Part E: Logistics and Transportation Review, 134, 101815.
Avci, M., & Topaloglu, S., 2016. A hybrid metaheuristic algorithm for heterogeneous vehicle routing problem with simultaneous pickup and delivery. Expert Systems with Applications53, pp.160-171,
Belgin, O., Karaoglan, I., & Altiparmak, F., 2018. Two-echelon vehicle routing problem with simultaneous pickup and delivery: Mathematical model and heuristic approach. Computers & Industrial Engineering115, pp.1-16,
Cissé, M., Yalçındağ, S., Kergosien, Y., Şahin, E., Lenté, C., & Matta, A., 2017. OR problems related to Home Health Care: A review of relevant routing and scheduling problems. Operations Research for Health Care13, pp.1-22,
Comert, S. E., Yazgan, H. R., Kır, S., & Yener, F., 2018. A cluster first-route second approach for a capacitated vehicle routing problem: a case study. International Journal of Procurement Management11(4), pp.399-419,
Decerle, J., Grunder, O., El Hassani, A. H., & Barakat, O., 2018. A memetic algorithm for a home health care routing and scheduling problem. Operations research for health care16, pp.59-71,
Defryn, C., & Sörensen, K., 2017. A fast two-level variable neighborhood search for the clustered vehicle routing problem. Computers & Operations Research83, pp.78-94,
En-nahli, L., Allaoui, H., & Nouaouri, I., 2015. A multi-objective modelling to human resource assignment and routing problem for home health care services. IFAC-PapersOnLine48(3), pp.698-703,
Ewbank, H., Wanke, P., & Hadi-Vencheh, A., 2016. An unsupervised fuzzy clustering approach to the capacitated vehicle routing problem. Neural Computing and Applications27(4), pp.857-867,
Expósito-Izquierdo, C., Rossi, A., & Sevaux, M., 2016. A two-level solution approach to solve the clustered capacitated vehicle routing problem. Computers & Industrial Engineering91, pp.274-289,
Fikar, C., & Hirsch, P., 2017. Home health care routing and scheduling: A review. Computers & Operations Research77, pp.86-95,
Golden, B., Ball, M., & Bodin, L., 1981. Current and future research directions in network optimization. Computers & Operations Research8(2), pp.71-81,
Hintsch, T., & Irnich, S., 2018. Large multiple neighborhood search for the clustered vehicle-routing problem. European Journal of Operational Research270(1), pp.118-131,
Kalayci, C. B., & Kaya, C., 2016. An ant colony system empowered variable neighborhood search algorithm for the vehicle routing problem with simultaneous pickup and delivery. Expert Systems with Applications66, pp.163-175,
Karimi, N., Zandieh, M., & Karamooz, H. R., 2010. Bi-objective group scheduling in hybrid flexible flowshop: a multi-phase approach. Expert Systems with Applications37(6), pp.4024-4032,
Liu, R., Xie, X., Augusto, V., & Rodriguez, C., 2013. Heuristic algorithms for a vehicle routing problem with simultaneous delivery and pickup and time windows in home health care. European Journal of Operational Research230(3), pp.475-486,
Ma, Y., Li, Z., Yan, F., & Feng, C. (2019). A hybrid priority-based genetic algorithm for simultaneous pickup and delivery problems in reverse logistics with time windows and multiple decision-makers. Soft Computing, 23(15), 6697-6714.
Marc, A. H., Fuksz, L., Pop, P. C., & Dănciulescu, D., 2015, June. A novel hybrid algorithm for solving the clustered vehicle routing problem. In International Conference on Hybrid Artificial Intelligence Systems (pp.679-689). Springer, Cham,
Mestria, M., 2018. New hybrid heuristic algorithm for the clustered traveling salesman problem. Computers & Industrial Engineering116, pp.1-12,
Naccache, S., Côté, J. F., & Coelho, L. C., 2018. The multi-pickup and delivery problem with time windows. European Journal of Operational Research269(1), pp.353-362,
Osaba, E., Yang, X. S., Fister Jr, I., Del Ser, J., Lopez-Garcia, P., & Vazquez-Pardavila, A. J., 2019. A discrete and improved bat algorithm for solving a medical goods distribution problem with pharmacological waste collection. Swarm and evolutionary computation44, pp.273-286,
Polat, O., Kalayci, C. B., Kulak, O., & Günther, H. O., 2015. A perturbation based variable neighborhood search heuristic for solving the vehicle routing problem with simultaneous pickup and delivery with time limit. European Journal of Operational Research242(2), pp.369-382,
Pop, P., & Chira, C., 2014, July. A hybrid approach based on genetic algorithms for solving the Clustered Vehicle Routing Problem. In 2014 IEEE Congress on Evolutionary Computation (CEC) (pp. 1421-1426). IEEE, 10.1109/CEC.2014.6900422.
Pop, P. C., Fuksz, L., Marc, A. H., & Sabo, C., 2018. A novel two-level optimization approach for clustered vehicle routing problem. Computers & Industrial Engineering115, pp.304-318,
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, pp.227-241,
Rabbani, M., Manavizadeh, N., Boostani, A., & Aghamohamadi, S. (2020). A multi-objective model for the residential waste collection location-routing problem with time windows. Journal of Industrial and Systems Engineering12(4), 227-241.
Rabbani, M., Mokhtarzadeh, M., & Farrokhi-Asl, H. (2018). A New Mathematical Model for Designing a Municipal Solid Waste System Considering Environmentally Issues. International Journal of Supply and Operations Management5(3), 234-255.
Sayyah, M., Larki, H., & Yousefikhoshbakht, M. (2016). Solving the vehicle routing problem with simultaneous pickup and delivery by an effective ant colony optimization. Journal of Industrial Engineering and Management Studies3(1), 15-38.
Schott, J. R., 1995. Fault tolerant design using single and multicriteria genetic algorithm optimization (No. AFIT/CI/CIA-95-039). AIR FORCE INST OF TECH WRIGHT-PATTERSON AFB OH.
Shi, Y., Boudouh, T., Grunder, O., & Wang, D., 2018. Modeling and solving simultaneous delivery and pick-up problem with stochastic travel and service times in home health care. Expert Systems with Applications102, pp.218-233,
Shi, Y., Zhou, Y., Boudouh, T., & Grunder, O. (2020). A lexicographic-based two-stage algorithm for vehicle routing problem with simultaneous pickup–delivery and time window. Engineering Applications of Artificial Intelligence, 95, 103901.
Suo, X. S., Yu, X. Q., & Li, H. S., 2017. Subset simulation for multi-objective optimization. Applied Mathematical Modelling44, pp.425-445,
Wang, C., Mu, D., Zhao, F., & Sutherland, J. W., 2015. A parallel simulated annealing method for the vehicle routing problem with simultaneous pickup–delivery and time windows. Computers & Industrial Engineering, 83, pp.111-122,
Zitzler, E., 1999. Evolutionary algorithms for multiobjective optimization: Methods and applications (Vol. 63). Ithaca: Shaker.