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
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...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Associação Brasileira de Engenharia de Produção (ABEPRO)
2006-12-01
|
| Series: | Production |
| Subjects: | |
| Online Access: | http://www.scielo.br/scielo.php?script=sci_arttext&pid=S0103-65132006000300014 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1850181393504534528 |
|---|---|
| author | Moacir Godinho Filho Rogério de Ávila Ribeiro Junqueira |
| author_facet | Moacir Godinho Filho Rogério de Ávila Ribeiro Junqueira |
| author_sort | Moacir Godinho Filho |
| collection | DOAJ |
| description | 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.<br>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. |
| format | Article |
| id | doaj-art-4ba1b343a60d4d008d0e591dcc9385c6 |
| institution | OA Journals |
| issn | 0103-6513 |
| language | English |
| publishDate | 2006-12-01 |
| publisher | Associação Brasileira de Engenharia de Produção (ABEPRO) |
| record_format | Article |
| series | Production |
| spelling | doaj-art-4ba1b343a60d4d008d0e591dcc9385c62025-08-20T02:17:54ZengAssociação Brasileira de Engenharia de Produção (ABEPRO)Production0103-65132006-12-0116353855110.1590/S0103-65132006000300014Problema 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 analysisMoacir Godinho FilhoRogério de Ávila Ribeiro JunqueiraO 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.<br>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.http://www.scielo.br/scielo.php?script=sci_arttext&pid=S0103-65132006000300014Logísticaproblema do carteiro chinêsescolha de método de soluçãotempo computacionalLogisticsChinese Postman Problemsolution procedure choicecomputational time |
| spellingShingle | Moacir Godinho Filho Rogério de Ávila Ribeiro Junqueira 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 Production Logística problema do carteiro chinês escolha de método de solução tempo computacional Logistics Chinese Postman Problem solution procedure choice computational time |
| title | 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 |
| title_full | 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 |
| title_fullStr | 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 |
| title_full_unstemmed | 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 |
| title_short | 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 |
| title_sort | problema do carteiro chines escolha de metodos de solucao e analise de tempos computacionais chinese postman problem solution methods choice and computational time analysis |
| topic | Logística problema do carteiro chinês escolha de método de solução tempo computacional Logistics Chinese Postman Problem solution procedure choice computational time |
| url | http://www.scielo.br/scielo.php?script=sci_arttext&pid=S0103-65132006000300014 |
| work_keys_str_mv | AT moacirgodinhofilho problemadocarteirochinesescolhademetodosdesolucaoeanalisedetemposcomputacionaischinesepostmanproblemsolutionmethodschoiceandcomputationaltimeanalysis AT rogeriodeavilaribeirojunqueira problemadocarteirochinesescolhademetodosdesolucaoeanalisedetemposcomputacionaischinesepostmanproblemsolutionmethodschoiceandcomputationaltimeanalysis |