IDEAS home Printed from https://ideas.repec.org/a/pal/jorsoc/v68y2017i8d10.1057_s41274-017-0244-1.html
   My bibliography  Save this article

Well-tuned algorithms for the Team Orienteering Problem with Time Windows

Author

Listed:
  • Aldy Gunawan

    (Singapore Management University)

  • Hoong Chuin Lau

    (Singapore Management University)

  • Pieter Vansteenwegen

    (KU Leuven Mobility Research Centre - CIB)

  • Kun Lu

    (Singapore Management University)

Abstract

The Team Orienteering Problem with Time Windows (TOPTW) is the extension of the Orienteering Problem (OP) where each node is limited by a predefined time window during which the service has to start. The objective of the TOPTW is to maximize the total collected score by visiting a set of nodes with a limited number of paths. We propose two algorithms, Iterated Local Search and a hybridization of Simulated Annealing and Iterated Local Search (SAILS), to solve the TOPTW. As indicated in multiple research works on algorithms for the OP and its variants, determining appropriate parameter values in a statistical way remains a challenge. We apply Design of Experiments, namely factorial experimental design, to screen and rank all the parameters thereby allowing us to focus on the parameter search space of the important parameters. The proposed algorithms are tested on benchmark TOPTW instances. We demonstrate that well-tuned ILS and SAILS lead to improvements in terms of the quality of the solutions. More precisely, we are able to improve 50 best known solution values on the available benchmark instances.

Suggested Citation

  • Aldy Gunawan & Hoong Chuin Lau & Pieter Vansteenwegen & Kun Lu, 2017. "Well-tuned algorithms for the Team Orienteering Problem with Time Windows," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 68(8), pages 861-876, August.
    • Handle: RePEc:pal:jorsoc:v:68:y:2017:i:8:d:10.1057_s41274-017-0244-1
    DOI: 10.1057/s41274-017-0244-1
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1057/s41274-017-0244-1
    File Function: Abstract
    Download Restriction: Access to full text is restricted to subscribers.
    File URL: https://libkey.io/10.1057/s41274-017-0244-1?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. Marius M. Solomon, 1987. "Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints," Operations Research, INFORMS, vol. 35(2), pages 254-265, April.
    2. 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.
    3. Gendreau, Michel & Laporte, Gilbert & Semet, Frederic, 1998. "A tabu search heuristic for the undirected selective travelling salesman problem," European Journal of Operational Research, Elsevier, vol. 106(2-3), pages 539-545, April.
    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. 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.
    6. 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.
    7. Wouter Souffriau & Pieter Vansteenwegen & Greet Vanden Berghe & Dirk Van Oudheusden, 2013. "The Multiconstraint Team Orienteering Problem with Multiple Time Windows," Transportation Science, INFORMS, vol. 47(1), pages 53-63, February.
    8. Lin, Shih-Wei & Yu, Vincent F., 2012. "A simulated annealing heuristic for the team orienteering problem with time windows," European Journal of Operational Research, Elsevier, vol. 217(1), pages 94-107.
    9. Belarmino Adenso-Díaz & Manuel Laguna, 2006. "Fine-Tuning of Algorithms Using Fractional Experimental Designs and Local Search," Operations Research, INFORMS, vol. 54(1), pages 99-114, February.
    10. Bruce L. Golden & Larry Levy & Rakesh Vohra, 1987. "The orienteering problem," Naval Research Logistics (NRL), John Wiley & Sons, vol. 34(3), pages 307-318, June.
    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. Vincent F. Yu & Yueh-Sheng Lin & Panca Jodiawan & Shih-Wei Lin & Yu-Chi Lai, 2023. "The Field Technician Scheduling Problem with Experience-Dependent Service Times," Mathematics, MDPI, vol. 11(21), pages 1-17, November.
    2. Álvarez-Miranda, Eduardo & Luipersbeck, Martin & Sinnl, Markus, 2018. "Gotta (efficiently) catch them all: Pokémon GO meets Orienteering Problems," European Journal of Operational Research, Elsevier, vol. 265(2), pages 779-794.
    3. 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.
    4. 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.

    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. 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.
    2. Rahma Lahyani & Mahdi Khemakhem & Frédéric Semet, 2017. "A unified matheuristic for solving multi-constrained traveling salesman problems with profits," EURO Journal on Computational Optimization, Springer;EURO - The Association of European Operational Research Societies, vol. 5(3), pages 393-422, September.
    3. 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.
    4. Mei, Yi & Salim, Flora D. & Li, Xiaodong, 2016. "Efficient meta-heuristics for the Multi-Objective Time-Dependent Orienteering Problem," European Journal of Operational Research, Elsevier, vol. 254(2), pages 443-457.
    5. 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.
    6. 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.
    7. Ivanoe De Falco & Umberto Scafuri & Ernesto Tarantino, 2016. "Optimizing Personalized Touristic Itineraries by a Multiobjective Evolutionary Algorithm," International Journal of Information Technology & Decision Making (IJITDM), World Scientific Publishing Co. Pte. Ltd., vol. 15(06), pages 1269-1312, November.
    8. Damianos Gavalas & Charalampos Konstantopoulos & Konstantinos Mastakas & Grammati Pantziou, 2019. "Efficient Cluster-Based Heuristics for the Team Orienteering Problem with Time Windows," Asia-Pacific Journal of Operational Research (APJOR), World Scientific Publishing Co. Pte. Ltd., vol. 36(01), pages 1-44, February.
    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. 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.
    11. Kim, Hyunjoon & Kim, Byung-In, 2022. "Hybrid dynamic programming with bounding algorithm for the multi-profit orienteering problem," European Journal of Operational Research, Elsevier, vol. 303(2), pages 550-566.
    12. 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.
    13. Zheng, Weimin & Liao, Zhixue & Qin, Jing, 2017. "Using a four-step heuristic algorithm to design personalized day tour route within a tourist attraction," Tourism Management, Elsevier, vol. 62(C), pages 335-349.
    14. Ernesto Tarantino & Ivanoe De Falco & Umberto Scafuri, 2019. "A mobile personalized tourist guide and its user evaluation," Information Technology & Tourism, Springer, vol. 21(3), pages 413-455, September.
    15. 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.
    16. 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.
    17. 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.
    18. Sun, Peng & Veelenturf, Lucas P. & Hewitt, Mike & Van Woensel, Tom, 2018. "The time-dependent pickup and delivery problem with time windows," Transportation Research Part B: Methodological, Elsevier, vol. 116(C), pages 1-24.
    19. 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.
    20. 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.

    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:pal:jorsoc:v:68:y:2017:i:8:d:10.1057_s41274-017-0244-1. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.palgrave-journals.com/ .

    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.