Dynamic Scoring and Costing in the Orienteering Problem: A Model Based on Length of Stay
Main Article Content
Keywords
orienteering problem, mixed integer programming, route design, optimization, diminishing return
Abstract
In today's travel and tourism landscape, the role of travel agents has become increasingly complex as they are challenged to explore a variety of potential destinations. More specifically, the complicated task of planning itineraries that truly satisfy travellers puts travel agents in a crucial role, increasing the complexity of itinerary planning. This complexity is compounded not only by the multitude of possible destinations, but also by non-negotiable constraints such as cost and time. To address these challenges, the orienteering problem represents a fundamental mathematical model that provides a theoretical basis for understanding the nuanced difficulties faced by travel agents.This study ventures into a novel iteration of the orienteering problem, with a particular focus on optimizing travel satisfaction based on length of stay. A notable aspect of this variant is the inclusion of time and cost constraints in the route determination process. Using an integer programming model, the satisfaction scores for each location are described by a diminishing returns function linked to length of stay, while the costs associated with each location follow a linear function influenced by the same parameter. The application of this model is in a hypothetical scenario with 32 nodes, with the calculations facilitated by the FilMINT solver. A sensitivity analysis examines time and cost constraints and shows their decisive influence on the optimization of travel routes. The results of this research contribute significantly to a strategic framework and provide travel agencies with the opportunity to create itineraries that not only meet practical limits but, more importantly, increase traveller satisfaction.
Downloads
References
[2] C. keung S. Wong and W. Y. Yan Kwong, ‘Outbound tourists’ selection criteria for choosing all-inclusive package tours’, Tour Manag, 2004, doi: 10.1016/j.tourman.2003.06.002.
[3] P. Vansteenwegen and W. Souffriau, ‘The orienteering problem: A survey’, Eur J Oper Res, vol. 209, pp. 1–10, Feb. 2011, doi: 10.1016/j.ejor.2010.03.045.
[4] A. Gunawan, H. C. Lau, and P. Vansteenwegen, ‘Orienteering Problem: A survey of recent variants, solution approaches and applications’, Eur J Oper Res, vol. 255, no. 2, pp. 315–332, 2016, doi: 10.1016/j.ejor.2016.04.059.
[5] I. M. Chao, B. L. Golden, and E. A. Wasil, ‘A fast and effective heuristic for the orienteering problem’, Eur J Oper Res, vol. 88, no. 3, pp. 475–489, 1996, doi: 10.1016/0377-2217(95)00035-6.
[6] T. Tsiligirides, ‘Heuristic methods applied to orienteering’, Journal of the Operational Research Society, vol. 35, no. 9, 1984, doi: 10.1057/jors.1984.162.
[7] B. L. Golden, L. Levy, and R. Vohra, ‘The orienteering problem’, Naval Research Logistics (NRL), vol. 34, no. 3, pp. 307–318, 1987, doi: 10.1002/1520-6750(198706)34:3<307::AID-NAV3220340302>3.0.CO;2-D.
[8] T. Thomadsen and T. Stidsen, ‘The Quadratic Selective Travelling Salesman Problem’, Informatics and Mathematical Modelling, 2003.
[9] W. Souffriau, P. Vansteenwegen, J. Vertommen, G. Vanden Berghe, and D. Van Oudheusden, ‘A personalized tourist trip design algorithm for mobile tourist guides’, Applied Artificial Intelligence, vol. 22, no. 10, 2008, doi: 10.1080/08839510802379626.
[10] P. Vansteenwegen and D. Van Oudheusden, ‘The Mobile Tourist Guide: An OR Opportunity’, OR Insight, 2007, doi: 10.1057/ori.2007.17.
[11] H. Kim, B. I. Kim, and D. jin Noh, ‘The multi-profit orienteering problem’, Comput Ind Eng, vol. 149, no. July, p. 106808, Nov. 2020, doi: 10.1016/j.cie.2020.106808.
[12] H. Rezki and B. Aghezzaf, ‘The bi-objective orienteering problem with budget constraint: GRASP-ILS’, 2017 International Colloquium on Logistics and Supply Chain Management: Competitiveness and Innovation in Automobile and Aeronautics Industries, LOGISTIQUA 2017, pp. 25–30, 2017, doi: 10.1109/LOGISTIQUA.2017.7962868.
[13] E. Cannan, ‘The Origin of the Law of Diminishing Returns, 1813-15’, The Economic Journal, 1892, doi: 10.2307/2955940.
[14] C. Riera-Prunera, ‘Diminishing Returns BT - Encyclopedia of Quality of Life and Well-Being Research’, A. C. Michalos, Ed., Dordrecht: Springer Netherlands, 2014, pp. 1631–1635. doi: 10.1007/978-94-007-0753-5_735.
[15] Prof. A. Trifu, ‘The Marginal Diminishing Returns/Marginal Increasing Returns in The Pursuit of Happiness’, Global Journal of Management and Business Research, vol. 20, no. 1, pp. 9–11, 2020, doi: 10.34257/gjmbrbvol20is1pg9.
[16] J. K. Whitaker, H. H. Gossen, R. Blitz, and N. Georgescu-Roegen, ‘The Laws of Human Relations and the Rules of Human Action Derived Therefrom.’, Economica, vol. 52, no. 207, p. 396, Aug. 1985, doi: 10.2307/2553864.
[17] A. Festjens and C. Janiszewski, ‘The value of time’, Journal of Consumer Research, vol. 42, no. 2, pp. 178–195, Jul. 2015, doi: 10.1093/jcr/ucv021.
[18] M. G. Kantor and M. B. Rosenwein, ‘The Orienteering Problem with Time Windows’, J Oper Res Soc, 1992, doi: 10.2307/2583018.
[19] P. Vansteenwegen, W. Souffriau, G. Vanden Berghe, and D. Van Oudheusden, ‘Iterated local search for the team orienteering problem with time windows’, Comput Oper Res, 2009, doi: 10.1016/j.cor.2009.03.008.
[20] I. Hapsari, I. Surjandari, and K. Komarudin, ‘Solving multi-objective team orienteering problem with time windows using adjustment iterated local search’, Journal of Industrial Engineering International, vol. 15, no. 4, pp. 679–693, 2019, doi: 10.1007/s40092-019-0315-9.
[21] M. Schilde, K. F. Doerner, R. F. Hartl, and G. Kiechle, ‘Metaheuristics for the bi-objective orienteering problem’, Swarm Intelligence, vol. 3, no. 3, pp. 179–201, 2009, doi: 10.1007/s11721-009-0029-5.
[22] C. Verbeeck, P. Vansteenwegen, and E. H. Aghezzaf, ‘The time-dependent orienteering problem with time windows: a fast ant colony system’, Ann Oper Res, vol. 254, no. 1–2, pp. 481–505, 2017, doi: 10.1007/s10479-017-2409-3.
[23] C. Archetti, F. Carrabs, and R. Cerulli, ‘The Set Orienteering Problem’, Eur J Oper Res, 2018, doi: 10.1016/j.ejor.2017.11.009.
[24] C. Archetti, D. Feillet, A. Hertz, and M. G. Speranza, ‘The capacitated team orienteering and profitable tour problems’, Journal of the Operational Research Society, 2009, doi: 10.1057/palgrave.jors.2602603.
[25] F. V. Fomin and A. Lingas, ‘Approximation algorithms for time-dependent orienteering’, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 2138, pp. 508–515, 2001, doi: 10.1007/3-540-44669-9_57.
[26] Y. Mei, F. D. Salim, and X. Li, ‘Efficient meta-heuristics for the Multi-Objective Time-Dependent Orienteering Problem’, Eur J Oper Res, vol. 254, no. 2, pp. 443–457, 2016, doi: 10.1016/j.ejor.2016.03.053.
[27] J. Pietz and J. O. Royset, ‘Generalized orienteering problem with resource dependent rewards’, Naval Research Logistics, 2013, doi: 10.1002/nav.21534.
[28] Q. Yu, K. Fang, N. Zhu, and S. Ma, ‘A matheuristic approach to the orienteering problem with service time dependent profits’, Eur J Oper Res, vol. 273, no. 2, pp. 488–503, 2019, doi: 10.1016/j.ejor.2018.08.007.
[29] A. M. Campbell, M. Gendreau, and B. W. Thomas, ‘The orienteering problem with stochastic travel and service times’, Ann Oper Res, 2011, doi: 10.1007/s10479-011-0895-2.
[30] G. Erdoǧan and G. Laporte, ‘The orienteering problem with variable profits’, in Networks, 2013. doi: 10.1002/net.21496.
[31] T. Ilhan, S. M. R. Iravani, and M. S. Daskin, ‘The orienteering problem with stochastic profits’, IIE Transactions (Institute of Industrial Engineers), vol. 40, no. 4, pp. 406–421, 2008, doi: 10.1080/07408170701592481.
[32] I. M. Chao, B. L. Golden, and E. A. Wasil, ‘The team orienteering problem’, Eur J Oper Res, 1996, doi: 10.1016/0377-2217(94)00289-4.
Article Sidebar
Article Details
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.
Authors' Retention of Copyright
Authors retain the copyright of their original work published in Jurnal Optimasi Sistem Industri (JOSI). By submitting their manuscript to the journal, authors grant Jurnal Optimasi Sistem Industri (JOSI) a non-exclusive license to publish the work under the CC BY-NC-SA 4.0 International License. This means that others are permitted to:
- Share and adapt the work for non-commercial purposes, provided proper attribution is given to the original authors and source.
- Create derivative works based on the original article, as long as the new work is non-commercial and under the same CC BY-NC-SA 4.0 International License.
Non-Commercial Usage
The CC BY-NC-SA 4.0 International License restricts commercial use of the published work and its derivatives. Commercial use includes generating revenue, financial gain, or any form of commercial exploitation. This limitation aims to preserve the scholarly and educational nature of the content.
ShareAlike Requirement
If you remix, adapt, or build upon the work, you must distribute your contributions under the same CC BY-NC-SA 4.0 International License as the original work. This "ShareAlike" requirement ensures that any new works based on the original content adhere to the same non-commercial, share-alike principles.
Usage, Attribution, and Citations
Authors and readers are allowed to:
- Share and distribute the published article in any medium or format.
- Adapt, remix, transform, and build upon the article for non-commercial purposes.
- Provide appropriate attribution to the original authors and the journal.
When using content from Jurnal Optimasi Sistem Industri (JOSI), proper attribution must be provided through citation of the original source and authors.
Copyright Infringement and Ethical Considerations
If you believe that any material published in Jurnal Optimasi Sistem Industri (JOSI) infringes upon your copyright or the copyright of someone you represent, please contact the editorial team promptly. The journal is committed to addressing copyright concerns in accordance with established ethical guidelines set forth by the Committee on Publication Ethics (COPE).
For any questions or inquiries related to copyright and licensing, please contact the editorial team at editor_josi[at]eng.unand.ac.id.
