Article ID: | iaor20083868 |
Country: | United Kingdom |
Volume: | 34 |
Issue: | 11 |
Start Page Number: | 3281 |
End Page Number: | 3294 |
Publication Date: | Nov 2007 |
Journal: | Computers and Operations Research |
Authors: | Ferreira J. Soeiro, Oliveira Jos F., Gomes A. Miguel, Moreira Lus M. |
Keywords: | vehicle routing & scheduling, heuristics |
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.