IDEAS home Printed from https://ideas.repec.org/a/spr/annopr/v157y2008i1p105-13310.1007-s10479-007-0199-8.html
   My bibliography  Save this article

Multi-start and path relinking methods to deal with multiobjective knapsack problems

Author

Listed:
  • Ricardo Beausoleil
  • Gulnara Baldoquin
  • Rodolfo Montejo

Abstract

This paper deals with a multiobjective combinatorial optimization problem called Extended Knapsack Problem. By applying multi-start search and path relinking we rapidly guide the search toward the most balanced zone of the Pareto-optimal front. The Pareto relation is applied in order to designate a subset of the best generated solutions to be the current efficient set of solutions. The max-min criterion with the Hamming distance is used as a measure of dissimilarity in order to find diverse solutions to be combined. The performance of our approach is compared with several state-of-the-art MOEAs for a suite test problems taken from the literature. Copyright Springer Science+Business Media, LLC 2008

Suggested Citation

  • Ricardo Beausoleil & Gulnara Baldoquin & Rodolfo Montejo, 2008. "Multi-start and path relinking methods to deal with multiobjective knapsack problems," Annals of Operations Research, Springer, vol. 157(1), pages 105-133, January.
  • Handle: RePEc:spr:annopr:v:157:y:2008:i:1:p:105-133:10.1007/s10479-007-0199-8
    DOI: 10.1007/s10479-007-0199-8
    as

    Download full text from publisher

    File URL: http://hdl.handle.net/10.1007/s10479-007-0199-8
    Download Restriction: Access to full text is restricted to subscribers.

    File URL: https://libkey.io/10.1007/s10479-007-0199-8?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. Beausoleil, Ricardo P., 2006. ""MOSS" multiobjective scatter search applied to non-linear multiple criteria optimization," European Journal of Operational Research, Elsevier, vol. 169(2), pages 426-449, 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. Michael Johnson & David Turcotte & Felicia Sullivan, 2010. "What Foreclosed Homes Should a Municipality Purchase to Stabilize Vulnerable Neighborhoods?," Networks and Spatial Economics, Springer, vol. 10(3), pages 363-388, September.
    2. Martí, Rafael & Resende, Mauricio G.C. & Ribeiro, Celso C., 2013. "Multi-start methods for combinatorial optimization," European Journal of Operational Research, Elsevier, vol. 226(1), pages 1-8.

    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. 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.
    2. Keliang Chang & Hong Zhou & Guijing Chen & Huiqin Chen, 2017. "Multiobjective Location Routing Problem considering Uncertain Data after Disasters," Discrete Dynamics in Nature and Society, Hindawi, vol. 2017, pages 1-7, March.
    3. Koutras, V.P. & Platis, A.N. & Gravvanis, G.A., 2009. "Optimal server resource reservation policies for priority classes of users under cyclic non-homogeneous markov modeling," European Journal of Operational Research, Elsevier, vol. 198(2), pages 545-556, October.
    4. Kerkhove, L.-P. & Vanhoucke, M., 2017. "A parallel multi-objective scatter search for optimising incentive contract design in projects," European Journal of Operational Research, Elsevier, vol. 261(3), pages 1066-1084.
    5. Julian Molina & Manuel Laguna & Rafael Martí & Rafael Caballero, 2007. "SSPMO: A Scatter Tabu Search Procedure for Non-Linear Multiobjective Optimization," INFORMS Journal on Computing, INFORMS, vol. 19(1), pages 91-100, February.
    6. Chen, Min-Rong & Lu, Yong-Zai, 2008. "A novel elitist multiobjective optimization algorithm: Multiobjective extremal optimization," European Journal of Operational Research, Elsevier, vol. 188(3), pages 637-651, August.
    7. A. D. López-Sánchez & J. Sánchez-Oro & M. Laguna, 2021. "A New Scatter Search Design for Multiobjective Combinatorial Optimization with an Application to Facility Location," INFORMS Journal on Computing, INFORMS, vol. 33(2), pages 629-642, May.
    8. de Athayde Costa e Silva, Marsil & Klein, Carlos Eduardo & Mariani, Viviana Cocco & dos Santos Coelho, Leandro, 2013. "Multiobjective scatter search approach with new combination scheme applied to solve environmental/economic dispatch problem," Energy, Elsevier, vol. 53(C), pages 14-21.
    9. Wang, Haijun & Du, Lijing & Ma, Shihua, 2014. "Multi-objective open location-routing model with split delivery for optimized relief distribution in post-earthquake," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 69(C), pages 160-179.
    10. A. R. Rahimi-Vahed & S. M. Mirghorbani, 2007. "A multi-objective particle swarm for a flow shop scheduling problem," Journal of Combinatorial Optimization, Springer, vol. 13(1), pages 79-102, January.
    11. Chen, Jianyong & Lin, Qiuzhen & Ji, Zhen, 2010. "A hybrid immune multiobjective optimization algorithm," European Journal of Operational Research, Elsevier, vol. 204(2), pages 294-302, July.
    12. Bekker, James & Aldrich, Chris, 2011. "The cross-entropy method in multi-objective optimisation: An assessment," European Journal of Operational Research, Elsevier, vol. 211(1), pages 112-121, May.

    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:spr:annopr:v:157:y:2008:i:1:p:105-133:10.1007/s10479-007-0199-8. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.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.