Skip to main content
SpringerLink
Log in

Heuristics for the plate-cutting traveling salesman problem

  • Published:
IIE Transactions

Abstract

In this paper we present a new problem that arises when parts are cut from large plates of metal or glass. We call this problem the plate-cutting traveling salesman problem (P-TSP) because it requires the determination of a minimum-length tour such that exactly one point must be visited on each of a number of given polygons. We present a mathematical formulation of the problem and show that the problem is a variation of the well-known traveling salesman problem. We examine the problem when the order in which parts are to be cut is known. For this problem we present a Lagrangean decomposition of the problem and develop lower bounds and heuristics based on this decomposition. Computational testing on problems with 5--40 polygons reveals that the heuristics give fairly good solutions. When the order in which polygons are to be cut is known, the heuristic solutions are within 3--4% of the optimal. The decomposition-based heuristics are embedded in a variable r-opt heuristic for the overall problem.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Dror, M., Stern, H. and Trudeau, P. (1987) Postman tours on a graph with precedence relation on arcs. Networks, 17(3), 283–294.

    Google Scholar 

  2. Manber, U. and Israni, S. (1984) Pierce point minimization and optimal path determination in flame cutting. Journal of Manufacturing Systems, 3(1), 81–89.

    Google Scholar 

  3. Francis, R., McGinnis, L. and White, J. (1992) Facility Layout and Location: An Analytical Approach, 2nd edn, Prentice-Hall, Englewood Cliffs, NJ.

    Google Scholar 

  4. Lawler, E., Lenstra, J., Rinnooy Kan, A. and Shmoys, D. (1985) The Traveling Salesman Problem, A Guided Tour of Combinatorial Optimization. John Wiley and Sons, New York.

    Google Scholar 

  5. Laporte, G., Mercure, H. and Nobert, Y. (1985) Finding the shortest Hamiltonian circuit through n clusters: a lagrangean relaxation approach. Congressus Numerantium, 48, 277–290.

    Google Scholar 

  6. Noon, C. and Bean, J. (1991) A Lagrangean based approach for the asymmetric generalized traveling salesman problem. Operations Research, 39(4), 623–632.

    Google Scholar 

  7. Noon, C. and Bean, J. (1989) An efficient transformation of the generalized traveling salesman problem. Working Paper, University of Tennessee, Knoxville, TN.

    Google Scholar 

  8. Blazewicz, J., Hawryluk, P. and Walkowiak, R. (1993) Using a tabu search approach for solving the two-dimensional irregular cutting problem. Annals of Operations Research, 41, 313–325.

    Google Scholar 

  9. Garey, M.R., Graham, R.L. and Johnson, D.S. (1976) Some NP-complete geometric problems, in Proc. 8th Ann. ACM Symposium on Theory of Computing, ACM, New York, pp. 10–22.

    Google Scholar 

  10. Lin, S. and Kernighan, B. (1973) An effective heuristic algorithm for the traveling salesman problem. Operations Research, 21(2), 498–516.

    Google Scholar 

  11. Guignard, M. and Kim, S. (1987) Lagrangean decomposition: a model yielding stronger Lagrangean bounds. Mathematical Programming, 39(2), 215–228.

    Google Scholar 

  12. Geoffrion, A.M. (1974) Lagrangean relaxation and its uses in integer programming, in Mathematical Programming Study, vol. 2, North Holland, Amsterdam. pp. 82–114.

    Google Scholar 

  13. Ahuja, R.K., Magnanti, T.L. and Orlin, J.B. (1989) Network flows, in Optimization, Nemhauser, G.L. et al. (ed.), Handbooks in Operations Research and Management Science, vol. 1, North-Holland, Amsterdam.

    Google Scholar 

  14. Goldfarb, D. and Todd M.J. (1989) Linear programming, in Optimization, Nemhauser, G.L. et al. (ed.), Handbooks in Operations Research and Management Science vol. 1, North-Holland, Amsterdam.

    Google Scholar 

  15. Stewart, W. (1977) A computationally efficient heuristic for the traveling salesman problem, in Proceedings of the 13th Annual Meeting of S. E. TIMS, The Institute of Management Science, Providence, RI. pp. 75–78.

    Google Scholar 

  16. Bozer, Y., Schorn, E. and Sharp, G. (1990) Geometric approaches to the Chebyshev traveling salesman problem. IIE Transactions, 22(3), 238–254.

    Google Scholar 

  17. Fischeti, M. and Toth, P. (1989) An additive bounding procedure for combinatorial optimization problems. Operations Research, 37(2), 319–328.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Caradco Inc., 201 Evans Drive Rantoul, IL, 61866, USA

    JEFFREY HOEFT

  2. Department of Mechanical and Industrial Engineering, University of Illinois at Urbana-Champaign, 1206 W. Green Street, Urbana, IL, 61801, USA

    UDATTA S. PALEKAR

Authors
  1. JEFFREY HOEFT
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. UDATTA S. PALEKAR
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

HOEFT , J., PALEKAR , U.S. Heuristics for the plate-cutting traveling salesman problem. IIE Transactions 29, 719–731 (1997). https://doi.org/10.1023/A:1018582320737

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1023/A:1018582320737

Keywords

Search

Navigation