Problema do carteiro chinês: escolha de métodos de solução e análise de tempos computacionais
Chinese Postman Problem: solution methods choice and computational time analysis
Godinho Filho, Moacir; Junqueira, Rogério de Ávila R.
http://dx.doi.org/10.1590/S0103-65132006000300014
Prod, vol.16, n3, p.538-551, 2006
Resumo
O presente trabalho trata do problema do carteiro chinês (CPP). Primeiramente, por meio da estruturação e análise de uma revisão bibliográfica, propõe-se um algoritmo para auxiliar na escolha de métodos adequados a fim de se resolver o CPP. Em seguida, o algoritmo desenvolvido é utilizado na escolha de métodos para resolução do CPP em dois casos reais. O trabalho também verifica se, nos problemas práticos de logística urbana estudados, é válida uma premissa citada na literatura de que a complexidade do CPP com uma única entidade em problemas mistos é muito maior do que para problemas direcionados e não direcionados. Para isto, são selecionados casos reais de coleta de lixo e correios em uma cidade do interior paulista. Este trabalho conclui que, para problemas extraídos de situações logísticas reais, inexistem significativas diferenças entre o tempo computacional para a resolução dos modelos matemáticos com vistas à obtenção de grafos eulerianos não direcionados, direcionados e mistos.
Palavras-chave
Logística, problema do carteiro chinês, escolha de método de solução, tempo computacional
Abstract
This work deals with Chinese Postman Problem (CPP). First, this paper, based on structuring and analyzing a CPP literature review, proposes an algorithm to help choosing suitable methods to solve CPP. The proposed algorithm is used on two real-world cases. This paper also verifies if in real urban logistics cases it is valid the assumption that the obtaining the optimal solution for the mixed 1 vehicle CPP is more difficult than directed and undirected cases. To accomplish this goal real-world cases are selected (household refuse collection and postal service). This work concludes that for real-world situations there are no significant differences on computational time between directed, undirected and mixed CPP.
Keywords
Logistics, Chinese Postman Problem, solution procedure choice, computational time
References
AHR, D.; REINELT, G. A tabu search algorithm for the min-max k-Chinese postman problem. Computers and Operations Research, v. 33, issue 12, p. 3403-3422, 2006.
AHUJA, R. K.; MAGNANTI, T. L.; ORLIN, J. B. Network Flows – Theory, Algorithms and Applications. Prentice Hall, Upper Saddle River, New Jersey, 1993.
BAKER, E. K. An exact algorithm for the time constrained travelling salesman problem. Operations Research, v. 31, n. 5, p. 938-945, 1983.
BELTRAMI, E.; BODIN, L. Networks and vehicle routing for municipal waste collection. Networks, v. 4, p. 65-94, 1974.
BRYMAN, A. Research methods and organization studies. Uniwin Hyman. London, 1989.
CHRISTOFIDES, N. Graph Theory – An Algorithmic Approach. Academic Press, London, 1975.
CHRISTOFIDES, N.; BENAVENT, E.; CAMPOS, A.; CORBRAN, A.; MOTA, E. An optimal method for the mixed postman problem. Proceedings of the 11th IFIP Conference, Copenhagen, Denmark, p. 641-649, 1983.
CORBERAN, A.; MARTI, R.; SANCHIS, J. M. A GRASP heuristic for the mixed Chinese Postman Problem. European Journal of Operational Research, v. 142, issue 1, p. 70-80, October 2002.
COSTA, M. A. B. Métodos para construção de rotas Eulerianas em grafos mistos com aplicação na distribuição de bens e serviços. Dissertação de Mestrado. Campina Grande, Paraíba, 1982.
DERIGS, U. & METZ, A. Solving (Large Scale) Matching Problems. Mathematical Programming, v. 50, p. 113-121, 1991.
EDMONDS, J. & JOHNSON, E. Matching, Euler Tours and the Chinese Postman Problem. Mathematical Programming, v. 5, p. 88-124, 1973.
EISELT, H. A.; GENDREAU, M.; LAPORTE, G. Arc Routing Problems, Part I: The Chinese Postman Problem. Operations Research, v. 43, n. 2, March-April, 1995a.
EISENHARDT, K. M. Building theories form case study research. Academy of Management Review, v. 14, n. 4, 532-550, 1989.
GALIL, Z.; MICALI, S.; GABOW, H. An O(EV log V) Algorithm for Finding a Maximal Weighted Matching in General Graphs. SIAM J. Comp., v. 15, p. 120-130, 1986.
GHIANI, G.; IMPROTA, G.; Algorithm for the hierarchical Chinese Postman Problem. Operations Research Letters, v. 26, n.1, p. 27-32, 2000.
GROTSCHEL, M.; WIN, Z. A Cutting plane algorithm for the Windy Postman Problem. Math. Prog., v. 55, p. 339-358, 1992.
JIANG, H.; KANG, L. Genetic Algorithm for Chinese Postman Problems. Wuhan University Journal of Natural Sciences, v. 8, n. 1B, p. 316-318, 2003
KAUFFMAN, A. Graphs, Dynamic Programming and Finite Games. Academic Press, New York, 1967.
KWAN, M. Graphic Programming using odd or even points. Chinese Math, 1, p. 273-277, 1962.
LARSON, R. C. & ODONI, A. R. Urban Operations Research. Prentice-Hall, Englewood Cliffs, New Jersey, 1981.
LAWLER, E. L. Combinatorial Optimization: Networks and Matroids. Holt, Rinehart & Winston, New York, 1976.
LIN, Y. & ZHAO, Y. A New Algorithm for the directed Chinese Postman Problem. Computers & Operations Research, v. 15, n. 6, p. 577-584, 1988.
MORABITO, R.N. Notas de Aula de Pesquisa Operacional Aplicada à Logística. DEP, UfSCar, 2003.
OPPENHEIM, A. N. Questionaire Design, Inverviewing and Attitude Measurement. Second Edition, London and New York: Pinter Publishers, 2000.
ORLOFF, C.S. A fundamental problem in vehicle routing. Networks, v. 4, p. 35-64, 1974.
PEARN, W.L. & CHOU, J.B. Improved Solutions for the Chinese postman problem on mixed networks. Computers & Operations Research, v. 26, p. 819-827, 1999.
PEARN, W.L.; LIU, C.M. Algorithms for the Chinese postman problem on mixed networks. Computers Ops Res, v. 22, n. 5, p. 479-489, 1995.
RARDIN, R. L. Optimization in Operations Research. Prentice Hall, Upper Saddle River, New Jersey, 1998.
VAN AARDENNE-EHRENFEST, T.; BRUIJN, N.G. Circuits and Trees in Oriented Linear graphs. Simon Stevin, v. 28, p. 293-217, 1951.
WANG, H.; WEN, Y. Time constrained Chinese Postman Problems. Computers and mathematics with Applications, v. 44, n. 3-4, p. 375-387, 2002.
YIN, R. K. Case study research - design and methods. Sage Publications, 2nd Ed., 1994.
YIN, Z.; ZHANG, F.; XU, J. A Chinese Postman Problem based on DNA computing. Journal of Chemical Information and Computer Sciences, v. 42, n. 2, p. 222-224, 2002.
Referências citadas por meio de apud
EULER, L.; Solutio Problematis ad Geometrian Situs Pertinentis. Commentarii academiae scientarum Petropolitanae, 8, p. 128-140, 1736.
FLEISCHNER, H.; Eulerian Graphs and Related Topics (Part 1, Volume 1). Annals of Discrete Mathematics, v. 45, North-Holland, Amsterdan, 1990.
FORD, L. R.; FULKERSON, D. R. Flows in Network Princeton University Press, Princeton N. J., 1962.
GUAN, M. Graphic Programming Using Odd and Even Points. Chinese Mat. 1, p. 273-277, 1962.
Referências complementares
BUDNICK, F. S.; MCLEAVEY, D. W.; MOJENA, R. Principles of Operations Research for Management. IRWIN, Homewood, Illinois, 2nd Edition, 1988.
EISELT, H. A.; GENDREAU, M.; LAPORTE, G. Arc Routing Problems, Part II: The Rural Postman Problem. Operations Research, v. 43, n. 2, March-April, 1995b.
NOBERT, Y; PICARD, J. C. An Optimal Algorithm for the Mixed Chinese Postman Problem. Publication # 799. Centre de Recherche sur les transports. Montreal, Canadá, 1991.
PEARN, W. L. & CHOU, J. B. Algorithms for the Chinese Postman problem on Mixed Networks. Computers & Operations Research, v. 22, n. 5, p. 479-489, 1995.
Facebook
Google+
Twitter
LinkedIn
Mendeley
StumbleUpon
CiteULike
Reddit
Email