IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v271y2018i3p1001-1013.html
   My bibliography  Save this article

Many-Objective Pareto Local Search

Author

Listed:
  • Jaszkiewicz, Andrzej

Abstract

We propose a new Pareto Local Search Algorithm for the many-objective combinatorial optimization. Pareto Local Search proved to be a very effective tool in the case of the bi-objective combinatorial optimization and it was used in a number of the state-of-the-art algorithms for problems of this kind. On the other hand, the standard Pareto Local Search algorithm becomes very inefficient for problems with more than two objectives. We build an effective Many-Objective Pareto Local Search algorithm using three new mechanisms: the efficient update of large Pareto archives with ND-Tree data structure, a new mechanism for the selection of the promising solutions for the neighborhood exploration, and a partial exploration of the neighborhoods. We apply the proposed algorithm to the instances of two different problems, i.e. the traveling salesperson problem and the traveling salesperson problem with profits with up to 5 objectives showing high effectiveness of the proposed algorithm.

Suggested Citation

  • Jaszkiewicz, Andrzej, 2018. "Many-Objective Pareto Local Search," European Journal of Operational Research, Elsevier, vol. 271(3), pages 1001-1013.
    • Handle: RePEc:eee:ejores:v:271:y:2018:i:3:p:1001-1013
    DOI: 10.1016/j.ejor.2018.06.009
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221718305320
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2018.06.009?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. Bérubé, Jean-François & Gendreau, Michel & Potvin, Jean-Yves, 2009. "An exact [epsilon]-constraint method for bi-objective combinatorial optimization problems: Application to the Traveling Salesman Problem with Profits," European Journal of Operational Research, Elsevier, vol. 194(1), pages 39-50, April.
    2. Dubois-Lacoste, Jérémie & López-Ibáñez, Manuel & Stützle, Thomas, 2015. "Anytime Pareto local search," European Journal of Operational Research, Elsevier, vol. 243(2), pages 369-385.
    3. Paquete, Luis & Stutzle, Thomas, 2006. "A study of stochastic local search algorithms for the biobjective QAP with correlated flow matrices," European Journal of Operational Research, Elsevier, vol. 169(3), pages 943-959, March.
    4. 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.
    5. Christos Voudouris & Edward P.K. Tsang & Abdullah Alsheddy, 2010. "Guided Local Search," International Series in Operations Research & Management Science, in: Michel Gendreau & Jean-Yves Potvin (ed.), Handbook of Metaheuristics, chapter 0, pages 321-361, Springer.
    6. Dominique Feillet & Pierre Dejax & Michel Gendreau, 2005. "Traveling Salesman Problems with Profits," Transportation Science, INFORMS, vol. 39(2), pages 188-205, May.
    7. Luis Paquete & Tommaso Schiavinotto & Thomas Stützle, 2007. "On local optima in multiobjective combinatorial optimization problems," Annals of Operations Research, Springer, vol. 156(1), pages 83-97, December.
    8. Andrzej Jaszkiewicz & Thibaut Lust, 2017. "Proper balance between search towards and along Pareto front: biobjective TSP case study," Annals of Operations Research, Springer, vol. 254(1), pages 111-130, July.
    9. Mori, Masakatsu & Kobayashi, Ryoji & Samejima, Masaki & Komoda, Norihisa, 2017. "Risk-cost optimization for procurement planning in multi-tier supply chain by Pareto Local Search with relaxed acceptance criterion," European Journal of Operational Research, Elsevier, vol. 261(1), pages 88-96.
    10. Jaszkiewicz, Andrzej & Zielniewicz, Piotr, 2009. "Pareto memetic algorithm with path relinking for bi-objective traveling salesperson problem," European Journal of Operational Research, Elsevier, vol. 193(3), pages 885-890, March.
    11. Jaszkiewicz, Andrzej, 2002. "Genetic local search for multi-objective combinatorial optimization," European Journal of Operational Research, Elsevier, vol. 137(1), pages 50-71, 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. Diaz, Juan Esteban & López-Ibáñez, Manuel, 2021. "Incorporating decision-maker’s preferences into the automatic configuration of bi-objective optimisation algorithms," European Journal of Operational Research, Elsevier, vol. 289(3), pages 1209-1222.

    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. Andrzej Jaszkiewicz & Thibaut Lust, 2017. "Proper balance between search towards and along Pareto front: biobjective TSP case study," Annals of Operations Research, Springer, vol. 254(1), pages 111-130, July.
    2. Florios, Kostas & Mavrotas, George, 2014. "Generation of the exact Pareto set in multi-objective traveling salesman and set covering problems," MPRA Paper 105074, University Library of Munich, Germany.
    3. Aritra Pal & Hadi Charkhgard, 2019. "A Feasibility Pump and Local Search Based Heuristic for Bi-Objective Pure Integer Linear Programming," INFORMS Journal on Computing, INFORMS, vol. 31(1), pages 115-133, February.
    4. Nicolas Jozefowiez & Gilbert Laporte & Frédéric Semet, 2012. "A Generic Branch-and-Cut Algorithm for Multiobjective Optimization Problems: Application to the Multilabel Traveling Salesman Problem," INFORMS Journal on Computing, INFORMS, vol. 24(4), pages 554-564, November.
    5. Archetti, Claudia & Corberán, Ángel & Plana, Isaac & Sanchis, José Maria & Speranza, M. Grazia, 2015. "A matheuristic for the Team Orienteering Arc Routing Problem," European Journal of Operational Research, Elsevier, vol. 245(2), pages 392-401.
    6. Manerba, Daniele & Mansini, Renata & Riera-Ledesma, Jorge, 2017. "The Traveling Purchaser Problem and its variants," European Journal of Operational Research, Elsevier, vol. 259(1), pages 1-18.
    7. Diclehan Tezcaner Öztürk & Murat Köksalan, 2016. "An interactive approach for biobjective integer programs under quasiconvex preference functions," Annals of Operations Research, Springer, vol. 244(2), pages 677-696, September.
    8. 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.
    9. Mădălina M. Drugan, 2018. "Scaling-up many-objective combinatorial optimization with Cartesian products of scalarization functions," Journal of Heuristics, Springer, vol. 24(2), pages 135-172, April.
    10. Mori, Masakatsu & Kobayashi, Ryoji & Samejima, Masaki & Komoda, Norihisa, 2017. "Risk-cost optimization for procurement planning in multi-tier supply chain by Pareto Local Search with relaxed acceptance criterion," European Journal of Operational Research, Elsevier, vol. 261(1), pages 88-96.
    11. Lakmali Weerasena & Aniekan Ebiefung & Anthony Skjellum, 2022. "Design of a heuristic algorithm for the generalized multi-objective set covering problem," Computational Optimization and Applications, Springer, vol. 82(3), pages 717-751, July.
    12. Calvete, Herminia I. & Galé, Carmen & Iranzo, José A., 2016. "MEALS: A multiobjective evolutionary algorithm with local search for solving the bi-objective ring star problem," European Journal of Operational Research, Elsevier, vol. 250(2), pages 377-388.
    13. Diaz, Juan Esteban & López-Ibáñez, Manuel, 2021. "Incorporating decision-maker’s preferences into the automatic configuration of bi-objective optimisation algorithms," European Journal of Operational Research, Elsevier, vol. 289(3), pages 1209-1222.
    14. Angelelli, E. & Archetti, C. & Vindigni, M., 2014. "The Clustered Orienteering Problem," European Journal of Operational Research, Elsevier, vol. 238(2), pages 404-414.
    15. Erfan Babaee Tirkolaee & Alireza Goli & Selma Gütmen & Gerhard-Wilhelm Weber & Katarzyna Szwedzka, 2023. "A novel model for sustainable waste collection arc routing problem: Pareto-based algorithms," Annals of Operations Research, Springer, vol. 324(1), pages 189-214, May.
    16. Bruce Golden & Zahra Naji-Azimi & S. Raghavan & Majid Salari & Paolo Toth, 2012. "The Generalized Covering Salesman Problem," INFORMS Journal on Computing, INFORMS, vol. 24(4), pages 534-553, November.
    17. Aymeric Blot & Marie-Éléonore Kessaci & Laetitia Jourdan, 2018. "Survey and unification of local search techniques in metaheuristics for multi-objective combinatorial optimisation," Journal of Heuristics, Springer, vol. 24(6), pages 853-877, December.
    18. Justus Bonz, 2021. "Application of a multi-objective multi traveling salesperson problem with time windows," Public Transport, Springer, vol. 13(1), pages 35-57, March.
    19. Thomas Kirschstein & Christian Bierwirth, 2018. "The selective Traveling Salesman Problem with emission allocation rules," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 40(1), pages 97-124, January.
    20. Miranda, Pablo A. & Blazquez, Carola A. & Obreque, Carlos & Maturana-Ross, Javier & Gutierrez-Jarpa, Gabriel, 2018. "The bi-objective insular traveling salesman problem with maritime and ground transportation costs," European Journal of Operational Research, Elsevier, vol. 271(3), pages 1014-1036.

    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:ejores:v:271:y:2018:i:3:p:1001-1013. 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/eor .

    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.