IDEAS home Printed from https://ideas.repec.org/a/eee/transb/v185y2024ics0191261524001085.html
   My bibliography  Save this article

The Capacitated Team Orienteering Problem: An online optimization framework with predictions of unknown accuracy

Author

Listed:
  • Shiri, Davood
  • Akbari, Vahid
  • Hassanzadeh, Ali

Abstract

The Capacitated Team Orienteering Problem (CTOP) is a challenging combinatorial optimization problem, wherein a fleet of vehicles traverses multiple locations, each with distinct prizes, demand weights, and service times. The primary objective is to determine optimal routes for the vehicles that collectively accumulate the highest total prize within capacity and time constraints. The CTOP finds applications across various domains such as disaster response, maintenance, marketing, tourism, and surveillance, where coordinated teams are required to efficiently explore and gather prizes from different sites. The complexity of this problem is further compounded by uncertainties in predicting specific attributes of each location, making it hard to plan routes accurately in advance. In numerous scenarios in practice, subjective predictions for these parameters may exist, but their precise values remain unknown until a location is visited by one of the vehicles. Given the unpredictable nature of these parameters, there is a pressing need for innovative online optimization strategies that can adapt to new information, ensuring the strategic allocation of resources and route planning within set constraints. To address this challenging online optimization problem, we offer a detailed analysis through the lens of theoretical and empirical competitive ratios. We derive an exact tight upper bound on the competitive ratio of online algorithms, and we introduce three novel online algorithms, with two of them achieving optimal competitive ratios. The third algorithm is a polynomial time approximation-based online algorithm with a competitive ratio of 13.53 times the tight upper bound. To evaluate our algorithms, we measure their empirical competitive ratios on randomly generated instances as well as instances from the literature. Our empirical analysis demonstrates the effectiveness of our solutions across a diverse range of simulation scenarios.

