Uma análise do Parâmetro Big M do Modelo Matemático para o Problema do Carteiro Rural Capacitado com Janelas de Tempo/ An Analysis of the Big M Parameter of the Mathematical Model for the Capacitated Rural Postman Problem with Time Windows

Diego Venancio Thomaz, Gustavo Valentim Loch, Tatiane Tambarussi, Cassius Tadeu Scarpin

Abstract


As formulações matemáticas para os Problemas de Roteamento em Arcos com Janelas de Tempo, em geral, contém um conjunto de restrições formado por inequações não lineares e para a utilização do método exato de resolução “Branch-and-Bound” existe a necessidade de linearização desse conjunto de restrições. Para isso, a maior parte dos trabalhos que apresentam formulações matemáticas para Problemas de Roteamento em Arcos com Janelas de Tempo utilizam-se de uma constante de grande valor, um parâmetro “Big M”. Este trabalho traz uma análise, por meio do solver GUROBI, do desempenho do método exato de resolução em uma formulação matemática baseada em Programação Linear Inteira Mista do Problema do Carteiro Rural Capacitado com Janelas de Tempo quando são consideradas três diferentes metodologias para gerar o parâmetro Big M do modelo. As três metodologias foram apresentadas nos trabalhos de Monroy-Licht et al. (2014) e Thomaz et al. (2018).  Os testes são realizados sobre 20 instâncias adaptadas de Monroy-Licht et al. (2014) que possuem até 60 nós, 90 arestas, 45 arestas requeridas e 4 veículos. A aplicação real do problema é associada à coleta de lixo. Resultados computacionais mostram que não há metodologia predominante sobre as demais, mas os diferentes valores do parâmetro Big M podem gerar relaxações fracas e dificuldades numéricas no método exato de resolução

Keywords


Problema de Roteamento em Arcos, Restrições de Janelas de Tempo, Parâmetro Big M.

References


CORBERÁN, A.; PRINS, C. Recent Results on Arc Routing Problems: An Annotated Bibliographys. Networks. p.50-69, 2010.

GOLDEN, B.L.; WONG, R.T. Capacitated Arc Routing Problems. Networks. Vol. 11, p.305-315, 1981.

GUAN, M. Graphic programming using odd and even points. Chinese Mathematics. Vol. 1, p.273-277, 1962.

LACOMME, P.; PRINS, C.; RAMDANE-CHÉRIF, W. Evolutionary Algorithms for Multiperiod Arc Routing Problems. IPMU 2002 (Ed.); 9th Int. Conf. on Information Processing and Management of Uncertainty in Knowledge-Based Systems. p.1-8. 2002.

MONROY, M. L; AMAYA, C. A.; LANGEVIN, A. The Periodic Capacitated Arc Routing Problem With Irregular Services. Discrete Applied Mathematics. Vol. 161, p.691-701, 2013.

MONROY-LICHT, M. L; AMAYA, C. A.; LANGEVIN, A. The Rural Postman Problem with Time Windows. Networks. p.169-180, 2014.

MULLASERIL, P.A. Capacitated rural postman problem with time Windows and Split Delivery. Phd Thesis, University of Arizona, 1996.

SUN, J.; MENG, Y.; TAN, G. An integer programming approach for the Chinese postman problem with time-dependent travel time. J. Comb. Optim. Vol. 29, p.565-588, 2015.

THOMAZ, D. V.; LOCH, G. V.; SCARPIN, C.T.; SCHENEKEMBERG, C.M. A Mathematical Model for the Periodic Capacitated Arc Routing Problem with Time Windows. IEEE Latin America Transactions. Vol. 16, p.2567-2573, 2018.

WAN, H. F.; WEN, Y. P. Time-Constrained Chinese Postman Problems. Computers and Mathematics with Applications. Vol. 44, p.375-387, 2002.




DOI: https://doi.org/10.34117/bjdv6n1-011

Refbacks

  • There are currently no refbacks.