Academic Journals Database
Disseminating quality controlled scientific knowledge

O problema do carteiro chinês, algoritmos exatos e um ambiente MVI para análise de suas instâncias: sistema XNÊS

ADD TO MY LIST
 
Author(s): Marcos José Negreiros Gomes | Wiler Rodrigues Coelho Júnior | Augusto Wagner de Castro Palhano | Emanuel Ferreira Coutinho | Gerson Alves de Castro | Francisco José Negreiros Gomes | Gianfrancesca Cutini Barcellos | Bruno Fernandes Rezende | Lúcio Wagner Lessa Pereira

Journal: Pesquisa Operacional
ISSN 0101-7438

Volume: 29;
Issue: 2;
Start page: 323;
Date: 2009;
Original page

Keywords: problema do carteiro chinês | grafos | modelagem visual interativa | Chinese postman problem | graphs | visual interactive modeling

ABSTRACT
Apresenta-se um estudo geral sobre o Problema do Carteiro Chinês (PCC), nas versões simétrica, orientada e mista, do ponto de vista dos algoritmos exatos até então publicados sobre o assunto. Para apresentar as soluções exatas das versões do problema, foram utilizadas as implementações exatas dos algoritmos de Sherafat (dos casos orientado e misto) com adaptações, e de Edmonds & Johnson (do simétrico) adaptada de Burkard & Derigs. O trabalho também apresenta as diferenças de comportamento dos métodos em situações bastante peculiares, através de um conjunto de instâncias testes com o objetivo de apurar mais detalhadamente o seu desempenho. Por fim, mostramos o software (Sistema XNÊS) idealizado para gerar grafos instâncias (simétricos, orientados e/ou mistos) e soluções exatas para estas versões do Problema do Carteiro Chinês (PCC). Implementa-se aqui uma versão de um modelo de geração de grafos no modo de Modelagem Visual Interativa (MVI), através de um editor específico de grafos com atributos e informações de efeitos visuais nos vértices e nas ligações. Este software pode ser usado como demonstração efetiva da importância do problema na academia, assim como um potencial analista de rotas de problemas semelhantes, ou até mesmo como verificador de instâncias das mais complicadas ou de razoável porte do PCC.We do a general study over the Chinese Postman Problem (CCP), in the symmetric, oriented and mixed cases, in consideration to the modeling and exact algorithms published most recently. To find exact solutions "for/to" these versions of the problem we show and use exact implementations reported by Sherafat (to the Oriented and the Mixed cases) with adaptations, Edmonds and Johnson (symmetric case) adapted from Burkard & Derigs approach. The work also presents a set of evaluation instances to the methods, and peculiarities behind them to the performance and solution quality analysis. In this work we show the software XNÊS, which was created to generate graph instances (pure symmetric, mixed and pure oriented) for the Chinese Postman Problem (CPP). We show an implementation of a graph generator in a Visual Interactive Modeling (MVI) mode, which builds graphs with attributes and bindings on nodes and links. This software can be used to demonstrate the effective importance of this problem and its application to academia, as its potential to solve other arc routing problems, or to verify difficult and/or high scale CPP instances.
Save time & money - Smart Internet Solutions      Why do you need a reservation system?