| Name: | Description: | Size: | Format: | |
|---|---|---|---|---|
| 136.16 KB | Adobe PDF |
Advisor(s)
Abstract(s)
The Rural Postman Problem (RPP) is a particular Arc Routing Problem (ARP) which consists
of determining a minimum cost circuit on a graph so that a given subset of required edges is traversed. The
RPP is an NP-hard problem with significant real-life applications. This paper introduces an original
approach based on Memetic Algorithms - the MARP algorithm - to solve the RPP and, also deals with an
interesting Industrial Application, which focuses on the path optimization for component cutting
operations. Memetic Algorithms are a class of Metaheuristics which may be seen as a population strategy
that involves cooperation and competition processes between population elements and integrates “social
knowledge”, using a local search procedure. The MARP algorithm is tested with different groups of
instances and the results are compared with those gathered from other publications. MARP is also used in
the context of various real-life applications.
Description
Keywords
Cutting path apllications Memetic algorithms Rural postman problem