An improvement heuristic framework for the laser cutting tool path problem

R.R.H. Dewil; Pieter Vansteenwegen; Dirk Cattrysse; Manuel Laguna; Thomas Vossen

doi:10.1080/00207543.2014.959268

An improvement heuristic framework for the laser cutting tool path problem

R.R.H. Dewil
, Pieter Vansteenwegen
, Dirk Cattrysse
, Manuel Laguna
, Thomas Vossen

Research output: Contribution to Journal › Article › Academic › peer-review

Abstract

This paper deals with generating cutting paths for laser cutting machines by representing a tool path in a novel way. Using the new representation, the tool path problem can be viewed as nding a partitioning of contours which minimizes the sum of the costs of a rooted directed minimum spanning tree to connect the partitions and the costs of a generalized traveling salesman problem (GTSP) solutions within each partition. Using Edmond-Liu's algorithm to solve the arborescence problem, an improved Lin-Kernighan heuristic to solve the GTSP and a heuristic repartitioning approach, tool paths can be generated that are 4.2% faster than those generated by an existing tool path construction heuristic.

Original language	English
Pages (from-to)	1761
Number of pages	1776
Journal	International Journal of Production Research
Volume	53
Issue number	6
DOIs	https://doi.org/10.1080/00207543.2014.959268
Publication status	Published - 19 Mar 2015

UN SDGs

This output contributes to the following UN Sustainable Development Goals (SDGs)

SDG 7 Affordable and Clean Energy

Keywords

laser cutting
path optimizatoin
heuristics
meta heuristics
precedence constraints

Access to Document

10.1080/00207543.2014.959268

Persistent URL (handle)

Persistent link

Cite this

@article{a0db90b61fb54943852c13e8abfa0fec,

title = "An improvement heuristic framework for the laser cutting tool path problem",

abstract = "This paper deals with generating cutting paths for laser cutting machines by representing a tool path in a novel way. Using the new representation, the tool path problem can be viewed as nding a partitioning of contours which minimizes the sum of the costs of a rooted directed minimum spanning tree to connect the partitions and the costs of a generalized traveling salesman problem (GTSP) solutions within each partition. Using Edmond-Liu's algorithm to solve the arborescence problem, an improved Lin-Kernighan heuristic to solve the GTSP and a heuristic repartitioning approach, tool paths can be generated that are 4.2\% faster than those generated by an existing tool path construction heuristic.",

keywords = "laser cutting, path optimizatoin, heuristics, meta heuristics, precedence constraints",

author = "R.R.H. Dewil and Pieter Vansteenwegen and Dirk Cattrysse and Manuel Laguna and Thomas Vossen",

year = "2015",

month = mar,

day = "19",

doi = "10.1080/00207543.2014.959268",

language = "English",

volume = "53",

pages = "1761",

journal = "International Journal of Production Research",

issn = "0020-7543",

publisher = "Taylor and Francis Ltd.",

number = "6",

}

TY - JOUR

T1 - An improvement heuristic framework for the laser cutting tool path problem

AU - Dewil, R.R.H.

AU - Vansteenwegen, Pieter

AU - Cattrysse, Dirk

AU - Laguna, Manuel

AU - Vossen, Thomas

PY - 2015/3/19

Y1 - 2015/3/19

N2 - This paper deals with generating cutting paths for laser cutting machines by representing a tool path in a novel way. Using the new representation, the tool path problem can be viewed as nding a partitioning of contours which minimizes the sum of the costs of a rooted directed minimum spanning tree to connect the partitions and the costs of a generalized traveling salesman problem (GTSP) solutions within each partition. Using Edmond-Liu's algorithm to solve the arborescence problem, an improved Lin-Kernighan heuristic to solve the GTSP and a heuristic repartitioning approach, tool paths can be generated that are 4.2% faster than those generated by an existing tool path construction heuristic.

AB - This paper deals with generating cutting paths for laser cutting machines by representing a tool path in a novel way. Using the new representation, the tool path problem can be viewed as nding a partitioning of contours which minimizes the sum of the costs of a rooted directed minimum spanning tree to connect the partitions and the costs of a generalized traveling salesman problem (GTSP) solutions within each partition. Using Edmond-Liu's algorithm to solve the arborescence problem, an improved Lin-Kernighan heuristic to solve the GTSP and a heuristic repartitioning approach, tool paths can be generated that are 4.2% faster than those generated by an existing tool path construction heuristic.

KW - laser cutting

KW - path optimizatoin

KW - heuristics

KW - meta heuristics

KW - precedence constraints

UR - https://www.scopus.com/pages/publications/84922261572

UR - https://www.scopus.com/pages/publications/84922261572#tab=citedBy

U2 - 10.1080/00207543.2014.959268

DO - 10.1080/00207543.2014.959268

M3 - Article

SN - 0020-7543

VL - 53

SP - 1761

JO - International Journal of Production Research

JF - International Journal of Production Research

IS - 6

ER -

An improvement heuristic framework for the laser cutting tool path problem

Abstract

UN SDGs

Keywords

Access to Document

Persistent URL (handle)

Other files and links

Fingerprint

A review of cutting path algorithms for laser cutters

Construction heuristics for generating tool paths for laser cutters

Cite this