Heuristics for a dynamic rural postman problem

• Type: Article in International Scientific Journal
• Date: 2007

Authors

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

Journal

Title: Computers and Operations Research

Vol. 34 No. 11

Pages: 3281-3294

ISSN: 0305-0548

Publisher: Elsevier

Indexing

ISI Web of Knowledge - 22 Citations

ISI Web of Science

Scopus - 23 Citations

INSPEC

Scientific classification

CORDIS: Technological sciences > Engineering > Industrial engineering ; Physical sciences > Mathematics > Applied mathematics > Operations research

FOS: Engineering and technology > Civil engineering

Other information

Authenticus ID: 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.

Language: English

Type (Professor's evaluation): Scientific

No. of pages: 14