Suggested Citation

  • Shiri, Davood & Akbari, Vahid & Hassanzadeh, Ali, 2024. "The Capacitated Team Orienteering Problem: An online optimization framework with predictions of unknown accuracy," Transportation Research Part B: Methodological, Elsevier, vol. 185(C).
    • Handle: RePEc:eee:transb:v:185:y:2024:i:c:s0191261524001085
    DOI: 10.1016/j.trb.2024.102984
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0191261524001085
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.trb.2024.102984?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Dimitris Bertsimas & Patrick Jaillet, & Sébastien Martin, 2019. "Online Vehicle Routing: The Edge of Optimization in Large-Scale Applications," Operations Research, INFORMS, vol. 67(1), pages 143-162, January.
    2. Luo, Zhixing & Cheang, Brenda & Lim, Andrew & Zhu, Wenbin, 2013. "An adaptive ejection pool with toggle-rule diversification approach for the capacitated team orienteering problem," European Journal of Operational Research, Elsevier, vol. 229(3), pages 673-682.
    3. Asma Ben-Said & Racha El-Hajj & Aziz Moukrim, 2019. "A variable space search heuristic for the Capacitated Team Orienteering Problem," Journal of Heuristics, Springer, vol. 25(2), pages 273-303, April.
    4. Patrick Jaillet & Michael R. Wagner, 2006. "Online Routing Problems: Value of Advanced Information as Improved Competitive Ratios," Transportation Science, INFORMS, vol. 40(2), pages 200-210, May.
    5. Stacy A. Voccia & Ann Melissa Campbell & Barrett W. Thomas, 2019. "The Same-Day Delivery Problem for Online Purchases," Service Science, INFORMS, vol. 53(1), pages 167-184, February.
    6. Yu, Wei & Liu, Zhaohui & Bao, Xiaoguang, 2014. "Optimal deterministic algorithms for some variants of Online Quota Traveling Salesman Problem," European Journal of Operational Research, Elsevier, vol. 238(3), pages 735-740.
    7. Lanah Evers & Twan Dollevoet & Ana Barros & Herman Monsuur, 2014. "Robust UAV mission planning," Annals of Operations Research, Springer, vol. 222(1), pages 293-315, November.
    8. Balcik, Burcu & Yanıkoğlu, İhsan, 2020. "A robust optimization approach for humanitarian needs assessment planning under travel time uncertainty," European Journal of Operational Research, Elsevier, vol. 282(1), pages 40-57.
    9. Bian, Zheyong & Liu, Xiang, 2018. "A real-time adjustment strategy for the operational level stochastic orienteering problem: A simulation-aided optimization approach," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 115(C), pages 246-266.
    10. Chao, I-Ming & Golden, Bruce L. & Wasil, Edward A., 1996. "A fast and effective heuristic for the orienteering problem," European Journal of Operational Research, Elsevier, vol. 88(3), pages 475-489, February.
    11. Xiao-Yue Gong & Vineet Goyal & Garud N. Iyengar & David Simchi-Levi & Rajan Udwani & Shuangyu Wang, 2022. "Online Assortment Optimization with Reusable Resources," Management Science, INFORMS, vol. 68(7), pages 4772-4785, July.
    12. Patrick Jaillet & Michael R. Wagner, 2008. "Generalized Online Routing: New Competitive Ratios, Resource Augmentation, and Asymptotic Analyses," Operations Research, INFORMS, vol. 56(3), pages 745-757, June.
    13. Javier Panadero & Angel A. Juan & Christopher Bayliss & Christine Currie, 2020. "Maximising reward from a team of surveillance drones: a simheuristic approach to the stochastic team orienteering problem," European Journal of Industrial Engineering, Inderscience Enterprises Ltd, vol. 14(4), pages 485-516.
    14. C Archetti & D Feillet & A Hertz & M G Speranza, 2009. "The capacitated team orienteering and profitable tour problems," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 60(6), pages 831-842, June.
    15. Michiel Blom & Sven O. Krumke & Willem E. de Paepe & Leen Stougie, 2001. "The Online TSP Against Fair Adversaries," INFORMS Journal on Computing, INFORMS, vol. 13(2), pages 138-148, May.
    16. S. Y. Teng & H. L. Ong & H. C. Huang, 2004. "An Integer L-Shaped Algorithm For Time-Constrained Traveling Salesman Problem With Stochastic Travel And Service Times," Asia-Pacific Journal of Operational Research (APJOR), World Scientific Publishing Co. Pte. Ltd., vol. 21(02), pages 241-257.
    17. Shu Zhang & Jeffrey W. Ohlmann & Barrett W. Thomas, 2018. "Dynamic Orienteering on a Network of Queues," Transportation Science, INFORMS, vol. 52(3), pages 691-706, June.
    18. Akbari, Vahid & Shiri, Davood, 2021. "Weighted online minimum latency problem with edge uncertainty," European Journal of Operational Research, Elsevier, vol. 295(1), pages 51-65.
    19. Zhang, Shu & Ohlmann, Jeffrey W. & Thomas, Barrett W., 2014. "A priori orienteering with time windows and stochastic wait times at customers," European Journal of Operational Research, Elsevier, vol. 239(1), pages 70-79.
    20. Sushil Gupta & Martin K. Starr & Reza Zanjirani Farahani & Mahsa Mahboob Ghodsi, 2020. "Prevention of Terrorism–An Assessment of Prior POM Work and Future Potentials," Production and Operations Management, Production and Operations Management Society, vol. 29(7), pages 1789-1815, July.
    21. Davood Shiri & Vahid Akbari & F. Sibel Salman, 2024. "Online algorithms for ambulance routing in disaster response with time-varying victim conditions," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 46(3), pages 785-819, September.
    22. Dolinskaya, Irina & Shi, Zhenyu (Edwin) & Smilowitz, Karen, 2018. "Adaptive orienteering problem with stochastic travel times," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 109(C), pages 1-19.
    23. Tarantilis, C.D. & Stavropoulou, F. & Repoussis, P.P., 2013. "The Capacitated Team Orienteering Problem: A Bi-level Filter-and-Fan method," European Journal of Operational Research, Elsevier, vol. 224(1), pages 65-78.
    24. Kotiloglu, S. & Lappas, T. & Pelechrinis, K. & Repoussis, P.P., 2017. "Personalized multi-period tour recommendations," Tourism Management, Elsevier, vol. 62(C), pages 76-88.
    25. Davood Shiri & Vahid Akbari & F. Sibel Salman, 2020. "Online routing and scheduling of search-and-rescue teams," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 42(3), pages 755-784, September.
    26. Ananya Christman & William Forcier & Aayam Poudel, 2018. "From theory to practice: maximizing revenues for on-line dial-a-ride," Journal of Combinatorial Optimization, Springer, vol. 35(2), pages 512-529, February.
    27. H Tang & E Miller-Hooks, 2005. "Algorithms for a stochastic selective travelling salesperson problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 56(4), pages 439-452, April.
    28. Ann Campbell & Michel Gendreau & Barrett Thomas, 2011. "The orienteering problem with stochastic travel and service times," Annals of Operations Research, Springer, vol. 186(1), pages 61-81, June.
    29. Gunawan, Aldy & Lau, Hoong Chuin & Vansteenwegen, Pieter, 2016. "Orienteering Problem: A survey of recent variants, solution approaches and applications," European Journal of Operational Research, Elsevier, vol. 255(2), pages 315-332.
    30. Will Ma & David Simchi-Levi & Chung-Piaw Teo, 2021. "On Policies for Single-Leg Revenue Management with Limited Demand Information," Operations Research, INFORMS, vol. 69(1), pages 207-226, January.
    31. Riera-Ledesma, Jorge & Salazar-González, Juan José, 2017. "Solving the Team Orienteering Arc Routing Problem with a column generation approach," European Journal of Operational Research, Elsevier, vol. 262(1), pages 14-27.
    32. Will Ma & David Simchi-Levi, 2020. "Algorithms for Online Matching, Assortment, and Pricing with Tight Weight-Dependent Competitive Ratios," Operations Research, INFORMS, vol. 68(6), pages 1787-1803, November.
    33. Zhang, Guowei & Jia, Ning & Zhu, Ning & Adulyasak, Yossiri & Ma, Shoufeng, 2023. "Robust drone selective routing in humanitarian transportation network assessment," European Journal of Operational Research, Elsevier, vol. 305(1), pages 400-428.
    34. Vansteenwegen, Pieter & Souffriau, Wouter & Oudheusden, Dirk Van, 2011. "The orienteering problem: A survey," European Journal of Operational Research, Elsevier, vol. 209(1), pages 1-10, February.
    35. Zhang, Huili & Tong, Weitian & Lin, Guohui & Xu, Yinfeng, 2019. "Online minimum latency problem with edge uncertainty," European Journal of Operational Research, Elsevier, vol. 273(2), pages 418-429.
    36. Anupam Gupta & Ravishankar Krishnaswamy & Viswanath Nagarajan & R. Ravi, 2015. "Running Errands in Time: Approximation Algorithms for Stochastic Orienteering," Mathematics of Operations Research, INFORMS, vol. 40(1), pages 56-79, February.
    37. Verbeeck, C. & Vansteenwegen, P. & Aghezzaf, E.-H., 2016. "Solving the stochastic time-dependent orienteering problem with time windows," European Journal of Operational Research, Elsevier, vol. 255(3), pages 699-718.
    38. Qinxiao Yu & Yossiri Adulyasak & Louis-Martin Rousseau & Ning Zhu & Shoufeng Ma, 2022. "Team Orienteering with Time-Varying Profit," INFORMS Journal on Computing, INFORMS, vol. 34(1), pages 262-280, January.
    39. Chao, I-Ming & Golden, Bruce L. & Wasil, Edward A., 1996. "The team orienteering problem," European Journal of Operational Research, Elsevier, vol. 88(3), pages 464-474, February.
    40. Akbari, Vahid & Shiri, Davood & Sibel Salman, F., 2021. "An online optimization approach to post-disaster road restoration," Transportation Research Part B: Methodological, Elsevier, vol. 150(C), pages 1-25.
    41. Qinxiao Yu & Chun Cheng & Ning Zhu, 2022. "Robust Team Orienteering Problem with Decreasing Profits," INFORMS Journal on Computing, INFORMS, vol. 34(6), pages 3215-3233, November.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Bian, Zheyong & Liu, Xiang, 2018. "A real-time adjustment strategy for the operational level stochastic orienteering problem: A simulation-aided optimization approach," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 115(C), pages 246-266.
    2. Ruiz-Meza, José & Montoya-Torres, Jairo R., 2022. "A systematic literature review for the tourist trip design problem: Extensions, solution techniques and future research lines," Operations Research Perspectives, Elsevier, vol. 9(C).
    3. Qinxiao Yu & Chun Cheng & Ning Zhu, 2022. "Robust Team Orienteering Problem with Decreasing Profits," INFORMS Journal on Computing, INFORMS, vol. 34(6), pages 3215-3233, November.
    4. Gunawan, Aldy & Lau, Hoong Chuin & Vansteenwegen, Pieter, 2016. "Orienteering Problem: A survey of recent variants, solution approaches and applications," European Journal of Operational Research, Elsevier, vol. 255(2), pages 315-332.
    5. Davood Shiri & Vahid Akbari & F. Sibel Salman, 2024. "Online algorithms for ambulance routing in disaster response with time-varying victim conditions," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 46(3), pages 785-819, September.
    6. Verbeeck, C. & Vansteenwegen, P. & Aghezzaf, E.-H., 2016. "Solving the stochastic time-dependent orienteering problem with time windows," European Journal of Operational Research, Elsevier, vol. 255(3), pages 699-718.
    7. Zhao, Yanlu & Alfandari, Laurent, 2020. "Design of diversified package tours for the digital travel industry : A branch-cut-and-price approach," European Journal of Operational Research, Elsevier, vol. 285(3), pages 825-843.
    8. Zhang, Shu & Ohlmann, Jeffrey W. & Thomas, Barrett W., 2020. "Multi-period orienteering with uncertain adoption likelihood and waiting at customers," European Journal of Operational Research, Elsevier, vol. 282(1), pages 288-303.
    9. Wu, Qinghua & He, Mu & Hao, Jin-Kao & Lu, Yongliang, 2024. "An effective hybrid evolutionary algorithm for the clustered orienteering problem," European Journal of Operational Research, Elsevier, vol. 313(2), pages 418-434.
    10. Yu, Qinxiao & Fang, Kan & Zhu, Ning & Ma, Shoufeng, 2019. "A matheuristic approach to the orienteering problem with service time dependent profits," European Journal of Operational Research, Elsevier, vol. 273(2), pages 488-503.
    11. Samita Kedkaew & Warisa Nakkiew & Parida Jewpanya & Wasawat Nakkiew, 2024. "A Novel Tourist Trip Design Problem with Stochastic Travel Times and Partial Charging for Battery Electric Vehicles," Mathematics, MDPI, vol. 12(18), pages 1-19, September.
    12. Stavropoulou, F. & Repoussis, P.P. & Tarantilis, C.D., 2019. "The Vehicle Routing Problem with Profits and consistency constraints," European Journal of Operational Research, Elsevier, vol. 274(1), pages 340-356.
    13. Orlis, Christos & Laganá, Demetrio & Dullaert, Wout & Vigo, Daniele, 2020. "Distribution with Quality of Service Considerations: The Capacitated Routing Problem with Profits and Service Level Requirements," Omega, Elsevier, vol. 93(C).
    14. Zhang, Guowei & Jia, Ning & Zhu, Ning & Adulyasak, Yossiri & Ma, Shoufeng, 2023. "Robust drone selective routing in humanitarian transportation network assessment," European Journal of Operational Research, Elsevier, vol. 305(1), pages 400-428.
    15. Dolinskaya, Irina & Shi, Zhenyu (Edwin) & Smilowitz, Karen, 2018. "Adaptive orienteering problem with stochastic travel times," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 109(C), pages 1-19.
    16. Shahmanzari, Masoud & Mansini, Renata, 2024. "A learning-based granular variable neighborhood search for a multi-period election logistics problem with time-dependent profits," European Journal of Operational Research, Elsevier, vol. 319(1), pages 135-152.
    17. Erika M. Herrera & Javier Panadero & Patricia Carracedo & Angel A. Juan & Elena Perez-Bernabeu, 2022. "Determining Reliable Solutions for the Team Orienteering Problem with Probabilistic Delays," Mathematics, MDPI, vol. 10(20), pages 1-15, October.
    18. Kotiloglu, S. & Lappas, T. & Pelechrinis, K. & Repoussis, P.P., 2017. "Personalized multi-period tour recommendations," Tourism Management, Elsevier, vol. 62(C), pages 76-88.
    19. Freeman, Nickolas K. & Keskin, Burcu B. & Çapar, İbrahim, 2018. "Attractive orienteering problem with proximity and timing interactions," European Journal of Operational Research, Elsevier, vol. 266(1), pages 354-370.
    20. Evers, L. & Glorie, K.M. & van der Ster, S. & Barros, A.I. & Monsuur, H., 2012. "The Orienteering Problem under Uncertainty Stochastic Programming and Robust Optimization compared," Econometric Institute Research Papers EI 2012-21, Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:transb:v:185:y:2024:i:c:s0191261524001085. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/wps/find/journaldescription.cws_home/548/description#description .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.