IDEAS home Printed from https://ideas.repec.org/a/plo/pone00/0137724.html
   My bibliography  Save this article

Automatic Combination of Operators in a Genetic Algorithm to Solve the Traveling Salesman Problem

Author

Listed:
  • Carlos Contreras-Bolton
  • Victor Parada

Abstract

Genetic algorithms are powerful search methods inspired by Darwinian evolution. To date, they have been applied to the solution of many optimization problems because of the easy use of their properties and their robustness in finding good solutions to difficult problems. The good operation of genetic algorithms is due in part to its two main variation operators, namely, crossover and mutation operators. Typically, in the literature, we find the use of a single crossover and mutation operator. However, there are studies that have shown that using multi-operators produces synergy and that the operators are mutually complementary. Using multi-operators is not a simple task because which operators to use and how to combine them must be determined, which in itself is an optimization problem. In this paper, it is proposed that the task of exploring the different combinations of the crossover and mutation operators can be carried out by evolutionary computing. The crossover and mutation operators used are those typically used for solving the traveling salesman problem. The process of searching for good combinations was effective, yielding appropriate and synergic combinations of the crossover and mutation operators. The numerical results show that the use of the combination of operators obtained by evolutionary computing is better than the use of a single operator and the use of multi-operators combined in the standard way. The results were also better than those of the last operators reported in the literature.

