Visiting the traveling salesman problem with Petri nets and application in the glass industry
Pascal Richard, M. Falcon Chang, Nicolas Monmarché, C. Proust · 2002
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.