The traveling salesman problem: mathematical models and solution methods

• Grant number: 07/08352-2
• Support Opportunities: Scholarships in Brazil - Scientific Initiation
• Start date: June 01, 2008
• End date: December 31, 2008
• Field of knowledge: Engineering - Production Engineering - Operational Research
• Principal Investigator: Maria Do Socorro Nogueira Rangel
• Grantee: Michelli Maldonado Carretero
• Host Institution: Instituto de Biociências, Letras e Ciências Exatas (IBILCE). Universidade Estadual Paulista (UNESP). Campus de São José do Rio Preto. São José do Rio Preto , SP, Brazil
• Associated research grant: 06/03496-3 - Theory and practice of cutting and packing problems, AP.TEM

Abstract

The production planning in industries that manufactures several items in many different machines is a complex task that has to be frequently done. In certain industries sectors such as soft drinks, furniture, electric wire and cable, there are sequence dependent production set up costs and times. Sometimes the production planning also involves the definition of items lot size (and/or raw material cut - cutting stock) as well as items scheduling. In general, in the industry practice, the lot sizing (and/or cutting stock) and scheduling problem is solved separately. That is, first the production lot sizes (and/or cutting stock) are defined and afterwards the production schedules. The Asymmetric Travelling Salesman problem can be used to capture the scheduling decisions in an integrated model (e.g. lot sizing and scheduling model, cutting stock and scheduling model). The objective of this project is to investigate mathematical models and exact solution methods for the Asymmetric Travelling Salesman problem. The focus is to study the problem automatic reformulation using valid inequalities and the efficiency of the branch and cut method. (AU)