Title :
Visiting the traveling salesman problem with Petri nets and application in the glass industry
Author :
Richard, Pierre ; Monmarche, N. ; Proust, C.
Author_Institution :
Lab. d´Inf., Univ. de Tours
Abstract :
We present a Petri net approach to the traveling salesman problem (TSP) in order to solve a planning problem in the glass industry. To a Petri net model can be associated, automatically, an integer linear program. That approach is useful to control the underlying graph structure of linear programs. For that reason, we found an acyclic Petri net, with a totally unimodular matrix, which leads to a polynomial version of the traveling salesman problem when the number of cities is less than 6
Keywords :
Petri nets; computational complexity; glass industry; graph theory; integer programming; linear programming; operations research; travelling salesman problems; Petri nets; TSP; acyclic Petri net; glass industry; graph structure; integer linear program; planning; totally unimodular matrix; traveling salesman problem; Automatic control; Cities and towns; Equations; Flexible manufacturing systems; Glass industry; Job shop scheduling; Linear programming; Petri nets; Polynomials; Traveling salesman problems;
Conference_Titel :
Emerging Technologies and Factory Automation, 1996. EFTA '96. Proceedings., 1996 IEEE Conference on
Conference_Location :
Kauai, HI
Print_ISBN :
0-7803-3685-2
DOI :
10.1109/ETFA.1996.573298
