IDEAS home Printed from https://ideas.repec.org/a/hin/complx/3813912.html
   My bibliography  Save this article

The Multiagent Planning Problem

Author

Listed:
  • Tamás Kalmár-Nagy
  • Giovanni Giardini
  • Bendegúz Dezső Bak

Abstract

The classical Multiple Traveling Salesmen Problem is a well-studied optimization problem. Given a set of goals/targets and agents, the objective is to find round trips, such that each target is visited only once and by only one agent, and the total distance of these round trips is minimal. In this paper we describe the Multiagent Planning Problem, a variant of the classical Multiple Traveling Salesmen Problem: given a set of goals/targets and a team of agents, subtours (simple paths) are sought such that each target is visited only once and by only one agent. We optimize for minimum time rather than minimum total distance; therefore the objective is to find the Team Plan in which the longest subtour is as short as possible (a min–max problem). We propose an easy to implement Genetic Algorithm Inspired Descent (GAID) method which evolves a set of subtours using genetic operators. We benchmarked GAID against other evolutionary algorithms and heuristics. GAID outperformed the Ant Colony Optimization and the Modified Genetic Algorithm. Even though the heuristics specifically developed for Multiple Traveling Salesmen Problem (e.g., -split, bisection) outperformed GAID, these methods cannot solve the Multiagent Planning Problem. GAID proved to be much better than an open-source Matlab Multiple Traveling Salesmen Problem solver.

