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

MEALS: A multiobjective evolutionary algorithm with local search for solving the bi-objective ring star problem

Author

Listed:
  • Calvete, Herminia I.
  • Galé, Carmen
  • Iranzo, José A.

Abstract

In this paper we develop a hybrid metaheuristic for approaching the Pareto front of the bi-objective ring star problem. This problem consists of finding a simple cycle (ring) through a subset of nodes of a network. The aim is to minimize both the cost of connecting the nodes in the ring and the cost of allocating the nodes not in the ring to nodes in the ring. The algorithm preserves the general characteristics of a multiobjective evolutionary algorithm and embeds a local search procedure which deals with multiple objectives. The encoding scheme utilized leads to solving a Traveling Salesman Problem in order to compute the ring associated with the chromosome. This allows the algorithm to implicitly discard feasible solutions which are not efficient. The algorithm also includes an ad-hoc initial population construction which contributes to diversification. Extensive computational experiments using benchmark problems show the performance of the algorithm and reveal the noteworthy contribution of the local search procedure.

Suggested Citation

  • 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.
    • Handle: RePEc:eee:ejores:v:250:y:2016:i:2:p:377-388
    DOI: 10.1016/j.ejor.2015.09.044
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221715008863
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2015.09.044?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. 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.
    2. Santos, Luís & Coutinho-Rodrigues, João & Current, John R., 2010. "An improved ant colony optimization based algorithm for the capacitated arc routing problem," Transportation Research Part B: Methodological, Elsevier, vol. 44(2), pages 246-266, February.
    3. Calvete, Herminia I. & Galé, Carmen & Iranzo, José A., 2013. "An efficient evolutionary algorithm for the ring star problem," European Journal of Operational Research, Elsevier, vol. 231(1), pages 22-33.
    4. 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.
    5. Helsgaun, Keld, 2000. "An effective implementation of the Lin-Kernighan traveling salesman heuristic," European Journal of Operational Research, Elsevier, vol. 126(1), pages 106-130, October.
    6. Moreno Perez, Jose A. & Marcos Moreno-Vega, J. & Rodriguez Martin, Inmaculada, 2003. "Variable neighborhood tabu search and its application to the median cycle problem," European Journal of Operational Research, Elsevier, vol. 151(2), pages 365-378, December.
    7. J Renaud & F F Boctor & G Laporte, 2004. "Efficient heuristics for Median Cycle Problems," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 55(2), pages 179-186, February.
    8. Jaszkiewicz, Andrzej, 2002. "Genetic local search for multi-objective combinatorial optimization," European Journal of Operational Research, Elsevier, vol. 137(1), pages 50-71, February.
    9. James C. Bean, 1994. "Genetic Algorithms and Random Keys for Sequencing and Optimization," INFORMS Journal on Computing, INFORMS, vol. 6(2), pages 154-160, May.
    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. Herminia I. Calvete & Carmen Galé & José A. Iranzo, 2022. "Approaching the Pareto Front in a Biobjective Bus Route Design Problem Dealing with Routing Cost and Individuals’ Walking Distance by Using a Novel Evolutionary Algorithm," Mathematics, MDPI, vol. 10(9), pages 1-17, April.
    2. 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.
    3. Xujin Chen & Xiaodong Hu & Xiaohua Jia & Zhongzheng Tang & Chenhao Wang & Ying Zhang, 0. "Algorithms for the metric ring star problem with fixed edge-cost ratio," Journal of Combinatorial Optimization, Springer, vol. 0, pages 1-25.
    4. Xujin Chen & Xiaodong Hu & Xiaohua Jia & Zhongzheng Tang & Chenhao Wang & Ying Zhang, 2021. "Algorithms for the metric ring star problem with fixed edge-cost ratio," Journal of Combinatorial Optimization, Springer, vol. 42(3), pages 499-523, October.

    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. Lamb, John D., 2012. "Variable neighbourhood structures for cycle location problems," European Journal of Operational Research, Elsevier, vol. 223(1), pages 15-26.
    2. Calvete, Herminia I. & Galé, Carmen & Iranzo, José A., 2013. "An efficient evolutionary algorithm for the ring star problem," European Journal of Operational Research, Elsevier, vol. 231(1), pages 22-33.
    3. L Vogt & C A Poojari & J E Beasley, 2007. "A tabu search algorithm for the single vehicle routing allocation problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 58(4), pages 467-480, April.
    4. Glock, Katharina & Meyer, Anne, 2023. "Spatial coverage in routing and path planning problems," European Journal of Operational Research, Elsevier, vol. 305(1), pages 1-20.
    5. Escobar, John Willmer & Linfati, Rodrigo & Baldoquin, Maria G. & Toth, Paolo, 2014. "A Granular Variable Tabu Neighborhood Search for the capacitated location-routing problem," Transportation Research Part B: Methodological, Elsevier, vol. 67(C), pages 344-356.
    6. Chen, Yu-Wang & Zhu, Yao-Jia & Yang, Gen-Ke & Lu, Yong-Zai, 2011. "Improved extremal optimization for the asymmetric traveling salesman problem," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 390(23), pages 4459-4465.
    7. Michael Schneider & Michael Drexl, 2017. "A survey of the standard location-routing problem," Annals of Operations Research, Springer, vol. 259(1), pages 389-414, December.
    8. Ghosh, Diptesh, 2016. "Exploring Lin Kernighan neighborhoods for the indexing problem," IIMA Working Papers WP2016-02-13, Indian Institute of Management Ahmedabad, Research and Publication Department.
    9. Jiang, Zhongzhou & Liu, Jing & Wang, Shuai, 2016. "Traveling salesman problems with PageRank Distance on complex networks reveal community structure," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 463(C), pages 293-302.
    10. Henke, Tino & Speranza, M. Grazia & Wäscher, Gerhard, 2015. "The multi-compartment vehicle routing problem with flexible compartment sizes," European Journal of Operational Research, Elsevier, vol. 246(3), pages 730-743.
    11. 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.
    12. Farasat, Alireza & Nikolaev, Alexander G., 2016. "Signed social structure optimization for shift assignment in the nurse scheduling problem," Socio-Economic Planning Sciences, Elsevier, vol. 56(C), pages 3-13.
    13. Qiu, Yuzhuo & Zhou, Dan & Du, Yanan & Liu, Jie & Pardalos, Panos M. & Qiao, Jun, 2021. "The two-echelon production routing problem with cross-docking satellites," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 147(C).
    14. Gary R. Waissi & Pragya Kaushal, 2020. "A polynomial matrix processing heuristic algorithm for finding high quality feasible solutions for the TSP," OPSEARCH, Springer;Operational Research Society of India, vol. 57(1), pages 73-87, March.
    15. Karapetyan, D. & Gutin, G., 2011. "Lin-Kernighan heuristic adaptations for the generalized traveling salesman problem," European Journal of Operational Research, Elsevier, vol. 208(3), pages 221-232, February.
    16. Mor, A. & Speranza, M.G. & Viegas, J.M., 2020. "Efficient loading and unloading operations via a booking system," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 141(C).
    17. Xujin Chen & Xiaodong Hu & Xiaohua Jia & Zhongzheng Tang & Chenhao Wang & Ying Zhang, 2021. "Algorithms for the metric ring star problem with fixed edge-cost ratio," Journal of Combinatorial Optimization, Springer, vol. 42(3), pages 499-523, October.
    18. Rui Xu & Yumiao Huang & Wei Xiao, 2023. "A Two-Level Variable Neighborhood Descent for a Split Delivery Clustered Vehicle Routing Problem with Soft Cluster Conflicts and Customer-Related Costs," Sustainability, MDPI, vol. 15(9), pages 1-22, May.
    19. Hipólito Hernández-Pérez & Juan-José Salazar-González, 2004. "Heuristics for the One-Commodity Pickup-and-Delivery Traveling Salesman Problem," Transportation Science, INFORMS, vol. 38(2), pages 245-255, May.
    20. K Sang-Ho & G Young-Gun & K Maing-Kyu, 2003. "Application of the out-of-kilter algorithm to the asymmetric traveling salesman problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 54(10), pages 1085-1092, October.

    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:250:y:2016:i:2:p:377-388. 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.