Immune-based evolutionary algorithm for determining the optimal sequence of multiple disinfection operations

Document Type : Article


1 Department of Industrial Management, National Formosa University, Huwei, Yunlin 632, Taiwan.

2 Department of Information Management, National Chung Cheng University, Chia-Yi 621, Taiwan.

3 Department of Business Administration, National ChiaYi University, Chia-Yi 600, Taiwan.


This paper presents a new multiple disinfection operation problem (MDOP) in which several buildings have to be sprayed with various disinfectants. The MDOP seeks to minimize the total cost of disinfection operations for all buildings. The problem is different from the typical vehicle routing problem since: (a) each building has to receive multiple spray applications of disinfectants; (b) the final spray application of disinfectant in each building is fixed; and (c) for safety, the time interval between two consecutive spray applications of disinfectants for each building must meet or exceed a specified minimum. The MDOP problem is NP-hard and difficult to solve directly. In this paper, we firstly develop an efficient encoding of spray operations to simultaneously determine the optimal sequence of buildings and their respective treatments with spray disinfectants. Secondly, we adopt immune algorithm to solve the presented MDOP. Finally, as a demonstration of our method, we solve the problem for a campus case to determine the optimal disinfection strategy and routes assuming both single and multiple vehicle scenarios. Numerical results of immune algorithm are discussed and compared with those of genetic algorithm and PSO to show the effectiveness of the adopted algorithm.


Main Subjects

1. Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G.,  and Shmoys, D.B., The Traveling Salesman Problem:  A Guided Tour of Combinatorial Optimization, John  Wiley & Sons (1985).  2. Gutin, G. and Punnen, A.P., The Traveling Salesman  Problem and Its Variations, Springer (2006).  3. Cook, W., In Pursuit of the Traveling Salesman:  Mathematics at the Limits of Computation, Princeton  University Press (2011).  4. Toth, P. and Vigo, D., The Vehicle Routing Problem,  Philadelphia: SIAM (2001).  5. Oliveira, H.C.B. and Vasconcelos, G.C. A hybrid  search method for the vehicle routing problem  with time windows", Annals of Operations Research,  180(1), pp. 125-144 (2008).  6. Pillac, V., Gendreau, M., Gu_eret, C., and Medaglia,  A.L. A review of dynamic vehicle routing problems",  European Journal of Operational Research, 225(1), pp.  1-11 (2013).  7. Beltrami, E.J. and Bodin, L.D. Networks and vehicle  routing for municipal waste collection", Networks,  4(1), pp. 65-94 (1974).  8. Francis, P.M., Smilowitz, K.R., and Tzur, M. The  period vehicle routing problem and its extensions",  (book series) Operations Research/Computer Science  Interfaces, 43, pp. 73-102 (2008).  9. Mourgaya, M. and Vanderbeck, F. The periodic  vehicle routing problem: classi_cation and heuristic",  RAIRO - Operations Research, 40(2), pp. 169-194  (2006).  10. Nguyen, P.K., Crainic, T.G., and Toulouse, M. Hybrid  generational genetic algorithm for the periodic  vehicle routing problem with time windows", Journal  of Heuristics, 20(4), pp. 383-416 (2014).  11. Michallet, J., Prins, C., Amodeo, L., Yalaoui, F., and  Vitry, G. Multi-start iterated local search for the  periodic vehicle routing problem with time windows  and time spread constraints on services", Computers  & Operations Research, 41, pp. 196-207 (2014).  12. Ko_c, C_ . A uni_ed-adaptive large neighborhood search  metaheuristic for periodic location-routing problems",  Transportation Research Part C, 68, pp. 265-284  (2016).  13. Lim, W.C.E., Kanagaraj, G., and Ponnambalam, S.G.  A hybrid cuckoo search-genetic algorithm for holemaking  sequence optimization", Journal of Intelligent  Manufacturing, 27(2), pp. 417-429 (2016).  14. Dalavi, A.M., Pawar, P.J., and Singh, T.P. Tool  path planning of hole-making operations in ejector  plate of injection mould using modi_ed shu_ed frog  leaping algorithm", Journal of Computational Design  and Engineering, 3, pp. 266-273 (2016).  15. Dalavi, A.M., Pawar, P.J., Singh, T.P., Warke, A.S.,  and Paliwal, P.D. Review on optimization of holemaking  operations for injection mould using nontraditional  algorithms", International Journal of Industrial  Engineering and Management, 7(1), pp. 9-14  (2016).  16. Solimanpur, M., Foroughi, A., and Mohammadi,  M. Optimum route selection in hole-making operations  using a dynamic programming-based method",  Cogent Engineering, 3, Article 1201991 (2016). .1201991  17. Garey, M.R. and Johnson, D.S., Computers and  Intractability: A Guide to the Theory of NPCompleteness,  Macmillan (1979).  18. Mirjalili, S. and Lewis, A. The whale optimization  algorithm", Advances in Engineering Software, 95, pp.  51-67 (2016).  19. Li, Z., Mobin, M., and Keyser, T. Multi-objective and  multi-stage reliability growth planning in early product  development stage", IEEE Transaction on Reliability,  65, pp. 769-781 (2016).  20. Tavana, M., Li, Z., Mobin, M., Komaki, M., and  Teymurian, E. Multi-objective design of control chart  optimization using NSGA-III and MOPSO enhanced  with DEA and TOPSIS", Expert System with Applications,  50, pp. 17-39 (2016).  21. Tavana, M., Kazemi, M.R., Vafadarnikjoo, A., and  Mobin, M. An arti_cial immune algorithm for ergonomic  product classi_cation using anthropometric  measurements", Measurement, 94, pp. 621-629 (2016).  22. Weissman, I.L. and Cooper, M.D. How the immune  system develops", Scienti_c American, 269, pp. 33-40  (1993).  23. Huang, S.J. Enhancement of thermal unit commitment  using immune algorithms based optimization  approaches", Electrical Power & Energy Systems, 21,  pp. 245-252 (1999).  24. Hsieh, Y.C. and You, P.S. An e_ective immune  based two-phase approach for the optimal reliabilityredundancy  allocation problem", Applied Mathematics  and Computation, 218, pp. 1297-1307 (2011).  25. Hsieh, Y.C. and You, P.S. An immune evolutionary  approach for the label printing problem", International  Journal of Computational Intelligence Systems, 7(3),  pp. 515-523 (2014).  26. Michalewicz, Z., Genetic Algorithm + Data Structures  = Evolution Programs, Springer-Verlag, New York  (1994).  27. Kennedy, J. and Eberhart, R., Particle swarm optimization",  Proceedings of IEEE International Conference  on Neural Networks, IV, pp. 1942-1948 (1995).  28. Chen, W. and Zhang, J. A novel set-based particle  swarm optimization method for discrete optimization  problem", IEEE Transactions on Evolutionary Computation,  14(2), pp. 278-300 (2010).  29. Eberhart, R.C., Hu, X., and Shi, Y. Particle swarm  with extended memory for multiobjective optimization",  IEEE International Conference on Swarm Intelligence  Symposium, pp. 193-197 (2003).