Heuristics for a dynamic rural postman problem

• Tipo: Artigo em Revista Científica Internacional
• Data: 2007

Autores

Luís M. Moreira (Autor) Outra; José F. Oliveira (Autor) FEUP; A. Miguel Gomes (Autor) Outra; J. Soeiro Ferreira (Autor) FEUP

Revista

Título: Computers and Operations Research

Vol. 34 Nº 11

Páginas: 3281-3294

ISSN: 0305-0548

Editora: Elsevier

Indexação

ISI Web of Knowledge - 22 Citações

ISI Web of Science

Scopus - 23 Citações

INSPEC

Classificação Científica

CORDIS: Ciências Tecnológicas > Engenharia > Engenharia industrial ; Ciências Físicas > Matemática > Matemática aplicada > Investigação operacional

FOS: Ciências da engenharia e tecnologias > Engenharia civil

Outras Informações

ID Authenticus: P-004-6ER

DOI: 10.1016/j.cor.2005.12.008

Resumo (PT): This paper presents a very special cutting path determination problem appearing in a high precision tools factory, and provides two new heuristics for its resolution. Particular features of both the cutting process, and of the material to be cut, bring in a set of unusual constraints, when compared with other cutting processes, which confer additional complexity and originality to the problem. In particular, this is a matter of practical and economic relevance, since the solution methods are intended to be implemented in a real-life industrial environment. The concept of dynamic graph is exploited to deal with the arc routing problem under study, which is modelled as a dynamic rural postman problem. The constructive heuristics developed, the “higher up vertex heuristic” (HUV) and the “minimum empty path heuristic” (MEP) are tested with real data sets.

Abstract (EN): This paper presents a very special cutting path determination problem appearing in a high precision tools factory, and provides two new heuristics for its resolution. Particular features of both the cutting process, and of the material to be cut, bring in a set of unusual constraints, when compared with other cutting processes, which confer additional complexity and originality to the problem. In particular, this is a matter of practical and economic relevance, since the solution methods are intended to be implemented in a real-life industrial environment. The concept of dynamic graph is exploited to deal with the arc routing problem under study, which is modelled as a dynamic rural postman problem. The constructive heuristics developed, the "higher up vertex heuristic" (HUV) and the "minimum empty path heuristic" (MEP) are tested with real data sets.

Idioma: Inglês

Tipo (Avaliação Docente): Científica

Nº de páginas: 14