IDEAS home Printed from https://ideas.repec.org/a/eee/proeco/v145y2013i1p150-160.html
   My bibliography  Save this article

A variable neighborhood search method for the orienteering problem with hotel selection

Author

Listed:
  • Divsalar, A.
  • Vansteenwegen, P.
  • Cattrysse, D.

Abstract

In this paper, we present the orienteering problem with hotel selection (OPHS), an extension of the orienteering problem (OP). In the OPHS, a set of vertices with a score and a set of hotels are given. The goal is to determine a fixed number of connected trips that visits some vertices and maximizes the sum of the collected scores. Each trip is limited in length and should start and end in one of the hotels. We formulate the problem mathematically, explain the differences with related optimization problems and indicate what makes this problem inherently more difficult.

Suggested Citation

  • Divsalar, A. & Vansteenwegen, P. & Cattrysse, D., 2013. "A variable neighborhood search method for the orienteering problem with hotel selection," International Journal of Production Economics, Elsevier, vol. 145(1), pages 150-160.
    • Handle: RePEc:eee:proeco:v:145:y:2013:i:1:p:150-160
    DOI: 10.1016/j.ijpe.2013.01.010
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0925527313000285
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ijpe.2013.01.010?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. Vansteenwegen, Pieter & Souffriau, Wouter & Berghe, Greet Vanden & Oudheusden, Dirk Van, 2009. "A guided local search metaheuristic for the team orienteering problem," European Journal of Operational Research, Elsevier, vol. 196(1), pages 118-127, July.
    2. Pieter Vansteenwegen & Wouter Souffriau & Greet Vanden Berghe & Dirk Van Oudheusden, 2009. "Metaheuristics for Tourist Trip Planning," Lecture Notes in Economics and Mathematical Systems, in: Kenneth Sörensen & Marc Sevaux & Walter Habenicht & Martin Josef Geiger (ed.), Metaheuristics in the Service Industry, chapter 2, pages 15-31, Springer.
    3. Hansen, Pierre & Mladenovic, Nenad, 2001. "Variable neighborhood search: Principles and applications," European Journal of Operational Research, Elsevier, vol. 130(3), pages 449-467, May.
    4. 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.
    5. 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.
    6. Labadie, Nacima & Mansini, Renata & Melechovský, Jan & Wolfler Calvo, Roberto, 2012. "The Team Orienteering Problem with Time Windows: An LP-based Granular Variable Neighborhood Search," European Journal of Operational Research, Elsevier, vol. 220(1), pages 15-27.
    7. 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.
    8. P Vansteenwegen & W Souffriau & K Sörensen, 2012. "The travelling salesperson problem with hotel selection," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 63(2), pages 207-217, February.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Dewil, R. & Vansteenwegen, P. & Cattrysse, D. & Van Oudheusden, D., 2015. "A minimum cost network flow model for the maximum covering and patrol routing problem," European Journal of Operational Research, Elsevier, vol. 247(1), pages 27-36.
    2. Chi Feng & Zhenyu Mei, 2023. "Optimization of Shared Autonomous Vehicles Routing Problem: From the View of Parking," Sustainability, MDPI, vol. 15(16), pages 1-17, August.
    3. Divsalar, A. & Vansteenwegen, P. & Sörensen, K. & Cattrysse, D., 2014. "A memetic algorithm for the orienteering problem with hotel selection," European Journal of Operational Research, Elsevier, vol. 237(1), pages 29-49.
    4. Naderi, B. & Zandieh, M., 2014. "Modeling and scheduling no-wait open shop problems," International Journal of Production Economics, Elsevier, vol. 158(C), pages 256-266.
    5. 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.
    6. Sifaleras, Angelo & Konstantaras, Ioannis & Mladenović, Nenad, 2015. "Variable neighborhood search for the economic lot sizing problem with product returns and recovery," International Journal of Production Economics, Elsevier, vol. 160(C), pages 133-143.
    7. Kotiloglu, S. & Lappas, T. & Pelechrinis, K. & Repoussis, P.P., 2017. "Personalized multi-period tour recommendations," Tourism Management, Elsevier, vol. 62(C), pages 76-88.
    8. Maximilian Schiffer & Michael Schneider & Grit Walther & Gilbert Laporte, 2019. "Vehicle Routing and Location Routing with Intermediate Stops: A Review," Transportation Science, INFORMS, vol. 53(2), pages 319-343, March.
    9. Sohrabi, Somayeh & Ziarati, Koorush & Keshtkaran, Morteza, 2020. "A Greedy Randomized Adaptive Search Procedure for the Orienteering Problem with Hotel Selection," European Journal of Operational Research, Elsevier, vol. 283(2), pages 426-440.
    10. Subramanian, Nachiappan & Gunasekaran, Angappa & Gao, Yanan, 2016. "Innovative service satisfaction and customer promotion behaviour in the Chinese budget hotel: an empirical study," International Journal of Production Economics, Elsevier, vol. 171(P2), pages 201-210.
    11. 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).
    12. Du, Jiaoman & Zhou, Jiandong & Li, Xiang & Li, Lei & Guo, Ao, 2021. "Integrated self-driving travel scheme planning," International Journal of Production Economics, Elsevier, vol. 232(C).

    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. Labadie, Nacima & Mansini, Renata & Melechovský, Jan & Wolfler Calvo, Roberto, 2012. "The Team Orienteering Problem with Time Windows: An LP-based Granular Variable Neighborhood Search," European Journal of Operational Research, Elsevier, vol. 220(1), pages 15-27.
    2. Dang, Duc-Cuong & Guibadj, Rym Nesrine & Moukrim, Aziz, 2013. "An effective PSO-inspired algorithm for the team orienteering problem," European Journal of Operational Research, Elsevier, vol. 229(2), pages 332-344.
    3. 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).
    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. 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.
    6. Morteza Keshtkaran & Koorush Ziarati & Andrea Bettinelli & Daniele Vigo, 2016. "Enhanced exact solution methods for the Team Orienteering Problem," International Journal of Production Research, Taylor & Francis Journals, vol. 54(2), pages 591-601, January.
    7. Balcik, Burcu, 2017. "Site selection and vehicle routing for post-disaster rapid needs assessment," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 101(C), pages 30-58.
    8. Gambardella, L.M. & Montemanni, R. & Weyland, D., 2012. "Coupling ant colony systems with strong local searches," European Journal of Operational Research, Elsevier, vol. 220(3), pages 831-843.
    9. Ke, Liangjun & Xu, Zongben & Feng, Zuren & Shang, Ke & Qian, Xueming, 2013. "Proportion-based robust optimization and team orienteering problem with interval data," European Journal of Operational Research, Elsevier, vol. 226(1), pages 19-31.
    10. Oktay Yılmaz & Ertan Yakıcı & Mumtaz Karatas, 2019. "A UAV location and routing problem with spatio-temporal synchronization constraints solved by ant colony optimization," Journal of Heuristics, Springer, vol. 25(4), pages 673-701, October.
    11. Hu, Qian & Lim, Andrew, 2014. "An iterative three-component heuristic for the team orienteering problem with time windows," European Journal of Operational Research, Elsevier, vol. 232(2), pages 276-286.
    12. 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.
    13. 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.
    14. Racha El-Hajj & Rym Nesrine Guibadj & Aziz Moukrim & Mehdi Serairi, 2020. "A PSO based algorithm with an efficient optimal split procedure for the multiperiod vehicle routing problem with profit," Annals of Operations Research, Springer, vol. 291(1), pages 281-316, August.
    15. Krzysztof Ostrowski & Joanna Karbowska-Chilinska & Jolanta Koszelew & Pawel Zabielski, 2017. "Evolution-inspired local improvement algorithm solving orienteering problem," Annals of Operations Research, Springer, vol. 253(1), pages 519-543, June.
    16. Lei, Chao & Lin, Wei-Hua & Miao, Lixin, 2014. "A multicut L-shaped based algorithm to solve a stochastic programming model for the mobile facility routing and scheduling problem," European Journal of Operational Research, Elsevier, vol. 238(3), pages 699-710.
    17. Afsaneh Amiri & Majid Salari, 2019. "Time-constrained maximal covering routing problem," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 41(2), pages 415-468, June.
    18. 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.
    19. 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.
    20. Zachariadis, E.E. & Kiranoudis, C.T., 2011. "Local search for the undirected capacitated arc routing problem with profits," European Journal of Operational Research, Elsevier, vol. 210(2), pages 358-367, April.

    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:proeco:v:145:y:2013:i:1:p:150-160. 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/locate/ijpe .

    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.