Sistema para Resolver o Problema de Roteamento de Estoque Baseado em Técnicas de Monte Carlo
Resumo
O Problema de Roteamento de Estoque com Demanda Estocástica (SIRP–Stochastic Inventory Routing Problem) é uma combinação dos problemas de controle de inventários com demandas estocásticas por mercadorias em centros comerciais e do roteamento de veículos utilizados no abastecimento desses centros a partir de um único centro de distribuição. Este trabalho apresenta uma variante do algoritmo proposto por [8] para o SIRP utilizando técnicas de Monte Carlo. O novo algoritmo foiimplementado e comparado ao algoritmo original considerando diversas políticas, tendo demonstrado resultados semelhantes em alguns casos e melhores em outros em termos de eficiência de tempo e custo total da solução. A análise, comparação e avaliação dos algoritmos foram feitas com base em benchmarks de problemas existentes na literatura.
Palavras-chave:
Roteamento de veículos, IRP (Inventory Routing Problem – Problema de Roteamento de Estoque), SIRP (Stochastic Inventory Routing Problem), Algoritmos heurísticos, Técnicas de Monte Carlo
Referências
Amaral, D.O.F., Fonseca, E.B., Lopes, L., Vieira, L. (2014) Comparative Analysis of Portuguese Named Entities Recognition Tools. In Int. CRE (vol. 1, pp. 2554-2558).
Anantharam, P., Barnaghi, P., Thirunarayan, K., & Sheth, A. (2015). Extracting city traffic events from social streams. ACM TIST (vol. 6, n. 4, pp. 43).
Auer, S., Bizer, C., Kobilarov, G., Lehmann, J., Cyganiak, R., and Ives, Z. (2007). Dbpedia: A nucleus for a web of open data (pp. 722-735). Springer Berlin Heidelberg.
Baldridge, J. (2005). The opennlp project. URL: http://opennlp.apache.org. (acessado em janeiro de 2016).
Berry, M. J., and Linoff, G. (1997). Data mining techniques: for marketing, sales, and customer support. John Wiley & Sons, Inc.
Bollacker, K., Cook, R., and Tufts, P. (2007). Freebase: A shared database of structured general human knowledge. In AAAI (vol. 7, pp. 1962-1963).
Bontcheva, K., Derczynski, L., Funk, A., Greenwood, M. A., Maynard, D., and Aswani, N. (2013). TwitIE: An Open- Source IE Pipeline for Microblog Text. In RANLP (pp. 83-90).
Bontcheva, K., Maynard, D., Tablan, V., and Cunningham, H. (2003). Gate: A unicode-based infrastructure supporting multilingual information extraction. Proc. IE for Slavonic and other Central and Eastern EU Languages, Borovets, Bulgaria.
Bowman, M., Debray, S. K., and Peterson, L. L. (1993). Reasoning about naming systems. ACM TOPLAS (vol. 15, n. 5, pp. 795-825).
Branco, A., and Silva, J. R. (2006). A suite of shallow processing tools for portuguese: Lx-suite. In Proc. Eleventh Conf. of the EU Chapter of the ACL (pp. 179-182).
Brants, T. (2000). A statistical Part-of-Speech tagger. In Proceedings of the Sixth ANLP (pp. 224-231).
Das, T. K., Acharjya, D. P., and Patra, M. R. (2014). Opinion mining about a product by analyzing public tweets in Twitter. In ICCCI (pp. 1-4). IEEE
Derczynski, L., Maynard, D., Rizzo, G., van Erp, M., Gorrell, G., Troncy, R., Petrak, J., Bontcheva, K. (2015). Analysis of named entity recognition and linking for tweets. Inf. Process. Manage (vol. 51, n. 2, pp. 32-49).
Derczynski, L., Ritter, A., Clark, S., and Bontcheva, K. (2013). Twitter Part-of-Speech Tagging for All: Overcoming Sparse and Noisy Data. In RANLP (pp. 198-206).
Dietterich, T. G. (2002). Ensemble Learning. The Handbook of Brain Theory and Neural Networks, MA Arbib.
Diniz, H. B., Silva, E. C., and Gama, K. S. (2015). Uma Arquitetura de Referência para Plataforma de Crowdsensing em Smart Cities. In Proc. of the BSIS (pp. 87-97).
Doddington, G. R., Mitchell, A., Przybocki, M. A., Ramshaw, L. A., Strassel, S., and Weischedel, R. M. (2004). The Automatic Content Extraction Program-Tasks, Data, and Evaluation. In LREC (vol. 2, pp. 1).
Downey, D., Broadhead, M., and Etzioni, O. (2007). Locating Complex Named Entities in Web Text. In IJCAI (vol. 7, pp. 2733-2739).
Feldman, R., and Sanger, J. (2007). The text mining handbook: advanced approaches in analyzing unstructured data. Cambridge University Press.
Fileto, R., May, C., Renso, C., Pelekis, N., Theodoridis, Y. (2015) The Baquara2 knowledge-based framework for semantic enrichment and analysis of movement data. Data & Knowledge Eng (vol. 98, pp 104-122.
Finkel, J. R., Grenager, T., and Manning, C. (2005). Incorporating non-local information into IE systems by gibbs sampling. In Proc. Annual Meeting on ACL (pp. 363-370).
Forman, G. (2003). An extensive empirical study of feature selection metrics for text classification. JMLR, 3, 1289-1305.
Goldberg, D. E., and Holland, J. H. (1988). Genetic algorithms and machine learning. Machine learning (vol. 3, n. 2, pp. 95-99).
Habib, M. B., and Keulen, V. M. (2014). Information extraction for social media. ACL.
Hall, M., Frank, E., Holmes, G., Pfahringer, B., Reutemann, P., & Witten, I. H. (2009). The WEKA data mining software: an update. ACM SIGKDD expl. newsl., (vol. 11, n. 1, pp. 10-18).
Han, J., Kamber, M., Pei, J. (2006) Data mining: concepts and techniques. Morgan kaufmann.
Jabeen, S., Shah, S., and Latif, A. (2013). Named entity recognition and normalization in tweets towards text summarization. In ICDIM (pp. 223-227). IEEE.
Jurafsky, D. and Martin, J. H. (2008). Speech and Language processing: An introduction to natural language processing. 2nd Ed., Pearson Prentice Hall.
Klein, D. (2015). Estudo de técnicas e ferramentas aplicáveis a mídias sociais para reconhecimento e desambiguação de entidades nomeadas (TCC). Univ. Federal de Santa Catarina.
Lev, B., and Thiagarajan, S. R. (1993). Fundamental information analysis. JA research, 190-215.
Liu, X., Zhang, S., Wei, F., and Zhou, M. (2011). Recognizing named entities in tweets. In Proc. of the 49th Annual Meeting of the ACL: HLT. (vol. 1, pp. 359-367).
Manning, C. D., Raghavan, P., and Schütze, H. (2008). Introduction to information retrieval (vol. 1, n. 1, p. 496). Cambridge: Cambridge University Press.
Padró, L., (1998). A Hybrid Environment for Syntax- Semantic Tagging. PhD thesis. Dept. LSI. Universitat Politècnica de Catalunya.
Padró, L., and Stanilovsky, E. (2012). Freeling 3.0: Towards wider multilinguality. In LREC2012.
Pazzani, M. J., and Billsus, D. (2007). Content-based recommendation systems. In The adaptive web (pp. 325-341). Springer Berlin Heidelberg.
Quilan, J.R., 1983. Learning efficient classification procedures and their application to chess end games. Machine Learning: An AI Approach, 1.
Ramage, D., Hall, D., Nallapati, R., and Manning, C. D. (2009). Labeled LDA: A supervised topic model for credit attribution in multi-labeled corpora. In Proc. CEMNLP (vol. 1, pp. 248-256). ACL.
Ratinov, L., and Roth, D. (2009). Design challenges and misconceptions in named entity recognition. In Proceedings CCNLL (pp. 147-155). ACL.
Ritter, A., Clark, S., and Etzioni, O. (2011). Named entity recognition in tweets: an experimental study. In Proc. of the Conf. on Empirical Methods in NLP (pp. 1524-1534). ACL.
Rizzo, G., Troncy, R. (2011). NERD: Evaluating Named Entity Recognition Tools in the Web of Data. In Workshop on WEKEX’11, Bonn, Germany, 1-16.
Rizzo, G., Troncy, R., Hellmann, S., and Bruemmer, M. (2012). NERD meets NIF: Lifting NLP Extraction Results to the Linked Data Cloud. LDOW, 937.
Ruck, D. W., Rogers, S. K., Kabrisky, M., Oxley, M. E., and Suter, B. W. (1990). The multilayer perceptron as an approximation to a Bayes optimal discriminant function. Neural Networks, IEEE Trans. on (vol. 1, n. 4, pp. 296-298).
Sacenti, J.A.P., Salvini, F., Fileto, R., Raffaetà, A., Roncato, A. (2015) Automatically Tailoring Semantics-Enabled Dimensions for Movement DW. In: DaWaK 2015: 205-216
Sha, F., and Pereira, F. (2003). Shallow parsing with conditional random fields. In Proc. NC of the ACL: HLT (vol. 1, pp. 134-141). ACL
Speck, R., and Ngomo, A. C. N. (2014). Named entity recognition using FOX. In Proc. of the 2014 Int. Conf. (vol. 1272, pp. 85-88). CEUR-WS. org.
Tjong Kim Sang, E. F., and De Meulder, F. (2003). Introduction to the CoNLL-2003 shared task: Languageindependent named entity recognition. In Proc. CNLL at HLT-NAACL (vol. 4, pp. 142-147). ACL.
Toutanova, K., Klein, D., Manning, C. D., and Singer, Y. (2003). Feature-rich part-of-speech tagging with a cyclic dependency network. In Proc. CNAC ACL: HLT (vol. 1, pp. 173-180)
Usbeck, R., Ngomo, A. C. N., Röder, M., Gerber, D., Coelho, S. A., Auer, S., and Both, A. (2014). AGDISTISgraph- based disambiguation of named entities using linked data. In The Semantic Web – ISWC 2014 (pp. 457-471). Springer International Publishing.
Voorhees, E. M. (1999). The TREC-8 Question Answering Track Report. In Trec (vol. 99, pp. 77-82).
Voutilainen, A. (2003). Part-of-speech tagging. The Oxford handbook of computational linguistics (pp. 219-232).
Wang, W., and Stewart, K. (2015). Spatiotemporal and semantic information extraction from Web news reports about natural hazards. Comp., Env. Urb. Syst., 50, 30-40.
Willingham, D. T. (2007). Cognition: The thinking animal. Englewood Cliffs, NJ: Pearson/Prentice Hall.
Witten, I.H., and Frank, E. (2011). Data Mining: Practical machine learning tools and techniques. Morgan Kaufmann, 664pp.
Xia, C., Hu, J., Zhu, Y., Naaman, M. (2015). What Is New in Our City? A Framework for Event Extraction Using Social Media Posts. In: Advances in KDD Mining, Springer, 16-32.
Anantharam, P., Barnaghi, P., Thirunarayan, K., & Sheth, A. (2015). Extracting city traffic events from social streams. ACM TIST (vol. 6, n. 4, pp. 43).
Auer, S., Bizer, C., Kobilarov, G., Lehmann, J., Cyganiak, R., and Ives, Z. (2007). Dbpedia: A nucleus for a web of open data (pp. 722-735). Springer Berlin Heidelberg.
Baldridge, J. (2005). The opennlp project. URL: http://opennlp.apache.org. (acessado em janeiro de 2016).
Berry, M. J., and Linoff, G. (1997). Data mining techniques: for marketing, sales, and customer support. John Wiley & Sons, Inc.
Bollacker, K., Cook, R., and Tufts, P. (2007). Freebase: A shared database of structured general human knowledge. In AAAI (vol. 7, pp. 1962-1963).
Bontcheva, K., Derczynski, L., Funk, A., Greenwood, M. A., Maynard, D., and Aswani, N. (2013). TwitIE: An Open- Source IE Pipeline for Microblog Text. In RANLP (pp. 83-90).
Bontcheva, K., Maynard, D., Tablan, V., and Cunningham, H. (2003). Gate: A unicode-based infrastructure supporting multilingual information extraction. Proc. IE for Slavonic and other Central and Eastern EU Languages, Borovets, Bulgaria.
Bowman, M., Debray, S. K., and Peterson, L. L. (1993). Reasoning about naming systems. ACM TOPLAS (vol. 15, n. 5, pp. 795-825).
Branco, A., and Silva, J. R. (2006). A suite of shallow processing tools for portuguese: Lx-suite. In Proc. Eleventh Conf. of the EU Chapter of the ACL (pp. 179-182).
Brants, T. (2000). A statistical Part-of-Speech tagger. In Proceedings of the Sixth ANLP (pp. 224-231).
Das, T. K., Acharjya, D. P., and Patra, M. R. (2014). Opinion mining about a product by analyzing public tweets in Twitter. In ICCCI (pp. 1-4). IEEE
Derczynski, L., Maynard, D., Rizzo, G., van Erp, M., Gorrell, G., Troncy, R., Petrak, J., Bontcheva, K. (2015). Analysis of named entity recognition and linking for tweets. Inf. Process. Manage (vol. 51, n. 2, pp. 32-49).
Derczynski, L., Ritter, A., Clark, S., and Bontcheva, K. (2013). Twitter Part-of-Speech Tagging for All: Overcoming Sparse and Noisy Data. In RANLP (pp. 198-206).
Dietterich, T. G. (2002). Ensemble Learning. The Handbook of Brain Theory and Neural Networks, MA Arbib.
Diniz, H. B., Silva, E. C., and Gama, K. S. (2015). Uma Arquitetura de Referência para Plataforma de Crowdsensing em Smart Cities. In Proc. of the BSIS (pp. 87-97).
Doddington, G. R., Mitchell, A., Przybocki, M. A., Ramshaw, L. A., Strassel, S., and Weischedel, R. M. (2004). The Automatic Content Extraction Program-Tasks, Data, and Evaluation. In LREC (vol. 2, pp. 1).
Downey, D., Broadhead, M., and Etzioni, O. (2007). Locating Complex Named Entities in Web Text. In IJCAI (vol. 7, pp. 2733-2739).
Feldman, R., and Sanger, J. (2007). The text mining handbook: advanced approaches in analyzing unstructured data. Cambridge University Press.
Fileto, R., May, C., Renso, C., Pelekis, N., Theodoridis, Y. (2015) The Baquara2 knowledge-based framework for semantic enrichment and analysis of movement data. Data & Knowledge Eng (vol. 98, pp 104-122.
Finkel, J. R., Grenager, T., and Manning, C. (2005). Incorporating non-local information into IE systems by gibbs sampling. In Proc. Annual Meeting on ACL (pp. 363-370).
Forman, G. (2003). An extensive empirical study of feature selection metrics for text classification. JMLR, 3, 1289-1305.
Goldberg, D. E., and Holland, J. H. (1988). Genetic algorithms and machine learning. Machine learning (vol. 3, n. 2, pp. 95-99).
Habib, M. B., and Keulen, V. M. (2014). Information extraction for social media. ACL.
Hall, M., Frank, E., Holmes, G., Pfahringer, B., Reutemann, P., & Witten, I. H. (2009). The WEKA data mining software: an update. ACM SIGKDD expl. newsl., (vol. 11, n. 1, pp. 10-18).
Han, J., Kamber, M., Pei, J. (2006) Data mining: concepts and techniques. Morgan kaufmann.
Jabeen, S., Shah, S., and Latif, A. (2013). Named entity recognition and normalization in tweets towards text summarization. In ICDIM (pp. 223-227). IEEE.
Jurafsky, D. and Martin, J. H. (2008). Speech and Language processing: An introduction to natural language processing. 2nd Ed., Pearson Prentice Hall.
Klein, D. (2015). Estudo de técnicas e ferramentas aplicáveis a mídias sociais para reconhecimento e desambiguação de entidades nomeadas (TCC). Univ. Federal de Santa Catarina.
Lev, B., and Thiagarajan, S. R. (1993). Fundamental information analysis. JA research, 190-215.
Liu, X., Zhang, S., Wei, F., and Zhou, M. (2011). Recognizing named entities in tweets. In Proc. of the 49th Annual Meeting of the ACL: HLT. (vol. 1, pp. 359-367).
Manning, C. D., Raghavan, P., and Schütze, H. (2008). Introduction to information retrieval (vol. 1, n. 1, p. 496). Cambridge: Cambridge University Press.
Padró, L., (1998). A Hybrid Environment for Syntax- Semantic Tagging. PhD thesis. Dept. LSI. Universitat Politècnica de Catalunya.
Padró, L., and Stanilovsky, E. (2012). Freeling 3.0: Towards wider multilinguality. In LREC2012.
Pazzani, M. J., and Billsus, D. (2007). Content-based recommendation systems. In The adaptive web (pp. 325-341). Springer Berlin Heidelberg.
Quilan, J.R., 1983. Learning efficient classification procedures and their application to chess end games. Machine Learning: An AI Approach, 1.
Ramage, D., Hall, D., Nallapati, R., and Manning, C. D. (2009). Labeled LDA: A supervised topic model for credit attribution in multi-labeled corpora. In Proc. CEMNLP (vol. 1, pp. 248-256). ACL.
Ratinov, L., and Roth, D. (2009). Design challenges and misconceptions in named entity recognition. In Proceedings CCNLL (pp. 147-155). ACL.
Ritter, A., Clark, S., and Etzioni, O. (2011). Named entity recognition in tweets: an experimental study. In Proc. of the Conf. on Empirical Methods in NLP (pp. 1524-1534). ACL.
Rizzo, G., Troncy, R. (2011). NERD: Evaluating Named Entity Recognition Tools in the Web of Data. In Workshop on WEKEX’11, Bonn, Germany, 1-16.
Rizzo, G., Troncy, R., Hellmann, S., and Bruemmer, M. (2012). NERD meets NIF: Lifting NLP Extraction Results to the Linked Data Cloud. LDOW, 937.
Ruck, D. W., Rogers, S. K., Kabrisky, M., Oxley, M. E., and Suter, B. W. (1990). The multilayer perceptron as an approximation to a Bayes optimal discriminant function. Neural Networks, IEEE Trans. on (vol. 1, n. 4, pp. 296-298).
Sacenti, J.A.P., Salvini, F., Fileto, R., Raffaetà, A., Roncato, A. (2015) Automatically Tailoring Semantics-Enabled Dimensions for Movement DW. In: DaWaK 2015: 205-216
Sha, F., and Pereira, F. (2003). Shallow parsing with conditional random fields. In Proc. NC of the ACL: HLT (vol. 1, pp. 134-141). ACL
Speck, R., and Ngomo, A. C. N. (2014). Named entity recognition using FOX. In Proc. of the 2014 Int. Conf. (vol. 1272, pp. 85-88). CEUR-WS. org.
Tjong Kim Sang, E. F., and De Meulder, F. (2003). Introduction to the CoNLL-2003 shared task: Languageindependent named entity recognition. In Proc. CNLL at HLT-NAACL (vol. 4, pp. 142-147). ACL.
Toutanova, K., Klein, D., Manning, C. D., and Singer, Y. (2003). Feature-rich part-of-speech tagging with a cyclic dependency network. In Proc. CNAC ACL: HLT (vol. 1, pp. 173-180)
Usbeck, R., Ngomo, A. C. N., Röder, M., Gerber, D., Coelho, S. A., Auer, S., and Both, A. (2014). AGDISTISgraph- based disambiguation of named entities using linked data. In The Semantic Web – ISWC 2014 (pp. 457-471). Springer International Publishing.
Voorhees, E. M. (1999). The TREC-8 Question Answering Track Report. In Trec (vol. 99, pp. 77-82).
Voutilainen, A. (2003). Part-of-speech tagging. The Oxford handbook of computational linguistics (pp. 219-232).
Wang, W., and Stewart, K. (2015). Spatiotemporal and semantic information extraction from Web news reports about natural hazards. Comp., Env. Urb. Syst., 50, 30-40.
Willingham, D. T. (2007). Cognition: The thinking animal. Englewood Cliffs, NJ: Pearson/Prentice Hall.
Witten, I.H., and Frank, E. (2011). Data Mining: Practical machine learning tools and techniques. Morgan Kaufmann, 664pp.
Xia, C., Hu, J., Zhu, Y., Naaman, M. (2015). What Is New in Our City? A Framework for Event Extraction Using Social Media Posts. In: Advances in KDD Mining, Springer, 16-32.
Publicado
17/05/2016
Como Citar
CURDULINO, Raucer; ALVES, Pedro Yuri Araujo Lima; DELGADO, Karina Valdivia.
Sistema para Resolver o Problema de Roteamento de Estoque Baseado em Técnicas de Monte Carlo. In: SIMPÓSIO BRASILEIRO DE SISTEMAS DE INFORMAÇÃO (SBSI), 12. , 2016, Florianópolis.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2016
.
p. 369-376.
DOI: https://doi.org/10.5753/sbsi.2016.5984.
