{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T04:00:32Z","timestamp":1760241632184,"version":"build-2065373602"},"reference-count":68,"publisher":"MDPI AG","issue":"7","license":[{"start":{"date-parts":[[2018,6,30]],"date-time":"2018-06-30T00:00:00Z","timestamp":1530316800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>With advances in information technology, people face the problem of dealing with tremendous amounts of information and need ways to save time and effort by summarizing the most important and relevant information. Thus, automatic text summarization has become necessary to reduce the information overload. This article proposes a novel extractive graph-based approach to solve the multi-document summarization (MDS) problem. To optimize the coverage of information in the output summary, the problem is formulated as an orienteering problem and heuristically solved by an ant colony system algorithm. The performance of the implemented system (MDS-OP) was evaluated on DUC 2004 (Task 2) and MultiLing 2015 (MMS task) benchmark corpora using several ROUGE metrics, as well as other methods. Its comparison with the performances of 26 systems shows that MDS-OP achieved the best F-measure scores on both tasks in terms of ROUGE-1 and ROUGE-L (DUC 2004), ROUGE-SU4, and three other evaluation methods (MultiLing 2015). Overall, MDS-OP ranked among the best 3 systems.<\/jats:p>","DOI":"10.3390\/a11070096","type":"journal-article","created":{"date-parts":[[2018,7,2]],"date-time":"2018-07-02T10:56:52Z","timestamp":1530529012000},"page":"96","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":12,"title":["Solving Multi-Document Summarization as an Orienteering Problem"],"prefix":"10.3390","volume":"11","author":[{"given":"Asma","family":"Al-Saleh","sequence":"first","affiliation":[{"name":"Department of Computer Science, College of Computer and Information Sciences, King Saud University, Riyadh 11543, Saudi Arabia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5981-6299","authenticated-orcid":false,"given":"Mohamed El Bachir","family":"Menai","sequence":"additional","affiliation":[{"name":"Department of Computer Science, College of Computer and Information Sciences, King Saud University, Riyadh 11543, Saudi Arabia"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2018,6,30]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"513","DOI":"10.1016\/j.ipm.2011.07.003","article-title":"Weighted consensus multi-document summarization","volume":"48","author":"Wang","year":"2012","journal-title":"Inf. Process. Manag."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1007\/s12293-011-0071-x","article-title":"Discrete particle swarm optimization for the team orienteering problem","volume":"3","author":"Muthuswamy","year":"2011","journal-title":"Memet. Comput."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.ejor.2010.03.045","article-title":"The orienteering problem: A survey","volume":"209","author":"Vansteenwegen","year":"2011","journal-title":"Eur. J. Oper. Res."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"315","DOI":"10.1016\/j.ejor.2016.04.059","article-title":"Orienteering Problem: A survey of recent variants, solution approaches and applications","volume":"255","author":"Gunawan","year":"2016","journal-title":"Eur. J. Oper. Res."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1109\/4235.585892","article-title":"Ant colony system: A cooperative learning approach to the traveling salesman problem","volume":"1","author":"Dorigo","year":"1997","journal-title":"IEEE Trans. Evolut. Comput."},{"key":"ref_6","unstructured":"Marie-Francine Moens, S.S. (2004, January 25\u201326). ROUGE: A Package for Automatic Evaluation of Summaries. Proceedings of the ACL-04 Workshop on Text Summarization Branches Out, Barcelona, Spain."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1145\/1410358.1410359","article-title":"Summarization System Evaluation Revisited: N-gram Graphs","volume":"5","author":"Giannakopoulos","year":"2008","journal-title":"ACM Trans. Speech Lang. Process."},{"key":"ref_8","unstructured":"Giannakopoulos, G., and Karkaletsis, V. (2011). AutoSummENG and MeMoG in evaluating guided summaries, MultiLing Summarisation Pilot Text Analysis Conference (TAC) 2011."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"436","DOI":"10.1007\/978-3-642-37256-8_36","article-title":"Summary Evaluation: Together We Stand NPowER-ed","volume":"Volume 7817","author":"Gelbukh","year":"2013","journal-title":"Computational Linguistics and Intelligent Text Processing"},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Mani, I. (2001). Automatic Summarization, John Benjamins Publishing.","DOI":"10.1075\/nlp.3"},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/s10462-011-9216-z","article-title":"Text Summarisation in Progress: A Literature Review","volume":"37","author":"Lloret","year":"2012","journal-title":"Artif. Intell. Rev."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"159","DOI":"10.1147\/rd.22.0159","article-title":"The Automatic Creation of Literature Abstracts","volume":"2","author":"Luhn","year":"1958","journal-title":"IBM J. Res. Dev."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"264","DOI":"10.1145\/321510.321519","article-title":"New Methods in Automatic Extracting","volume":"16","author":"Edmundson","year":"1969","journal-title":"J. ACM"},{"key":"ref_14","unstructured":"Litkowski, K.C. (2004, January 6\u20137). Summarization experiments in DUC 2004. Proceedings of the 2004 Document Understanding Conference, Boston, MA, USA."},{"key":"ref_15","unstructured":"Lacatusu, F., Hickl, A., Harabagiu, S., and Nezda, L. (2004, January 6\u20137). Lite-GISTexter at DUC 2004. Proceedings of the 2004 Document Understanding Conference, Boston, MA, USA."},{"key":"ref_16","unstructured":"Nobata, C., and Sekine, S. (2004, January 6\u20137). CRL\/NYU summarization system at DUC-2004. Proceedings of the 2004 Document Understanding Conference, Boston, MA, USA."},{"key":"ref_17","unstructured":"Conroy, J.M., Davis, S.T., and Kubina, J. (2018, March 25). Preprocessing and Term Weights in Multilingual Summarization. Available online: http:\/\/multiling.iit.demokritos.gr\/file\/download\/1582."},{"key":"ref_18","unstructured":"Conroy, J., Davis, S.T., Kubina, J., Liu, Y.K., O\u2019Leary, D.P., and Schlesinger, J.D. (2013, January 9). Multilingual Summarization: Dimensionality Reduction and a Step Towards Optimal Term Coverage. Proceedings of the MultiLing 2013 Workshop on Multilingual Multi-Document Summarization, Sofia, Bulgaria."},{"key":"ref_19","unstructured":"Balikas, G., and Amini, M.R. (2018, April 01). The Participation of UJF-Grenoble Team at Multiling 2015. Available online: http:\/\/multiling.iit.demokritos.gr\/file\/download\/1585."},{"key":"ref_20","unstructured":"Hirao, T., Suzuki, J., Hideki, I., and Maeda, E. (2004, January 6\u20137). NTT\u2019s Multiple Document Summarization System for DUC 2004. Proceedings of the 2004 Document Understanding Conference, Boston, MA, USA."},{"key":"ref_21","unstructured":"Wan, S., Li, L., Huang, T., Gao, Z., Mao, L., and Huang, F. (2018, March 25). CIST System Report for SIGdial MultiLing 2015. Available online: http:\/\/multiling.iit.demokritos.gr\/file\/download\/1575."},{"key":"ref_22","unstructured":"Conroy, J.M., Schlesinger, J.D., Goldstein, J., and O\u2019leary, D.P. (2004, January 6\u20137). Left-brain\/right-brain multi-document summarization. Proceedings of the 2004 Document Understanding Conference, Boston, MA, USA."},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Conroy, J., and O\u2019Leary, D.P. (2001). Text Summarization via Hidden Markov Models and Pivoted QR Matrix Decomposition, University of Maryland. Technical Report.","DOI":"10.1145\/383952.384042"},{"key":"ref_24","unstructured":"Litvak, M., Dlikman, A., and Last, M. (2018, April 01). MUSEEC: A Multilingual Text Summarization Tool. Available online: http:\/\/www.aclweb.org\/anthology\/P16-4013."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"629","DOI":"10.1007\/s10791-012-9210-3","article-title":"Cross-lingual training of summarization systems using annotated corpora in a foreign language","volume":"16","author":"Litvak","year":"2013","journal-title":"Inf. Retr."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"8146","DOI":"10.1016\/j.eswa.2015.05.034","article-title":"Query-oriented unsupervised multi-document summarization via deep learning model","volume":"42","author":"Zhong","year":"2015","journal-title":"Expert Syst. Appl."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1016\/j.eswa.2016.10.017","article-title":"Text summarization using unsupervised deep learning","volume":"68","author":"Hamey","year":"2017","journal-title":"Expert Syst. Appl."},{"key":"ref_28","unstructured":"Blair-Goldensohn, S., Evans, D., Hatzivassiloglou, V., McKeown, K., Nenkova, A., Passonneau, R., Schiffman, B., Schlaikjer, A., Siddharthan, A., and Siegelman, S. (2004, January 6\u20137). Columbia University at DUC 2004. Proceedings of the 2004 Document Understanding Conference, Boston, MA, USA."},{"key":"ref_29","unstructured":"Abdelkrime, A., Zegour, D.E., and Hidouci, K.W. (2015, January 6\u201310). AllSummarizer system at MultiLing 2015: Multilingual single and multi-document summarization. Proceedings of the SIGDIAL 2015 Conference, Dresden, Germany."},{"key":"ref_30","unstructured":"Saggion, H., and Gaizauskas, R. (2004, January 6\u20137). Multi-document summarization by cluster\/profile relevance and redundancy removal. Proceedings of the 2004 Document Understanding Conference, Boston, MA, USA."},{"key":"ref_31","unstructured":"Angheluta, R., Mitra, R., Jing, X., and Moens, M.F. (2004, January 6\u20137). KU Leuven summarization system at DUC 2004. Proceedings of the 2004 Document Understanding Conference, Boston, MA, USA."},{"key":"ref_32","doi-asserted-by":"crossref","unstructured":"Mihalcea, R., and Radev, D. (2011). Graph-Based Natural Language Processing and Information Retrieval, Cambridge University Press.","DOI":"10.1017\/CBO9780511976247"},{"key":"ref_33","doi-asserted-by":"crossref","unstructured":"Erkan, G., and Radev, D.R. (2004, January 6\u20137). The University of Michigan at DUC 2004. Proceedings of the 2004 Document Understanding Conference, Boston, MA, USA.","DOI":"10.6028\/NIST.SP.500-261.novelty-u.michigan"},{"key":"ref_34","unstructured":"Mani, I., and Bloedorn, E. (1997, January 27\u201331). Multi-document Summarization by Graph Search and Matching. Proceedings of the Fourteenth National Conference on Artificial Intelligence and Ninth Conference on Innovative Applications of Artificial Intelligence, Providence, Rhode Island."},{"key":"ref_35","doi-asserted-by":"crossref","unstructured":"Zha, H. (2002, January 11\u201315). Generic Summarization and Keyphrase Extraction Using Mutual Reinforcement Principle and Sentence Clustering. Proceedings of the 25th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval SIGIR \u201902, Tampere, Finland.","DOI":"10.1145\/564396.564398"},{"key":"ref_36","first-page":"457","article-title":"LexRank: Graph-based Lexical Centrality As Salience in Text Summarization","volume":"22","author":"Erkan","year":"2004","journal-title":"J. Artif. Int. Res."},{"key":"ref_37","unstructured":"Vanderwende, L., Banko, M., and Menezes, A. (2004). Event-Centric Summary Generation, NIST. Working Notes of the Document Understanding Conference 2004."},{"key":"ref_38","unstructured":"Wan, X., Yang, J., and Xiao, J. (2007, January 25\u201327). Towards an Iterative Reinforcement Approach for Simultaneous Document Summarization and Keyword Extraction. Proceedings of the 45th Annual Meeting of the Association of Computational Linguistics, Prague, Czech."},{"key":"ref_39","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1016\/S0169-7552(98)00110-X","article-title":"The Anatomy of a Large-scale Hypertextual Web Search Engine","volume":"30","author":"Brin","year":"1998","journal-title":"Comput. Netw. ISDN Syst."},{"key":"ref_40","doi-asserted-by":"crossref","first-page":"604","DOI":"10.1145\/324133.324140","article-title":"Authoritative Sources in a Hyperlinked Environment","volume":"46","author":"Kleinberg","year":"1999","journal-title":"J. ACM"},{"key":"ref_41","doi-asserted-by":"crossref","unstructured":"Thomas, S., Beutenm\u00fcller, C., de la Puente, X., Remus, R., and Bordag, S. (2015, January 6\u201310). ExB Text Summarizer. Proceedings of the SIGDIAL 2015 Conference, Dresden, Germany.","DOI":"10.18653\/v1\/W15-4637"},{"key":"ref_42","unstructured":"Wan, X., Yang, J., and Xiao, J. (2007, January 6\u201312). Manifold-ranking Based Topic-focused Multi-document Summarization. Proceedings of the 20th International Joint Conference on Artifical Intelligence IJCAI\u201907, Hyderabad, India."},{"key":"ref_43","unstructured":"Chali, Y., and Kolla, M. (2004, January 6\u20137). Summarization techniques at DUC 2004. Proceedings of the 2004 Document Understanding Conference, Boston, MA, USA."},{"key":"ref_44","unstructured":"Bergler, S., Witte, R., Li, Z., Khalife, M., Chen, Y., Doandes, M., and Andreevskaia, A. (2004, January 6\u20137). Multi-ERSS and ERSS 2004. Proceedings of the 2004 Document Understanding Conference, Boston, MA, USA."},{"key":"ref_45","doi-asserted-by":"crossref","unstructured":"Huang, L., He, Y., Wei, F., and Li, W. (2010, January 2\u20134). Modeling Document Summarization as Multi-objective Optimization. Proceedings of the 2010 Third International Symposium on Intelligent Information Technology and Security Informatics (IITSI), Jinggangshan, China.","DOI":"10.1109\/IITSI.2010.80"},{"key":"ref_46","doi-asserted-by":"crossref","unstructured":"Rautray, R., and Balabantaray, R.C. (2017). Bio-Inspired Algorithms for Text Summarization: A Review. Bio-Inspired Computing for Information Retrieval Applications, IGI Global.","DOI":"10.4018\/978-1-5225-2375-8.ch003"},{"key":"ref_47","unstructured":"Shen, C., and Li, T. (2010, January 23\u201327). Multi-document Summarization via the Minimum Dominating Set. Proceedings of the 23rd International Conference on Computational Linguistics COLING \u201910, Beijing, China."},{"key":"ref_48","unstructured":"Jaoua, K.F., Jaoua, M., and Ben Hamadou, A. (2004, January 6\u20137). Summarization at LARIS laboratory. Proceedings of the 2004 Document Understanding Conference, Boston, MA, USA."},{"key":"ref_49","doi-asserted-by":"crossref","first-page":"385","DOI":"10.1016\/j.eswa.2017.05.075","article-title":"Extractive multi-document summarization using population-based multicriteria optimization","volume":"86","author":"John","year":"2017","journal-title":"Expert Syst. Appl."},{"key":"ref_50","doi-asserted-by":"crossref","unstructured":"Vanetik, N., and Litvak, M. (2015, January 6\u201310). Multilingual Summarization with Polytope Model. Proceedings of the SIGDIAL 2015 Conference, Dresden, Germany.","DOI":"10.18653\/v1\/W15-4632"},{"key":"ref_51","first-page":"510","article-title":"A Class of Submodular Functions for Document Summarization","volume":"Volume 1","author":"Lin","year":"2011","journal-title":"Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies HLT \u201911"},{"key":"ref_52","doi-asserted-by":"crossref","unstructured":"Takamura, H., and Okumura, M. (2009, January 2). Text Summarization Model Based on Maximum Coverage Problem and Its Variant. Proceedings of the 12th Conference of the European Chapter of the Association for Computational Linguistics EACL \u201909, Athens, Greece.","DOI":"10.3115\/1609067.1609154"},{"key":"ref_53","doi-asserted-by":"crossref","first-page":"94","DOI":"10.1016\/j.cie.2012.09.005","article-title":"Formulation of document summarization as a 0\u20131 nonlinear programming problem","volume":"64","author":"Alguliev","year":"2013","journal-title":"Comput. Ind. Eng."},{"key":"ref_54","doi-asserted-by":"crossref","first-page":"571","DOI":"10.1016\/j.ipm.2010.03.004","article-title":"Fuzzy Swarm Diversity Hybrid Model for Text Summarization","volume":"46","author":"Binwahlan","year":"2010","journal-title":"Inf. Process. Manag."},{"key":"ref_55","unstructured":"Peyrard, M., and Eckle-Kohler, J. (2016, January 11\u201316). A General Optimization Framework for Multi-Document Summarization Using Genetic Algorithms and Swarm Intelligence. Proceedings of the 26th International Conference on Computational Linguistics COLING 2016, Osaka, Japan."},{"key":"ref_56","doi-asserted-by":"crossref","unstructured":"Sanchez-Gomez, J.M., Vega-Rodr\u00edguez, M.A., and P\u00e9rez, C.J. (2017). Extractive multi-document text summarization using a multi-objective artificial bee colony optimization approach. Knowl. Based Syst.","DOI":"10.1016\/j.knosys.2017.11.029"},{"key":"ref_57","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1016\/j.knosys.2016.11.009","article-title":"Ant colony heuristic for user-contributed comments summarization","volume":"118","author":"Mosa","year":"2017","journal-title":"Knowl. Based Syst."},{"key":"ref_58","doi-asserted-by":"crossref","unstructured":"Asgari, H., Masoumi, B., and Sheijani, O. (2014, January 4\u20136). Automatic text summarization based on multi-agent particle swarm optimization. Proceedings of the 2014 Iranian Conference on Intelligent Systems (ICIS), Bam, Iran.","DOI":"10.1109\/IranianCIS.2014.6802592"},{"key":"ref_59","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1016\/j.eswa.2017.01.010","article-title":"Graph coloring and ACO based summarization for social networks","volume":"74","author":"Mosa","year":"2017","journal-title":"Expert Syst. Appl."},{"key":"ref_60","doi-asserted-by":"crossref","unstructured":"Rautray, R., and Balabantaray, R.C. (2017). An evolutionary framework for multi document summarization using Cuckoo search approach: MDSCS. Appl. Comput. Inf.","DOI":"10.1016\/j.physa.2017.02.056"},{"key":"ref_61","unstructured":"Kim, K.J., and Joukov, N. (2017, January 26\u201329). Autonomous Text Summarization Using Collective Intelligence Based on Nature-Inspired Algorithm. Proceedings of the International Conference on Mobile and Wireless Technology, Kuala Lumpur, Malaysia."},{"key":"ref_62","doi-asserted-by":"crossref","first-page":"307","DOI":"10.1002\/1520-6750(198706)34:3<307::AID-NAV3220340302>3.0.CO;2-D","article-title":"The orienteering problem","volume":"34","author":"Golden","year":"1987","journal-title":"Nav. Res. Logist."},{"key":"ref_63","doi-asserted-by":"crossref","first-page":"475","DOI":"10.1016\/0377-2217(95)00035-6","article-title":"A fast and effective heuristic for the orienteering problem","volume":"88","author":"Chao","year":"1996","journal-title":"Eur. J. Oper. Res."},{"key":"ref_64","doi-asserted-by":"crossref","first-page":"188","DOI":"10.1287\/trsc.1030.0079","article-title":"Traveling Salesman Problems with Profits","volume":"39","author":"Feillet","year":"2005","journal-title":"Transp. Sci."},{"key":"ref_65","doi-asserted-by":"crossref","unstructured":"Manning, C.D., Surdeanu, M., Bauer, J., Finkel, J., Bethard, S.J., and McClosky, D. (2014). The Stanford CoreNLP Natural Language Processing Toolkit, Association for Computational Linguistics (ACL) System Demonstrations.","DOI":"10.3115\/v1\/P14-5010"},{"key":"ref_66","unstructured":"Jurafsky, D., and Martin, J.H. (2009). Speech and Language Processing: An Introduction to Natural Language Processing, Computational Linguistics, and Speech Recognition, Prentice-Hall, Inc.. [2nd ed.]."},{"key":"ref_67","doi-asserted-by":"crossref","unstructured":"Giannakopoulos, G., Kubina, J., Conroy, J.M., Steinberger, J., Favre, B., Kabadjov, M., Kruschwitz, U., and Poesio, M. (2015, January 6\u201310). MultiLing 2015: Multilingual Summarization of Single and Multi-Documents, On-line Fora, and Call-center Conversations. Proceedings of the SIGDIAL 2015 Conference, Dresden, Germany.","DOI":"10.18653\/v1\/W15-4638"},{"key":"ref_68","doi-asserted-by":"crossref","first-page":"1506","DOI":"10.1016\/j.ipm.2007.01.019","article-title":"DUC in context","volume":"43","author":"Over","year":"2007","journal-title":"Inf. Process. Manag."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/11\/7\/96\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T15:10:50Z","timestamp":1760195450000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/11\/7\/96"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,6,30]]},"references-count":68,"journal-issue":{"issue":"7","published-online":{"date-parts":[[2018,7]]}},"alternative-id":["a11070096"],"URL":"https:\/\/doi.org\/10.3390\/a11070096","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2018,6,30]]}}}