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

Document Type : Article

Authors

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.

Abstract

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.

Keywords

Main Subjects

References

References:
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., Gueret, 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: classification 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. Koc, C . "A unified-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 modified shuffled 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).http://dx.doi.org/10.1080/23311916.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 artificial immune algorithm for ergonomic product classification using anthropometric measurements", Measurement, 94, pp. 621-629 (2016).
22. Weissman, I.L. and Cooper, M.D. "How the immune system develops", Scientific 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 effective 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).
Scientia Iranica
Volume 26, Issue 2 - Serial Number 2
Transactions on Industrial Engineering (E)
March and April 2019
Pages 959-974

Files

Share

How to cite

Statistics