Hybrid Evolutionary Approach with the Jaya Algorithm for the Multiobjective Patrolling Problem

Authors

  • Fumito Kudo Department of Life Science and Informatics, Graduate School of Engineering, Maebashi Institute of Technology, Maebashi, Gunma, Japan.
  • Muneaki Ohshima Department of Communication, Ikuei Junior College, Takasaki, Gunma, Japan.
  • Takeru Yamanaka Department of Life Science and Informatics, Graduate School of Engineering, Maebashi Institute of Technology, Maebashi, Gunma, Japan.
  • Hiroaki Tohyama Department of Life Engineering, Faculty of Engineering, Maebashi Institute of Technology, Maebashi, Gunma, Japan.
  • Masaki Tomisawa * Department of Life Engineering, Faculty of Engineering, Maebashi Institute of Technology, Maebashi, Gunma, Japan. https://orcid.org/0009-0007-5485-6006

https://doi.org/10.48314/ijorai.v2i2.93

Abstract

Routing optimization is crucial for many real-world applications, such as urban security, infrastructure inspection, and logistics. Many of these problems can be formulated as Arc Routing Problems (ARPs) on complex transportation networks. Building on our previous studies, we consider the Police Officer Patrol Problem (POPP) and its extension, the Generalized POPP (GPOPP), a bi-objective optimization problem defined on mixed graphs. The GPOPP aims to minimize patrol route length while maximizing the coverage of the guarded area, where patrol officers can visually confirm adjacent streets without physically traversing them.
However, solving the GPOPP efficiently remains challenging for two main reasons. First, conventional route operators developed for node-routing problems often produce infeasible solutions when applied to arc-routing contexts. Second, existing hybrid evolutionary approaches typically require repeated route modifications, resulting in high computational overhead and exhibit sensitivity to parameter settings.
To address these issues, this study proposes an improved hybrid evolutionary framework that integrates evolutionary computation with the Jaya algorithm. The proposed method introduces three key components:
1) a Connectivity-Based Mutation (CBM) operator designed to maintain feasible route structures in mixed graphs while generating diverse solutions, 2) a decomposed Jaya algorithm that improves search efficiency by focusing on a single objective at a time, and 3) a Fuzzy Logic Controller (FLC) that dynamically adjusts mutation and crossover probabilities.
Extensive numerical experiments using benchmark problems derived from the Mixed Rural Postman Problem (MRPP) demonstrate that the proposed method consistently outperforms both the existing hybrid method and NSGA-II in terms of solution quality and computational efficiency.

Keywords:

Arc routing problem, Police officer patrolling problem, Evolutionary algorithms, MoEA-HSS, Jaya algorithm, Fuzzy logic control

