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

Heuristics for the generalized median graph problem

Author

Listed:
  • Musmanno, Leonardo M.
  • Ribeiro, Celso C.

Abstract

Structural approaches for pattern recognition frequently make use of graphs to represent objects. The concept of object similarity is of great importance in pattern recognition. The graph edit distance is often used to measure the similarity between two graphs. It basically consists in the amount of distortion needed to transform one graph into the other. The median graph of a set S of graphs is a graph of S that minimizes the sum of its distances to all other graphs in S. The generalized median graph of S is a graph that minimizes the sum of the distances to all graphs in S. It is the graph that best captures the information contained in S and may be regarded as the best representative of the set. Exact methods for solving the generalized median graph problem are capable to handle only a few small graphs. We propose two new heuristics for solving the generalized median graph problem: a greedy adaptive algorithm and a GRASP heuristic. Numerical results indicate that both heuristics can be used to obtain good approximate solutions for the generalized median graph problem, significantly improving the initial solutions and the median graphs. Therefore, the generalized median graph can be effectively computed and used as a better representation than the median graph in a number of relevant pattern recognition applications. This conclusion is supported by experiments with a classification problem and comparisons with algorithm k-NN.

Suggested Citation

  • Musmanno, Leonardo M. & Ribeiro, Celso C., 2016. "Heuristics for the generalized median graph problem," European Journal of Operational Research, Elsevier, vol. 254(2), pages 371-384.
    • Handle: RePEc:eee:ejores:v:254:y:2016:i:2:p:371-384
    DOI: 10.1016/j.ejor.2016.03.048
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221716301941
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2016.03.048?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. Mauricio G. C. Resende & Celso C. Ribeiro, 2014. "GRASP: Greedy Randomized Adaptive Search Procedures," Springer Books, in: Edmund K. Burke & Graham Kendall (ed.), Search Methodologies, edition 2, chapter 0, pages 287-312, Springer.
    2. Allahyari, Somayeh & Salari, Majid & Vigo, Daniele, 2015. "A hybrid metaheuristic algorithm for the multi-depot covering tour vehicle routing problem," European Journal of Operational Research, Elsevier, vol. 242(3), pages 756-768.
    3. Lopamudra Mukherjee & Vikas Singh & Jiming Peng & Jinhui Xu & Michael J. Zeitz & Ronald Berezney, 2009. "Generalized median graphs and applications," Journal of Combinatorial Optimization, Springer, vol. 17(1), pages 21-44, January.
    4. Mauricio G.C. Resende & Celso C. Ribeiro, 2010. "Greedy Randomized Adaptive Search Procedures: Advances, Hybridizations, and Applications," International Series in Operations Research & Management Science, in: Michel Gendreau & Jean-Yves Potvin (ed.), Handbook of Metaheuristics, chapter 0, pages 283-319, Springer.
    5. Nguyen, Viet-Phuong & Prins, Christian & Prodhon, Caroline, 2012. "Solving the two-echelon location routing problem by a GRASP reinforced by a learning process and path relinking," European Journal of Operational Research, Elsevier, vol. 216(1), pages 113-126.
    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. Simona Mancini, 2013. "Multi-echelon distribution systems in city logistics," European Transport \ Trasporti Europei, ISTIEE, Institute for the Study of Transport within the European Economic Integration, issue 54, pages 1-2.
    2. Fernando Stefanello & Vaneet Aggarwal & Luciana S. Buriol & Mauricio G. C. Resende, 2019. "Hybrid algorithms for placement of virtual machines across geo-separated data centers," Journal of Combinatorial Optimization, Springer, vol. 38(3), pages 748-793, October.
    3. Zhou, Lin & Baldacci, Roberto & Vigo, Daniele & Wang, Xu, 2018. "A Multi-Depot Two-Echelon Vehicle Routing Problem with Delivery Options Arising in the Last Mile Distribution," European Journal of Operational Research, Elsevier, vol. 265(2), pages 765-778.
    4. Sahar Validi & Arijit Bhattacharya & P. J. Byrne, 2020. "Sustainable distribution system design: a two-phase DoE-guided meta-heuristic solution approach for a three-echelon bi-objective AHP-integrated location-routing model," Annals of Operations Research, Springer, vol. 290(1), pages 191-222, July.
    5. Yue Lu & Maoxiang Lang & Xueqiao Yu & Shiqi Li, 2019. "A Sustainable Multimodal Transport System: The Two-Echelon Location-Routing Problem with Consolidation in the Euro–China Expressway," Sustainability, MDPI, vol. 11(19), pages 1-25, October.
    6. Jone R. Hansen & Kjetil Fagerholt & Magnus Stålhane & Jørgen G. Rakke, 2020. "An adaptive large neighborhood search heuristic for the planar storage location assignment problem: application to stowage planning for Roll-on Roll-off ships," Journal of Heuristics, Springer, vol. 26(6), pages 885-912, December.
    7. Kafle, Nabin & Zou, Bo & Lin, Jane, 2017. "Design and modeling of a crowdsource-enabled system for urban parcel relay and delivery," Transportation Research Part B: Methodological, Elsevier, vol. 99(C), pages 62-82.
    8. Hendri Sutrisno & Chao-Lung Yang, 2023. "A two-echelon location routing problem with mobile satellites for last-mile delivery: mathematical formulation and clustering-based heuristic method," Annals of Operations Research, Springer, vol. 323(1), pages 203-228, April.
    9. Dumez, Dorian & Lehuédé, Fabien & Péton, Olivier, 2021. "A large neighborhood search approach to the vehicle routing problem with delivery options," Transportation Research Part B: Methodological, Elsevier, vol. 144(C), pages 103-132.
    10. Drexl, Michael & Schneider, Michael, 2015. "A survey of variants and extensions of the location-routing problem," European Journal of Operational Research, Elsevier, vol. 241(2), pages 283-308.
    11. Alexis Robbes & Yannick Kergosien & Virginie André & Jean-Charles Billaut, 2022. "Efficient heuristics to minimize the total tardiness of chemotherapy drug production and delivery," Flexible Services and Manufacturing Journal, Springer, vol. 34(3), pages 785-820, September.
    12. Angel Juan & Javier Faulin & Albert Ferrer & Helena Lourenço & Barry Barrios, 2013. "MIRHA: multi-start biased randomization of heuristics with adaptive local search for solving non-smooth routing problems," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 21(1), pages 109-132, April.
    13. Ali Heidari & Din Mohammad Imani & Mohammad Khalilzadeh & Mahdieh Sarbazvatan, 2023. "Green two-echelon closed and open location-routing problem: application of NSGA-II and MOGWO metaheuristic approaches," Environment, Development and Sustainability: A Multidisciplinary Approach to the Theory and Practice of Sustainable Development, Springer, vol. 25(9), pages 9163-9199, September.
    14. Julian Hof & Michael Schneider, 2021. "Intraroute Resource Replenishment with Mobile Depots," Transportation Science, INFORMS, vol. 55(3), pages 660-686, May.
    15. 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.
    16. Li, Hongqi & Liu, Yinying & Jian, Xiaorong & Lu, Yingrong, 2018. "The two-echelon distribution system considering the real-time transshipment capacity varying," Transportation Research Part B: Methodological, Elsevier, vol. 110(C), pages 239-260.
    17. Anders Reenberg Andersen & Thomas Jacob Riis Stidsen & Line Blander Reinhardt, 2020. "Simulation-Based Rolling Horizon Scheduling for Operating Theatres," SN Operations Research Forum, Springer, vol. 1(2), pages 1-26, June.
    18. Sluijk, Natasja & Florio, Alexandre M. & Kinable, Joris & Dellaert, Nico & Van Woensel, Tom, 2023. "Two-echelon vehicle routing problems: A literature review," European Journal of Operational Research, Elsevier, vol. 304(3), pages 865-886.
    19. Govindan, K. & Jafarian, A. & Khodaverdi, R. & Devika, K., 2014. "Two-echelon multiple-vehicle location–routing problem with time windows for optimization of sustainable supply chain network of perishable food," International Journal of Production Economics, Elsevier, vol. 152(C), pages 9-28.
    20. Victor Reyes & Ignacio Araya, 2021. "A GRASP-based scheme for the set covering problem," Operational Research, Springer, vol. 21(4), pages 2391-2408, December.

    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:254:y:2016:i:2:p:371-384. 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.