Suggested Citation

  • Tamás Kalmár-Nagy & Giovanni Giardini & Bendegúz Dezső Bak, 2017. "The Multiagent Planning Problem," Complexity, Hindawi, vol. 2017, pages 1-12, February.
    • Handle: RePEc:hin:complx:3813912
    DOI: 10.1155/2017/3813912
    as

    Download full text from publisher

    File URL: http://downloads.hindawi.com/journals/8503/2017/3813912.pdf
    Download Restriction: no
    File URL: http://downloads.hindawi.com/journals/8503/2017/3813912.xml
    Download Restriction: no
    File URL: https://libkey.io/10.1155/2017/3813912?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. Tang, Lixin & Liu, Jiyin & Rong, Aiying & Yang, Zihou, 2000. "A multiple traveling salesman problem model for hot rolling scheduling in Shanghai Baoshan Iron & Steel Complex," European Journal of Operational Research, Elsevier, vol. 124(2), pages 267-282, July.
    2. Gerhard Reinelt, 1991. "TSPLIB—A Traveling Salesman Problem Library," INFORMS Journal on Computing, INFORMS, vol. 3(4), pages 376-384, November.
    3. Carter, Arthur E. & Ragsdale, Cliff T., 2002. "Scheduling pre-printed newspaper advertising inserts using genetic algorithms," Omega, Elsevier, vol. 30(6), pages 415-421, December.
    4. Samuel Gorenstein, 1970. "Printing Press Scheduling for Multi-Edition Periodicals," Management Science, INFORMS, vol. 16(6), pages 373-383, February.
    5. Bektas, Tolga, 2006. "The multiple traveling salesman problem: an overview of formulations and solution procedures," Omega, Elsevier, vol. 34(3), pages 209-219, June.
    6. Carter, Arthur E. & Ragsdale, Cliff T., 2006. "A new approach to solving the multiple traveling salesperson problem using genetic algorithms," European Journal of Operational Research, Elsevier, vol. 175(1), pages 246-257, November.
    7. Kara, Imdat & Bektas, Tolga, 2006. "Integer linear programming formulations of multiple salesman problems and its variations," European Journal of Operational Research, Elsevier, vol. 174(3), pages 1449-1458, November.
    8. Evelyn C. Brown & Cliff T. Ragsdale & Arthur E. Carter, 2007. "A Grouping Genetic Algorithm For The Multiple Traveling Salesperson Problem," International Journal of Information Technology & Decision Making (IJITDM), World Scientific Publishing Co. Pte. Ltd., vol. 6(02), pages 333-347.
    9. Bezalel Gavish & Kizhanathan Srikanth, 1986. "An Optimal Solution Method for Large-Scale Multiple Traveling Salesmen Problems," Operations Research, INFORMS, vol. 34(5), pages 698-717, October.
    10. Saman Hong & Manfred W. Padberg, 1977. "Technical Note—A Note on the Symmetric Multiple Traveling Salesman Problem with Fixed Charges," Operations Research, INFORMS, vol. 25(5), pages 871-874, October.
    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. José Alejandro Cornejo-Acosta & Jesús García-Díaz & Julio César Pérez-Sansalvador & Carlos Segura, 2023. "Compact Integer Programs for Depot-Free Multiple Traveling Salesperson Problems," Mathematics, MDPI, vol. 11(13), pages 1-25, July.
    2. Yuan, Shuai & Skinner, Bradley & Huang, Shoudong & Liu, Dikai, 2013. "A new crossover approach for solving the multiple travelling salesmen problem using genetic algorithms," European Journal of Operational Research, Elsevier, vol. 228(1), pages 72-82.
    3. Haluk Yapicioglu, 2018. "Multiperiod Multi Traveling Salesmen Problem Considering Time Window Constraints with an Application to a Real World Case," Networks and Spatial Economics, Springer, vol. 18(4), pages 773-801, December.
    4. Enrique Benavent & Antonio Martínez, 2013. "Multi-depot Multiple TSP: a polyhedral study and computational results," Annals of Operations Research, Springer, vol. 207(1), pages 7-25, August.
    5. Bektas, Tolga, 2006. "The multiple traveling salesman problem: an overview of formulations and solution procedures," Omega, Elsevier, vol. 34(3), pages 209-219, June.
    6. He, Pengfei & Hao, Jin-Kao, 2023. "Memetic search for the minmax multiple traveling salesman problem with single and multiple depots," European Journal of Operational Research, Elsevier, vol. 307(3), pages 1055-1070.
    7. F. Angel-Bello & Y. Cardona-Valdés & A. Álvarez, 2019. "Mixed integer formulations for the multiple minimum latency problem," Operational Research, Springer, vol. 19(2), pages 369-398, June.
    8. Muren, & Wu, Jianjun & Zhou, Li & Du, Zhiping & Lv, Ying, 2019. "Mixed steepest descent algorithm for the traveling salesman problem and application in air logistics," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 126(C), pages 87-102.
    9. Kara, Imdat & Bektas, Tolga, 2006. "Integer linear programming formulations of multiple salesman problems and its variations," European Journal of Operational Research, Elsevier, vol. 174(3), pages 1449-1458, November.
    10. Tuğçe Uzun Kocamiş & Gülçin Yildirim, 2016. "Sustainability Reporting in Turkey: Analysis of Companies in the BIST Sustainability Index," European Journal of Economics and Business Studies Articles, Revistia Research and Publishing, vol. 2, ejes_v2_i.
    11. Culley, D.M. & Funke, S.W. & Kramer, S.C. & Piggott, M.D., 2016. "Integration of cost modelling within the micro-siting design optimisation of tidal turbine arrays," Renewable Energy, Elsevier, vol. 85(C), pages 215-227.
    12. Khalid Mekamcha & Mehdi Souier & Hakim Nadhir Bessenouci & Mohammed Bennekrouf, 2021. "Two metaheuristics approaches for solving the traveling salesman problem: an Algerian waste collection case," Operational Research, Springer, vol. 21(3), pages 1641-1661, September.
    13. Burger, M. & Su, Z. & De Schutter, B., 2018. "A node current-based 2-index formulation for the fixed-destination multi-depot travelling salesman problem," European Journal of Operational Research, Elsevier, vol. 265(2), pages 463-477.
    14. William Cook & Sanjeeb Dash & Ricardo Fukasawa & Marcos Goycoolea, 2009. "Numerically Safe Gomory Mixed-Integer Cuts," INFORMS Journal on Computing, INFORMS, vol. 21(4), pages 641-649, November.
    15. Thiago Serra & Ryan J. O’Neil, 2020. "MIPLIBing: Seamless Benchmarking of Mathematical Optimization Problems and Metadata Extensions," SN Operations Research Forum, Springer, vol. 1(3), pages 1-6, September.
    16. Barbato, Michele & Gouveia, Luís, 2024. "The Hamiltonian p-median problem: Polyhedral results and branch-and-cut algorithms," European Journal of Operational Research, Elsevier, vol. 316(2), pages 473-487.
    17. S Salhi & A Al-Khedhairi, 2010. "Integrating heuristic information into exact methods: The case of the vertex p-centre problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 61(11), pages 1619-1631, November.
    18. Marilène Cherkesly & Claudio Contardo, 2021. "The conditional p-dispersion problem," Journal of Global Optimization, Springer, vol. 81(1), pages 23-83, September.
    19. Malaguti, Enrico & Martello, Silvano & Santini, Alberto, 2018. "The traveling salesman problem with pickups, deliveries, and draft limits," Omega, Elsevier, vol. 74(C), pages 50-58.
    20. Bernardino, Raquel & Paias, Ana, 2018. "Solving the family traveling salesman problem," European Journal of Operational Research, Elsevier, vol. 267(2), pages 453-466.

    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:hin:complx:3813912. 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: Mohamed Abdelhakeem (email available below). General contact details of provider: https://www.hindawi.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.