scientific article; zbMATH DE number 4031726

From MaRDI portal
Publication:3772248





A new bound rule at branch and bound method for travelling salesman problem is proposed. The next evident statement is the rule basis: the shortest path from vertex V to W passes through N vertices and has minimal weight among all paths from V to W passing through these N vertices. To avoid a large scale enumeration, N is at most 5. Suggested rule was applied to graphs having up to 67 vertices. The search tree branches were cut down at 15 per cent, as compared with the initial search tree. As the paper reports, the method was used for linen way optimization at dye-works, and for optimal data collection at comprehensive automation of semiconductor material parameter measuring.











This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3772248)