Adaptive Visitor Itinerary Optimization Under Temporal And Spatial Constraints: A Clustered MARL Approach For The Prophet's Mosque Precinct In Madinah
DOI:
https://doi.org/10.29284/67m0gz41Keywords:
multi-agent reinforcement learning; visitor itinerary optimization; K-means clustering; Prophet's Mosque; Madinah; temporal-spatial constraints; smart tourism; crowd management; deep Q-network; heritage site management.Abstract
Explore Routing Problem of Prophet Mosque Visitors Competition Background One of the busiest religious tourism destinations in the world is facing a surge in visitation. The precinct of Prophet's Mosque (Al-Masjid an-Nabawi) in Madinah city attracts millions of visitors every week, especially in the seasons of Hajj and Ramadan. Attracting such huge crowds has led to overcrowding and visitors not being able to fully enjoy their visits. In addition, current methods leave a lot to be desired in terms of schedule optimization. Scheduling methods that assign visits based on a set of rules or greedily solve each visitor's route independently do not consider the varying interests of each visitor, nor do they consider the temporal fluctuations of crowd density at each zone nor capacity constraints across zones. Methods Objective Proposed Method To address this problem, we propose a clustered multi-agent reinforcement learning approach that segments visitors into clusters, then utilizes five Deep Q-Learning agents to learn visit scheduling policies that are conditioned on the cluster they were segmented into. We first cluster visitors into 5 clusters using K-means. We then train 5 independent DQN agents which learn a policy to traverse a graph of 10 zones which includes Prophet's Mosque and its surrounding attractions. Results Our model was trained for 150 episodes and we observed that the average reward consistently increased from 34.6 to 41.9 per agent. In addition, we observed that epsilon started at 1.0 and gradually decreased to 0.48. We evaluated our model against Random, Greedy, and Round Robin agents and our results were competitive with them. We then used SHAP to find the features that affect the reward the most and we found that it was tourists rating in addition to the satisfaction score. We found that our clustered multi-agent RL agents covered more zones, had higher satisfaction per agent, and had a 100% rate of finishing episodes.
References
1. Abutaleb, K., El-Shimy, M., & Al-Mutairi, A. (2022). AI-based crowd monitoring and flow prediction at Al-Masjid al-Nabawi in Madinah. *Journal of Urban Technology*, 29(3), 45–67. https://doi.org/10.1080/10630732.2021.2001122
2. Ahmad, W., Ismail, H., & Razak, F. A. (2022). Ethical considerations in AI-driven pilgrimage management: Privacy, equity, and cultural sensitivity. *Journal of Islamic Tourism*, 4(1), 12–28. https://doi.org/10.1177/20551-622.2022
3. Al-Anezi, M. A. (2021). Visitor typology and satisfaction at the Prophet's Mosque: A survey-based analysis. *International Journal of Religious Tourism and Pilgrimage*, 9(2), 34–51. https://doi.org/10.21427/D7H4T3
4. Al-Hamarneh, A., & Steiner, C. (2004). Islamic tourism: Rethinking the strategies of tourism development in the Arab world after September 11, 2001. *Comparative Studies of South Asia, Africa and the Middle East*, 24(1), 173–182.
5. Al-Kodmany, K. (2021). Smart technology for Hajj and pilgrimage management: A literature review. *Sustainability*, 13(8), 4537. https://doi.org/10.3390/su13084537
6. Alegre, J., & Cladera, M. (2006). Repeat visitation in mature sun and sand holiday destinations. *Journal of Travel Research*, 44(3), 288–297.
7. Alotaibi, R., Bahaidara, A., & Al-Harbi, O. (2022). Deep learning-based crowd density estimation at Grand Mosque, Makkah. *IEEE Access*, 10, 54312–54325.
8. Brambilla, M., Ciavotta, M., & Facca, F. M. (2021). Combining multi-objective metaheuristics for tourist itinerary planning with real-time crowd data. *Expert Systems with Applications*, 170, 114539.
9. Busoniu, L., Babuska, R., & De Schutter, B. (2008). A comprehensive survey of multi-agent reinforcement learning. *IEEE Transactions on Systems, Man, and Cybernetics*, 38(2), 156–172.
10. Chen, X., Li, S., Liu, C., & Hu, X. (2020). Scalable multi-agent reinforcement learning for pedestrian crowd simulation with decentralised execution. *Transportation Research Part C*, 119, 102738.
11. Chu, T., Wang, J., Codeca, L., & Li, Z. (2020). Multi-agent deep reinforcement learning for large-scale traffic signal control. *IEEE Transactions on Intelligent Transportation Systems*, 21(3), 1086–1095.
12. Dolnicar, S. (2020). Vacation traveler market segmentation: Classic and new approaches. In J. J. Baggio & M. Pantano (Eds.), *Information and Communication Technologies in Tourism 2020* (pp. 23–41). Springer.
13. Feliciani, C., Corbetta, A., Haghani, M., & Nishinari, K. (2020). Trends in crowd accidents and the need for an international database of crowd-related incidents. *Safety Science*, 130, 104879.
14. Gama, F., Henriques, R., & Correia, L. (2022). Deep Q-learning for tourist itinerary recommendation with multi-site coverage. *Expert Systems with Applications*, 201, 117147.
15. Gavalas, D., Konstantopoulos, C., Mastakas, K., & Pantziou, G. (2014). A survey on algorithmic approaches for solving tourist trip design problems. *Journal of Heuristics*, 20(3), 291–328.
16. Gunawan, A., Lau, H. C., & Vansteenwegen, P. (2016). Orienteering problem: A survey of recent variants, solution approaches and applications. *European Journal of Operational Research*, 255(2), 315–332.
17. Guo, Y., Liu, H., Xu, K., & Chen, Z. (2022). Adaptive tourist itinerary optimisation with real-time crowd feedback using deep reinforcement learning. *Tourism Management*, 90, 104476.
18. Hassan, M. R., & Ramli, N. (2022). IoT-based indoor wayfinding and personalised route recommendation at Malaysian Islamic heritage corridors. *Journal of Heritage Tourism*, 17(4), 345–362.
19. Huybers, T. (2003). Modelling short-break holiday destination choices. *Tourism Economics*, 9(4), 389–405.
20. Kim, J., & Park, S. (2022). Multi-agent reinforcement learning for museum crowd redistribution across exhibition zones. *Computers in Human Behavior*, 135, 107347.
21. Lim, K. H., Chan, J., Leckie, C., & Karunasekera, S. (2018). Personalized trip recommendation for tourists based on user interests, points of interest visit durations and visit recency. *Knowledge and Information Systems*, 54(2), 375–406.
22. Liu, Z., Chen, H., Wang, Q., & Li, Y. (2022). Museum visitor routing optimisation using proximal policy optimisation under dynamic crowd conditions. *Information Sciences*, 614, 419–435.
23. Lloyd, S. P. (1982). Least squares quantization in PCM. *IEEE Transactions on Information Theory*, 28(2), 129–137.
24. Lowe, R., Wu, Y., Tamar, A., Harb, J., Abbeel, O. P., & Mordatch, I. (2017). Multi-agent actor-critic for mixed cooperative-competitive environments. *Advances in Neural Information Processing Systems*, 30, 6379–6390.
25. Marrese-Taylor, E., Velásquez, J. D., & Bravo-Marquez, F. (2021). A novel deterministic approach for aspect-based opinion mining in tourism products reviews. *Expert Systems with Applications*, 38(11), 14608–14622.
26. Mnih, V., Kavukcuoglu, K., Silver, D., Rusu, A. A., Veness, J., Bellemare, M. G., Graves, A., Riedmiller, M., Fidjeland, A. K., Ostrovski, G., Petersen, S., Beattie, C., Sadik, A., Antonoglou, I., King, H., Kumaran, D., Wierstra, D., Legg, S., & Hassabis, D. (2015). Human-level control through deep reinforcement learning. *Nature*, 518(7540), 529–533.
27. Moreno, A., Pinton, J., Valls, A., & Isern, D. (2021). Personalised tourist itinerary recommendation based on a hybrid deep learning approach with cold-start handling. *Applied Soft Computing*, 112, 107796.
28. Narvekar, S., Peng, B., Leonetti, M., Sinapov, J., Taylor, M. E., & Stone, P. (2020). Curriculum learning for reinforcement learning domains: A framework and survey. *Journal of Machine Learning Research*, 21(181), 1–50.
29. Nguyen, T. D., Luu, V. T., & Tran, D. H. (2023). Cluster-conditioned multi-agent reinforcement learning for personalised urban tourism routing. *Tourism Management Perspectives*, 46, 101091.
30. Oda, Y., & Joe-Wong, C. (2018). MOVI: A model-free approach to dynamic fleet management. In *Proceedings of IEEE INFOCOM 2018* (pp. 2708–2716). IEEE.
31. Prayag, G., & Ryan, C. (2011). The relationship between tourists' destination image, place attachment, personal involvement, and behavioural intentions. *Journal of Travel Research*, 50(4), 372–386.
32. Rahman, M. A., Hamid, M. N., & Aziz, A. (2023). Virtual reality for Hajj and Umrah pre-visit familiarisation: Impact on on-site navigation performance. *International Journal of Pilgrimage Research*, 5(1), 78–94.
33. Rashid, T., Samvelyan, M., De Witt, C. S., Farquhar, G., Foerster, J., & Whiteson, S. (2020). Monotonic value function factorisation for deep multi-agent reinforcement learning. *Journal of Machine Learning Research*, 21(178), 1–51.
34. Raun, J., Ahas, R., & Tiru, M. (2016). Measuring tourism destinations using mobile tracking data. *Tourism Management*, 57, 202–212.
35. Rousseeuw, P. J. (1987). Silhouettes: A graphical aid to the interpretation and validation of cluster analysis. *Journal of Computational and Applied Mathematics*, 20, 53–65.
36. Saudi Tourism Authority. (2023). *Annual tourism statistics report 2023*. Ministry of Tourism, Kingdom of Saudi Arabia.
37. Sutton, R. S., & Barto, A. G. (2018). *Reinforcement learning: An introduction* (2nd ed.). MIT Press.
38. Tan, L., Li, Y., Xie, J., & Chen, X. (2021). Emergency evacuation path assignment using multi-agent deep reinforcement learning in large public spaces. *Safety Science*, 140, 105266.
39. Tang, X., Qin, Z., Zhang, F., Wang, Z., Xu, Z., Ma, Y., Zhu, H., & Ye, J. (2021). A deep value-network based approach for multi-driver order dispatching. In *Proceedings of the 25th ACM SIGKDD Conference on Knowledge Discovery and Data Mining* (pp. 1780–1790). ACM.
40. Vamplew, P., Dazeley, R., Foale, C., Firmin, S., & Mummery, J. (2022). Human-aligned artificial intelligence is a multiobjective problem. *Ethics and Information Technology*, 24, 1–17.
41. Vansteenwegen, P., Souffriau, W., & Van Oudheusden, D. (2011). The orienteering problem: A survey. *European Journal of Operational Research*, 209(1), 1–10.
42. Wei, H., Xu, N., Zhang, H., Zheng, G., Zang, X., Chen, C., Zhang, W., Zhu, Y., Xu, K., & Li, Z. (2019). CoLight: Learning network-level cooperation for traffic signal control. In *Proceedings of the 28th ACM International Conference on Information and Knowledge Management* (pp. 1913–1922). ACM.
43. Xu, Z., Li, Z., Guan, Q., Zhang, D., Li, Q., Nan, J., Liu, C., Bian, W., & Ye, J. (2018). Large-scale order dispatch in on-demand ride-hailing platforms: A learning and planning approach. In *Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining* (pp. 905–913). ACM.
44. Yu, C., Velu, A., Vinitsky, E., Gao, J., Wang, Y., Bayen, A., & Wu, Y. (2022). The surprising effectiveness of MAPPO in cooperative multi-agent games. *Advances in Neural Information Processing Systems*, 35, 24611–24624.
45. Zhang, J., Zheng, L., & Sui, D. (2021). Multi-agent reinforcement learning: A selective overview of theories and algorithms. In K. G. Vamvoudakis, Y. Wan, F. L. Lewis, & D. Cansever (Eds.), *Handbook of Reinforcement Learning and Control* (pp. 321–384). Springer.
46. Zhang, W., Chen, X., Li, H., & Tang, Y. (2023). Graph attention network-enhanced Q-learning for explainable cultural heritage itinerary recommendation. *Knowledge-Based Systems*, 261, 110228.
47. Zheng, W., Ji, H., Lin, J., Wang, B., & Yu, B. (2020). Using a heuristic approach to design personalized urban tourism itineraries with hotel selection. *Tourism Management*, 76, 103956.
Downloads
Published
Issue
Section
License
This work is licensed under a Creative Commons Attribution 4.0 International License.
This work is licensed under a Creative Commons Attribution 4.0 International License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
