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

Authors

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

Abstract

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.

Keywords

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, https://doi.org/10.1007/978-3-319-66963-2_45.
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, https://doi.org/10.1016/j.eswa.2016.01.038.
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, https://doi.org/10.1016/j.cie.2017.10.032.
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, https://doi.org/10.1016/j.orhc.2017.06.001.
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, https://doi.org/10.1504/IJPM.2018.092766.
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, https://doi.org/10.1016/j.orhc.2018.01.004.
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, https://doi.org/10.1016/j.cor.2017.02.007.
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, https://doi.org/10.1016/j.ifacol.2015.06.164.
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, https://doi.org/10.1007/s00521-015-1901-4.
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, https://doi.org/10.1016/j.cie.2015.11.022.
Fikar, C., & Hirsch, P., 2017. Home health care routing and scheduling: A review. Computers & Operations Research77, pp.86-95, https://doi.org/10.1016/j.cor.2016.07.019.
Golden, B., Ball, M., & Bodin, L., 1981. Current and future research directions in network optimization. Computers & Operations Research8(2), pp.71-81, https://doi.org/10.1016/0305-0548(81)90035-6.
Hintsch, T., & Irnich, S., 2018. Large multiple neighborhood search for the clustered vehicle-routing problem. European Journal of Operational Research270(1), pp.118-131, https://doi.org/10.1016/j.ejor.2018.02.056.
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, https://doi.org/10.1016/j.eswa.2016.09.017.
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, https://doi.org/10.1016/j.eswa.2009.09.005.
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, https://doi.org/10.1016/j.ejor.2013.04.044.
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, https://doi.org/10.1007/978-3-319-19644-2_56.
Mestria, M., 2018. New hybrid heuristic algorithm for the clustered traveling salesman problem. Computers & Industrial Engineering116, pp.1-12, https://doi.org/10.1016/j.cie.2017.12.018.
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, https://doi.org/10.1016/j.ejor.2018.01.035.
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, https://doi.org/10.1016/j.swevo.2018.04.001.
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, https://doi.org/10.1016/j.ejor.2014.10.010.
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, https://doi.org/10.1016/j.cie.2017.11.018.
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, https://doi.org/10.1016/j.jclepro.2017.09.029.
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, https://doi.org/10.1016/j.eswa.2018.02.025.
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, https://doi.org/10.1016/j.apm.2017.02.005.
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, https://doi.org/10.1016/j.cie.2015.02.005.
Zitzler, E., 1999. Evolutionary algorithms for multiobjective optimization: Methods and applications (Vol. 63). Ithaca: Shaker.