Suggested Citation

  • Carlos Contreras-Bolton & Victor Parada, 2015. "Automatic Combination of Operators in a Genetic Algorithm to Solve the Traveling Salesman Problem," PLOS ONE, Public Library of Science, vol. 10(9), pages 1-25, September.
  • Handle: RePEc:plo:pone00:0137724
    DOI: 10.1371/journal.pone.0137724
    as

    Download full text from publisher

    File URL: https://journals.plos.org/plosone/article?id=10.1371/journal.pone.0137724
    Download Restriction: no

    File URL: https://journals.plos.org/plosone/article/file?id=10.1371/journal.pone.0137724&type=printable
    Download Restriction: no

    File URL: https://libkey.io/10.1371/journal.pone.0137724?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. Merrill M. Flood, 1956. "The Traveling-Salesman Problem," Operations Research, INFORMS, vol. 4(1), pages 61-75, February.
    2. Carlos Contreras Bolton & Gustavo Gatica & Víctor Parada, 2013. "Automatically Generated Algorithms for the Vertex Coloring Problem," PLOS ONE, Public Library of Science, vol. 8(3), pages 1-9, March.
    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. Zengliang Han & Dongqing Wang & Feng Liu & Zhiyong Zhao, 2017. "Multi-AGV path planning with double-path constraints by using an improved genetic algorithm," PLOS ONE, Public Library of Science, vol. 12(7), pages 1-16, July.
    2. Cacchiani, Valentina & Contreras-Bolton, Carlos & Toth, Paolo, 2020. "Models and algorithms for the Traveling Salesman Problem with Time-dependent Service times," European Journal of Operational Research, Elsevier, vol. 283(3), pages 825-843.
    3. Yujia Ge & Bin Xu, 2016. "Dynamic Staffing and Rescheduling in Software Project Management: A Hybrid Approach," PLOS ONE, Public Library of Science, vol. 11(6), pages 1-28, June.

    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. Lei, Chao & Ouyang, Yanfeng, 2024. "Average minimum distance to visit a subset of random points in a compact region," Transportation Research Part B: Methodological, Elsevier, vol. 181(C).
    2. Neves-Moreira, Fábio & Almada-Lobo, Bernardo & Guimarães, Luís & Amorim, Pedro, 2022. "The multi-product inventory-routing problem with pickups and deliveries: Mitigating fluctuating demand via rolling horizon heuristics," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 164(C).
    3. Herer, Yale T., 1999. "Submodularity and the traveling salesman problem," European Journal of Operational Research, Elsevier, vol. 114(3), pages 489-508, May.
    4. Arthur Charpentier & Romuald Élie & Carl Remlinger, 2023. "Reinforcement Learning in Economics and Finance," Computational Economics, Springer;Society for Computational Economics, vol. 62(1), pages 425-462, June.
    5. Bergmann, Felix M. & Wagner, Stephan M. & Winkenbach, Matthias, 2020. "Integrating first-mile pickup and last-mile delivery on shared vehicle routes for efficient urban e-commerce distribution," Transportation Research Part B: Methodological, Elsevier, vol. 131(C), pages 26-62.
    6. Doppstadt, C. & Koberstein, A. & Vigo, D., 2016. "The Hybrid Electric Vehicle – Traveling Salesman Problem," European Journal of Operational Research, Elsevier, vol. 253(3), pages 825-842.
    7. Chen, Hanwen & Liu, Siyi & Wang, Junjie & Wu, Zhijuan, 2022. "The effect of geographic proximity on corporate tax avoidance: Evidence from China," Journal of Corporate Finance, Elsevier, vol. 72(C).
    8. Maximilian Zähringer & Sebastian Wolff & Jakob Schneider & Georg Balke & Markus Lienkamp, 2022. "Time vs. Capacity—The Potential of Optimal Charging Stop Strategies for Battery Electric Trucks," Energies, MDPI, vol. 15(19), pages 1-18, September.
    9. Jose Gonzalez-Velarde & Salvador Garcia-Lumbreras & Alberto Garcia-Diaz, 2008. "A multi-stop routing problem," Annals of Operations Research, Springer, vol. 157(1), pages 153-167, January.
    10. Burcu B. Keskin & İbrahim Çapar & Charles R. Sox & Nickolas K. Freeman, 2014. "An Integrated Load-Planning Algorithm for Outbound Logistics at Webb Wheel," Interfaces, INFORMS, vol. 44(5), pages 480-497, October.
    11. Cristina Maria Păcurar & Ruxandra-Gabriela Albu & Victor Dan Păcurar, 2021. "Tourist Route Optimization in the Context of Covid-19 Pandemic," Sustainability, MDPI, vol. 13(10), pages 1-17, May.
    12. Kemal Ihsan Kilic & Leonardo Mostarda, 2022. "Novel Concave Hull-Based Heuristic Algorithm For TSP," SN Operations Research Forum, Springer, vol. 3(2), pages 1-45, June.
    13. Alonso Tabares, Diego & Mora-Camino, Felix & Drouin, Antoine, 2021. "A multi-time scale management structure for airport ground handling automation," Journal of Air Transport Management, Elsevier, vol. 90(C).
    14. Gendreau, Michel & Laporte, Gilbert & Seguin, Rene, 1996. "Stochastic vehicle routing," European Journal of Operational Research, Elsevier, vol. 88(1), pages 3-12, January.
    15. G Laporte, 2010. "A concise guide to the Traveling Salesman Problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 61(1), pages 35-40, January.
    16. van Lon, Rinde R.S. & Ferrante, Eliseo & Turgut, Ali E. & Wenseleers, Tom & Vanden Berghe, Greet & Holvoet, Tom, 2016. "Measures of dynamism and urgency in logistics," European Journal of Operational Research, Elsevier, vol. 253(3), pages 614-624.
    17. Allahyari, Somayeh & Salari, Majid & Vigo, Daniele, 2015. "A hybrid metaheuristic algorithm for the multi-depot covering tour vehicle routing problem," European Journal of Operational Research, Elsevier, vol. 242(3), pages 756-768.
    18. Hughes, Michael S. & Lunday, Brian J. & Weir, Jeffrey D. & Hopkinson, Kenneth M., 2021. "The multiple shortest path problem with path deconfliction," European Journal of Operational Research, Elsevier, vol. 292(3), pages 818-829.
    19. Arthur Charpentier & Romuald Elie & Carl Remlinger, 2020. "Reinforcement Learning in Economics and Finance," Papers 2003.10014, arXiv.org.
    20. Ioannou, Petros & Giuliano, Genevieve & Dessouky, Maged & Chen, Pengfei & Dexter, Sue, 2020. "Freight Load Balancing and Efficiencies in Alternative Fuel Freight Modes," Institute of Transportation Studies, Working Paper Series qt3ns4b894, Institute of Transportation Studies, UC Davis.

    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:plo:pone00:0137724. 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: plosone (email available below). General contact details of provider: https://journals.plos.org/plosone/ .

    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.