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

Anytime Pareto local search

Author

Listed:
  • Dubois-Lacoste, Jérémie
  • López-Ibáñez, Manuel
  • Stützle, Thomas

Abstract

Pareto Local Search (PLS) is a simple and effective local search method for tackling multi-objective combinatorial optimization problems. It is also a crucial component of many state-of-the-art algorithms for such problems. However, PLS may be not very effective when terminated before completion. In other words, PLS has poor anytime behavior. In this paper, we study the effect that various PLS algorithmic components have on its anytime behavior. We show that the anytime behavior of PLS can be greatly improved by using alternative algorithmic components. We also propose Dynagrid, a dynamic discretization of the objective space that helps PLS to converge faster to a good approximation of the Pareto front and continue to improve it if more time is available. We perform a detailed empirical evaluation of the new proposals on the bi-objective traveling salesman problem and the bi-objective quadratic assignment problem. Our results demonstrate that the new PLS variants not only have significantly better anytime behavior than the original PLS, but also may obtain better results for longer computation time or upon completion.

Suggested Citation

  • 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.
    • Handle: RePEc:eee:ejores:v:243:y:2015:i:2:p:369-385
    DOI: 10.1016/j.ejor.2014.10.062
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221714009011
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2014.10.062?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. Beume, Nicola & Naujoks, Boris & Emmerich, Michael, 2007. "SMS-EMOA: Multiobjective selection based on dominated hypervolume," European Journal of Operational Research, Elsevier, vol. 181(3), pages 1653-1669, September.
    2. 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.
    3. Verel, Sébastien & Liefooghe, Arnaud & Jourdan, Laetitia & Dhaenens, Clarisse, 2013. "On the structure of multiobjective combinatorial search space: MNK-landscapes with correlated objectives," European Journal of Operational Research, Elsevier, vol. 227(2), pages 331-342.
    4. Loudni, Samir & Boizumault, Patrice, 2008. "Combining VNS with constraint programming for solving anytime optimization problems," European Journal of Operational Research, Elsevier, vol. 191(3), pages 705-735, December.
    5. Hansen, Pierre & Mladenovic, Nenad, 2001. "Variable neighborhood search: Principles and applications," European Journal of Operational Research, Elsevier, vol. 130(3), pages 449-467, May.
    6. Laumanns, Marco & Zenklusen, Rico, 2011. "Stochastic convergence of random search methods to fixed size Pareto front approximations," European Journal of Operational Research, Elsevier, vol. 213(2), pages 414-421, September.
    7. Matthias Ehrgott & Xavier Gandibleux, 2004. "Approximative solution methods for multiobjective combinatorial optimization," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 12(1), pages 1-63, 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. 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.
    2. 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.
    3. 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.
    4. Lamiaa Dahite & Abdeslam Kadrani & Rachid Benmansour & Rym Nesrine Guibadj & Cyril Fonlupt, 2022. "Multi-Objective Model and Variable Neighborhood Search Algorithms for the Joint Maintenance Scheduling and Workforce Routing Problem," Mathematics, MDPI, vol. 10(11), pages 1-37, May.
    5. Pablo A. Miranda-Gonzalez & Javier Maturana-Ross & Carola A. Blazquez & Guillermo Cabrera-Guerrero, 2021. "Exact Formulation and Analysis for the Bi-Objective Insular Traveling Salesman Problem," Mathematics, MDPI, vol. 9(21), pages 1-33, October.
    6. Eduardo Álvarez-Miranda & Camilo Campos-Valdés & Maurcio Morales Quiroga & Matías Moreno-Faguett & Jordi Pereira, 2020. "A Multi-Criteria Pen for Drawing Fair Districts: When Democratic and Demographic Fairness Matter," Mathematics, MDPI, vol. 8(9), pages 1-26, August.
    7. Jaszkiewicz, Andrzej, 2018. "Many-Objective Pareto Local Search," European Journal of Operational Research, Elsevier, vol. 271(3), pages 1001-1013.
    8. Alexandre D. Jesus & Luís Paquete & Arnaud Liefooghe, 2021. "A model of anytime algorithm performance for bi-objective optimization," Journal of Global Optimization, Springer, vol. 79(2), pages 329-350, February.

    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. Yeudiel Lara Moreno & Carlos Ignacio Hernández Castellanos, 2024. "A Hierarchical Approach to a Tri-Objective Portfolio Optimization Problem Considering an ESG Index," Mathematics, MDPI, vol. 12(19), pages 1-16, October.
    2. Derbel, Bilel & Humeau, Jérémie & Liefooghe, Arnaud & Verel, Sébastien, 2014. "Distributed localized bi-objective search," European Journal of Operational Research, Elsevier, vol. 239(3), pages 731-743.
    3. 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.
    4. Cosson, Raphaël & Santana, Roberto & Derbel, Bilel & Liefooghe, Arnaud, 2024. "On bi-objective combinatorial optimization with heterogeneous objectives," European Journal of Operational Research, Elsevier, vol. 319(1), pages 89-101.
    5. Pierre Hansen & Nenad Mladenović & José Moreno Pérez, 2010. "Variable neighbourhood search: methods and applications," Annals of Operations Research, Springer, vol. 175(1), pages 367-407, March.
    6. Verel, Sébastien & Liefooghe, Arnaud & Jourdan, Laetitia & Dhaenens, Clarisse, 2013. "On the structure of multiobjective combinatorial search space: MNK-landscapes with correlated objectives," European Journal of Operational Research, Elsevier, vol. 227(2), pages 331-342.
    7. Maenhout, Broos & Vanhoucke, Mario, 2010. "A hybrid scatter search heuristic for personalized crew rostering in the airline industry," European Journal of Operational Research, Elsevier, vol. 206(1), pages 155-167, October.
    8. Liagkouras, Konstantinos & Metaxiotis, Konstantinos, 2021. "Improving multi-objective algorithms performance by emulating behaviors from the human social analogue in candidate solutions," European Journal of Operational Research, Elsevier, vol. 292(3), pages 1019-1036.
    9. Manlio Gaudioso & Giovanni Giallombardo & Giovanna Miglionico, 2018. "Minimizing Piecewise-Concave Functions Over Polyhedra," Mathematics of Operations Research, INFORMS, vol. 43(2), pages 580-597, May.
    10. 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.
    11. Fernandez del Pozo, J. A. & Bielza, C. & Gomez, M., 2005. "A list-based compact representation for large decision tables management," European Journal of Operational Research, Elsevier, vol. 160(3), pages 638-662, February.
    12. Amina Lamghari & Roussos Dimitrakopoulos & Jacques Ferland, 2015. "A hybrid method based on linear programming and variable neighborhood descent for scheduling production in open-pit mines," Journal of Global Optimization, Springer, vol. 63(3), pages 555-582, November.
    13. J. Redondo & J. Fernández & I. García & P. Ortigosa, 2009. "A robust and efficient algorithm for planar competitive location problems," Annals of Operations Research, Springer, vol. 167(1), pages 87-105, March.
    14. López-Ibáñez, Manuel & Stützle, Thomas, 2014. "Automatically improving the anytime behaviour of optimisation algorithms," European Journal of Operational Research, Elsevier, vol. 235(3), pages 569-582.
    15. Patricia Domínguez-Marín & Stefan Nickel & Pierre Hansen & Nenad Mladenović, 2005. "Heuristic Procedures for Solving the Discrete Ordered Median Problem," Annals of Operations Research, Springer, vol. 136(1), pages 145-173, April.
    16. Gong, Wenyin & Cai, Zhihua, 2009. "An improved multiobjective differential evolution based on Pareto-adaptive [epsilon]-dominance and orthogonal design," European Journal of Operational Research, Elsevier, vol. 198(2), pages 576-601, October.
    17. Ali Shahabi & Sadigh Raissi & Kaveh Khalili-Damghani & Meysam Rafei, 2021. "Designing a resilient skip-stop schedule in rapid rail transit using a simulation-based optimization methodology," Operational Research, Springer, vol. 21(3), pages 1691-1721, September.
    18. Janssens, Jochen & Talarico, Luca & Sörensen, Kenneth, 2016. "A hybridised variable neighbourhood tabu search heuristic to increase security in a utility network," Reliability Engineering and System Safety, Elsevier, vol. 145(C), pages 221-230.
    19. Wilson, Duncan T. & Hawe, Glenn I. & Coates, Graham & Crouch, Roger S., 2013. "A multi-objective combinatorial model of casualty processing in major incident response," European Journal of Operational Research, Elsevier, vol. 230(3), pages 643-655.
    20. Felipe, Ángel & Ortuño, M. Teresa & Righini, Giovanni & Tirado, Gregorio, 2014. "A heuristic approach for the green vehicle routing problem with multiple technologies and partial recharges," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 71(C), pages 111-128.

    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:243:y:2015:i:2:p:369-385. 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.