References

  1. [1] Beke, L., Uribe, L., Lara, A., Artemio Coello Coello, C., Weiszer, M., Burke, E. K., & Chen, J. (2024). Routing and scheduling in
  2. [2] multigraphs with time constraints—a memetic approach for airport ground movement. IEEE Transactions on evolutionary
  3. [3] computation, 28(2), 474–488. https://doi.org/10.1109/TEVC.2023.3262743
  4. [4] Wu, R., Wang, R., Hao, Jie., Wu, Q., Wang, P., & Niyato, D. (2025). Multiobjective vehicle routing optimization with
  5. [5] time windows: A hybrid approach using deep reinforcement learning and NSGA-II. IEEE transactions on intelligent transportation systems, 26(3), 4032–4047. https://doi.org/10.1109/TITS.2024.3515997
  6. [6] Zhao, W., Bian, X., & Mei, X. (2024). An adaptive multiobjective genetic algorithm for solving heterogeneous green city
  7. [7] vehicle routing problem. Multidisciplinary digital publishing institute , 14(15), 6594. https://doi.org/10.3390/app14156594
  8. [8] Dutta, J., Barma, P. S., Mukherjee, A., Kar, S., De, T., Pamučar, D., ... & Garbinčius, G. (2021). Multi-objective green
  9. [9] mixed vehicle routing problem under rough environment. Transport, 37(1), 51-63..
  10. [10] https://doi.org/10.3846/transport.2021.14464
  11. [11] Liu, Fei., Lu, C., Gui, L., Zhang, Q., Tong, X., & Yuan, M. (2023). Heuristics for vehicle routing problem: a survey and
  12. [12] recent advances. arXiv:2303.04147. https://doi.org/10.48550/arXiv.2303.04147
  13. [13] Potvin, J.-Y. (2009). State-of-the art review—evolutionary algorithms for vehicle routing. INFORMS Journal on Computing,
  14. [14] (4), 518–548. https://doi.org/10.1287/ijoc.1080.0312
  15. [15] Gendreau, M., Potvin, J. Y., Bräumlaysy, O., Hasle, G., & Løkketangen, A. (2008). Metaheuristics for the vehicle routing problem and
  16. [16] its extensions: A categorized bibliography. In The vehicle routing problem: latest advances and new challenges (pp. 143-169). Boston, MA: Springer US.
  17. [17] https://doi.org/10.1007/978-0-387-77778-8_7
  18. [18] Ochelska-Mierzejewska, J., Poniszewska-Marańda, A., & Marańda, W. (2021). Selected genetic algorithms for vehicle
  19. [19] routing problem solving. Electronics, 10(24), 3147. https://doi.org/10.3390/electronics10243147
  20. [20] Lacomme, P., Prins, C., & Tanguy, A. (2004, September). First competitive ant colony scheme for the CARP. In international workshop on
  21. [21] ant colony optimization and swarm intelligence (pp. 426-427). Berlin, Heidelberg: Springer Berlin Heidelberg. https://doi.org/10.1007/978-3-540-28646-2_48
  22. [22] Pavai, G., & Geetha, T. V. (2016). A survey on crossover operators.ACM computing surveys (CSUR), 49(4), 1-43.
  23. [23] https://doi.org/10.1145/3009966
  24. [24] Alorf, A. (2023). A survey of recently developed metaheuristics and their comparative analysis. Engineering applications of artificial
  25. [25] intelligence, 117, 105622. https://doi.org/10.1016/j.engappai.2022.105622
  26. [26] Li, Q., Liu, S., Chen, W., Zou, J., Tang, K., & Yao, X. (2025). Knowledge-Guided memetic algorithm for capacitated arc routing
  27. [27] problems with time-dependent service costs. arXiv preprint arXiv:2507.21740. https://doi.org/10.48550/arXiv.2507.21740
  28. [28] Sobhanan, A., Charkhgard, H., & Kwon, C. (2025). Arc Routing Problems with Multiple Trucks and Drones: A Hybrid Genetic
  29. [29] Algorithm. arXiv preprint arXiv:2508.18105. https://doi.org/10.48550/arXiv.2508.18105
  30. [30] Rao, R. (2016). Jaya: A simple and new optimization algorithm for solving constrained and unconstrained optimization
  31. [31] problems. International journal of industrial engineering computations, 7(1), 19-34. https://doi.org/10.5267/j.ijiec.2015.8.004
  32. [32] Gao, K., Zhang, Y., Sadollah, A., & Su, R. (2016, November). Jaya algorithm for solving urban traffic signal control problem. In 2016
  33. [33] th international conference on control, automation, robotics and vision (ICARCV) (pp. 1-6). IEEE. https://doi.org/10.1109/ICARCV.2016.7838661 [16] Gunduz, M., & Aslan, M. (2021). DJAYA: A discrete Jaya algorithm for solving traveling salesman problem. Applied soft computing, 105,
  34. [34] https://doi.org/10.1016/j.asoc.2021.107275
  35. [35] Wang, R., Zhou, M., Wang, J., & Gao, K. (2023). An improved discrete Jaya algorithm for shortest path problems in transportation-
  36. [36] related processes. Processes, 11(8), 2447. https://doi.org/10.3390/pr11082447
  37. [37] Xu, J., Hu, W., Gu, W., & Yu, Y. (2023). A discrete jaya algorithm based on reinforcement learning and simulated annealing for the
  38. [38] traveling salesman problem. Mathematics, 11(14), 3221. https://doi.org/10.3390/math11143221
  39. [39] Zhang, J., Ye, J. X., Lin, J., & Song, H. B. (2024). A discrete Jaya algorithm for vehicle routing problems with uncertain
  40. [40] demands. Systems science & control engineering, 12(1), 2350165. https://doi.org/10.1080/21642583.2024.2350165
  41. [41] Bajaj, A., & Dhodiya, J. (2025). Multi-Route Multi-Objective TSP: mathematical model and its solution by reference point and
  42. [42] aspiration level-based MOQO Jaya algorithm. Neural computing and applications, 37(16), 10243-10285. https://doi.org/10.1007/s00521-025-11029-4
  43. [43] Katoch, S., Chauhan, S. S., & Kumar, V. (2021). A review on genetic algorithm: past, present, and future. Multimedia tools and
  44. [44] applications, 80(5), 8091-8126. https://doi.org/10.1007/s11042-020-10139-6
  45. [45] Mosayebi, M., & Sodhi, M. (2020, July). Tuning genetic algorithm parameters using design of experiments. In Proceedings of the 2020
  46. [46] genetic and evolutionary computation conference companion (pp. 1937-1944). https://doi.org/10.1145/3377929.3398136
  47. [47] Mills, K. L., Filliben, J. J., & Haines, A. L. (2015). Determining relative importance and effective settings for genetic algorithm control
  48. [48] parameters. Evolutionary computation, 23(2), 309-342. https://doi.org/10.1162/EVCO_a_00137
  49. [49] Lin, W. Y., Lee, W. Y., & Hong, T. P. (2003). Adapting crossover and mutation rates in genetic algorithms. Journal of information science
  50. [50] and engineering, 19(5), 889-903. https://doi.org/10.1688/JISE.2003.19.5.10
  51. [51] Hassanat, A., Almohammadi, K., Alkafaween, E. A., Abunawas, E., Hammouri, A., & Prasath, V. S. (2019). Choosing mutation and
  52. [52] crossover ratios for genetic algorithms—a review with a new dynamic approach. Information, 10(12), 390. https://doi.org/10.3390/info10120390
  53. [53] Altiparmak, F., Gen, M., Dengiz, B., & Smith, A. E. (2004). A genetic algorithm with fuzzy logic controller for design of
  54. [54] communication networks. IEEJ transactions on electronics, information and systems, 124(10), 1979-1985. https://doi.org/10.1541/ieejeiss.124.1979
  55. [55] Vannucci, M., Colla, V., & Dettori, S. (2016). Fuzzy adaptive genetic algorithm for improving the solution of industrial optimization
  56. [56] problems. IFAC-PapersOnLine, 49(12), 1128-1133. https://doi.org/10.1016/j.ifacol.2016.07.650
  57. [57] Pytel, K. (2025). Fuzzy logic applied to tunning mutation size in evolutionary algorithms. Scientific reports, 15(1), 1937.
  58. [58] https://doi.org/10.1038/s41598-025-86349-5
  59. [59] Tohyama, H., & Tomisawa, M. (2022). Complexity of the police officer patrol problem. Journal of information processing, 30, 307-314.
  60. [60] https://doi.org/10.2197/ipsjjip.30.307
  61. [61] Tomisawa, M., & Tohyama, H. (2024). Computational complexity of the police officer patrol
  62. [62] problem on weighted digraphs. Electronic Journal of graph theory & applications, 12(2). 297–313. https://doi.org/10.5614/ejgta.2024.12.2.10
  63. [63] Kudo, F., Tohyama, H., & Tomisawa, M. (2025). Hybrid heuristic approach for generalized
  64. [64] police officer patrolling problem. Frontiers in industrial engineering, 3, 1620422. https://doi.org/10.3389/fieng.2025.1620422
  65. [65] Zhang, W., Gen, M., & Jo, J. (2014). Hybrid sampling strategy-based multiobjective evolutionary algorithm for process planning and scheduling problem. Journal of intelligent manufacturing, 25(5), 881-897. https://doi.org/10.1007/s10845-013-0814-2
  66. [66] Schaffer, J. D. (2014, January). Multiple objective optimization with vector evaluated genetic
  67. [67] algorithms. In Proceedings of the first international conference on genetic algorithms and their applications (pp.
  68. [68] -100). Psychology Press.
  69. [69] https://www.taylorfrancis.com/chapters/edit/10.4324/9781315799674-9/multiple-objective-optimization-vector-evaluated-genetic-algorithms-david-schaffer
  70. [70] Deb, K., Pratap, A., Agarwal, S., & Meyarivan, T. A. M. T. (2002). A fast and elitist multiobjective genetic
  71. [71] algorithm: NSGA-II. IEEE transactions on evolutionary computation, 6(2), 182-
  72. [72] https://doi.org/10.1109/4235.996017
  73. [73] Zitzler, E., & Thiele, L. (1999). Multiobjective evolutionary algorithms: a comparative case study
  74. [74] and the strength Pareto approach. IEEE transactions on Evolutionary Computation, 3(4), 257-271. https://doi.org/10.1109/4235.797969
  75. [75] Coello Coello, C. A., & Reyes Sierra, M. (2004, April). A study of the parallelization of a coevolutionary multi-objective evolutionary algorithm. In Mexican international conference on artificial intelligence (pp. 688-697). Berlin, Heidelberg: Springer Berlin Heidelberg. https://doi.org/10.1007/978-3-540-24694-7_71

Downloads

Published

2026-06-19

Issue

Vol. 2 No. 2 (2026): International Journal of Operations Research and Artificial Intelligence (IJORAI)

Section

Articles

License

Copyright (c) 2026 International Journal of Operations Research and Artificial Intelligence (IJORAI)

Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 International License.

How to Cite

Kudo, F. ., Ohshima, M. ., Yamanaka, T. ., Tohyama, H. ., & Tomisawa, M. . (2026). Hybrid Evolutionary Approach with the Jaya Algorithm for the Multiobjective Patrolling Problem. International Journal of Operations Research and Artificial Intelligence , 2(2), 108-132. https://doi.org/10.48314/ijorai.v2i2.93

Similar Articles

11-16 of 16

You may also start an advanced similarity search for this article.