Heuristic for the orthogonal discrete milling with turn costs

• Grant number: 11/18366-6
• Support Opportunities: Scholarships in Brazil - Scientific Initiation
• Start date: December 01, 2011
• End date: July 31, 2012
• Field of knowledge: Physical Sciences and Mathematics - Computer Science - Theory of Computation
• Principal Investigator: Cid Carvalho de Souza
• Grantee: Bruno Espinosa Crepaldi
• Host Institution: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brazil

Abstract

This Scientific Initiation project aims to study the Milling Tour Problem with Turn Costs (MTTC), and create a heuristic for one of its variants known as the Discrete Orthogonal Milling Problem (ODMP). In this problem, we wish to find a close curve that covers all points of a rectilinear polygon when it is traversed by an object of rectangular shape and minimize the cost of conversions performed on the route. It is an NP-hard problem with geometric reference and has various applications, such as numerically controlled machining applications, inspection, spray painting/coating operations, robotic exploration, arc routing, and even mathematical origami.(AU)