IDEAS home Printed from https://ideas.repec.org/a/wly/jnljam/v2018y2018i1n2453185.html

A Comparison of Algorithms for Finding an Efficient Theme Park Tour

Author

Listed:
  • Elizabeth L. Bouzarth
  • Richard J. Forrester
  • Kevin R. Hutson
  • Rahul Isaac
  • James Midkiff
  • Danny Rivers
  • Leonard J. Testa

Abstract

The problem of efficiently touring a theme park so as to minimize the amount of time spent in queues is an instance of the Traveling Salesman Problem with Time‐Dependent Service Times (TSP‐TS). In this paper, we present a mixed‐integer linear programming formulation of the TSP‐TS and describe a branch‐and‐cut algorithm based on this model. In addition, we develop a lower bound for the TSP‐TS and describe two metaheuristic approaches for obtaining good quality solutions: a genetic algorithm and a tabu search algorithm. Using test instances motivated by actual theme park data, we conduct a computational study to compare the effectiveness of our algorithms.

Suggested Citation

  • Elizabeth L. Bouzarth & Richard J. Forrester & Kevin R. Hutson & Rahul Isaac & James Midkiff & Danny Rivers & Leonard J. Testa, 2018. "A Comparison of Algorithms for Finding an Efficient Theme Park Tour," Journal of Applied Mathematics, John Wiley & Sons, vol. 2018(1).
    • Handle: RePEc:wly:jnljam:v:2018:y:2018:i:1:n:2453185
    DOI: 10.1155/2018/2453185
    as

    Download full text from publisher

    File URL: https://doi.org/10.1155/2018/2453185
    Download Restriction: no
    File URL: https://libkey.io/10.1155/2018/2453185?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
    ---><---

    References listed on IDEAS

    as
    1. Malandraki, Chryssi & Dial, Robert B., 1996. "A restricted dynamic programming heuristic algorithm for the time dependent traveling salesman problem," European Journal of Operational Research, Elsevier, vol. 90(1), pages 45-55, April.
    2. G. Dantzig & R. Fulkerson & S. Johnson, 1954. "Solution of a Large-Scale Traveling-Salesman Problem," Operations Research, INFORMS, vol. 2(4), pages 393-410, November.
    3. Bernhard Fleischmann & Martin Gietz & Stefan Gnutzmann, 2004. "Time-Varying Travel Times in Vehicle Routing," Transportation Science, INFORMS, vol. 38(2), pages 160-173, May.
    4. Chryssi Malandraki & Mark S. Daskin, 1992. "Time Dependent Vehicle Routing Problems: Formulations, Properties and Heuristic Algorithms," Transportation Science, INFORMS, vol. 26(3), pages 185-200, August.
    5. S. Lin & B. W. Kernighan, 1973. "An Effective Heuristic Algorithm for the Traveling-Salesman Problem," Operations Research, INFORMS, vol. 21(2), pages 498-516, April.
    6. Remy Spliet & Said Dabia & Tom Van Woensel, 2018. "The Time Window Assignment Vehicle Routing Problem with Time-Dependent Travel Times," Transportation Science, INFORMS, vol. 52(2), pages 261-276, March.
    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. Furini, Fabio & Persiani, Carlo Alfredo & Toth, Paolo, 2016. "The Time Dependent Traveling Salesman Planning Problem in Controlled Airspace," Transportation Research Part B: Methodological, Elsevier, vol. 90(C), pages 38-55.
    2. Liu, Yiming & Yu, Yang & Baldacci, Roberto & Tang, Jiafu & Sun, Wei, 2025. "Optimizing carbon emissions in green logistics for time-dependent routing," Transportation Research Part B: Methodological, Elsevier, vol. 192(C).
    3. Van Woensel, T. & Kerbache, L. & Peremans, H. & Vandaele, N., 2008. "Vehicle routing with dynamic travel times: A queueing approach," European Journal of Operational Research, Elsevier, vol. 186(3), pages 990-1007, May.
    4. Lu, Jiawei & Nie, Qinghui & Mahmoudi, Monirehalsadat & Ou, Jishun & Li, Chongnan & Zhou, Xuesong Simon, 2022. "Rich arc routing problem in city logistics: Models and solution algorithms using a fluid queue-based time-dependent travel time representation," Transportation Research Part B: Methodological, Elsevier, vol. 166(C), pages 143-182.
    5. Andres Figliozzi, Miguel, 2012. "The time dependent vehicle routing problem with time windows: Benchmark problems, an efficient solution algorithm, and solution characteristics," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 48(3), pages 616-636.
    6. Vidal, Thibaut & Crainic, Teodor Gabriel & Gendreau, Michel & Prins, Christian, 2013. "Heuristics for multi-attribute vehicle routing problems: A survey and synthesis," European Journal of Operational Research, Elsevier, vol. 231(1), pages 1-21.
    7. Rifki, Omar & Chiabaut, Nicolas & Solnon, Christine, 2020. "On the impact of spatio-temporal granularity of traffic conditions on the quality of pickup and delivery optimal tours," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 142(C).
    8. LIAN, Ying & LUCAS, Flavien & SÖRENSEN, Kenneth, 2022. "The on-demand bus routing problem with real-time traffic information," Working Papers 2022003, University of Antwerp, Faculty of Business and Economics.
    9. Albiach, José & Sanchis, José Marí­a & Soler, David, 2008. "An asymmetric TSP with time windows and with time-dependent travel times and costs: An exact solution through a graph transformation," European Journal of Operational Research, Elsevier, vol. 189(3), pages 789-802, September.
    10. Xiao, Yiyong & Konak, Abdullah, 2016. "The heterogeneous green vehicle routing and scheduling problem with time-varying traffic congestion," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 88(C), pages 146-166.
    11. Daqing Wu & Chenxiang Wu, 2022. "Research on the Time-Dependent Split Delivery Green Vehicle Routing Problem for Fresh Agricultural Products with Multiple Time Windows," Agriculture, MDPI, vol. 12(6), pages 1-28, May.
    12. Huang, Yixiao & Zhao, Lei & Van Woensel, Tom & Gross, Jean-Philippe, 2017. "Time-dependent vehicle routing problem with path flexibility," Transportation Research Part B: Methodological, Elsevier, vol. 95(C), pages 169-195.
    13. Dong Lei & Zhen Yang & Tao Jia, 2025. "Integrating incentive-driven delivery options and time-dependent routing decisions with availability profiles," Operational Research, Springer, vol. 25(3), pages 1-40, September.
    14. Said Dabia & Stefan Ropke & Tom van Woensel & Ton De Kok, 2013. "Branch and Price for the Time-Dependent Vehicle Routing Problem with Time Windows," Transportation Science, INFORMS, vol. 47(3), pages 380-396, August.
    15. Cavaliere, Francesco & Fischetti, Matteo & Roberti, Roberto & Salvagnin, Domenico, 2026. "Models and algorithms for the Time Window Assignment Traveling Salesperson Problem with stochastic travel times," European Journal of Operational Research, Elsevier, vol. 329(1), pages 96-111.
    16. Anke Stieber & Armin Fügenschuh, 2022. "Dealing with time in the multiple traveling salespersons problem with moving targets," Central European Journal of Operations Research, Springer;Slovak Society for Operations Research;Hungarian Operational Research Society;Czech Society for Operations Research;Österr. Gesellschaft für Operations Research (ÖGOR);Slovenian Society Informatika - Section for Operational Research;Croatian Operational Research Society, vol. 30(3), pages 991-1017, September.
    17. Jean-François Cordeau & Gianpaolo Ghiani & Emanuela Guerriero, 2014. "Analysis and Branch-and-Cut Algorithm for the Time-Dependent Travelling Salesman Problem," Transportation Science, INFORMS, vol. 48(1), pages 46-58, February.
    18. Sandra Zajac, 2018. "On a two-phase solution approach for the bi-objective k-dissimilar vehicle routing problem," Journal of Heuristics, Springer, vol. 24(3), pages 515-550, June.
    19. Ichoua, Soumia & Gendreau, Michel & Potvin, Jean-Yves, 2003. "Vehicle dispatching with time-dependent travel times," European Journal of Operational Research, Elsevier, vol. 144(2), pages 379-396, January.
    20. Malandraki, Chryssi & Dial, Robert B., 1996. "A restricted dynamic programming heuristic algorithm for the time dependent traveling salesman problem," European Journal of Operational Research, Elsevier, vol. 90(1), pages 45-55, April.

    More about this item

    Statistics

    Access and download statistics

    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:wly:jnljam:v:2018:y:2018:i:1:n:2453185. 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: Wiley Content Delivery (email available below). General contact details of provider: https://onlinelibrary.wiley.com/journal/4185 .

    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.