Rank-based memetic algorithm for capacitated arc routing problems

• Main Author: Mittal, Sameer.
• Other Authors: Ong Yew Soon
• Format: Final Year Project
• Language: English
• Published: 2013
• Subjects: DRNTU::Engineering::Computer science and engineering::Theory of computation::Analysis of algorithms and problem complexity; DRNTU::Engineering
• Online Access: http://hdl.handle.net/10356/52085
• Institution: Nanyang Technological University

The Capacitated Arc Routing Problem (CARP) has gathered a lot of interest lately. It has a wide range of applications in real world problems, such as waste collection, winter gritting, postal delivery, etc. A number of different algorithms have been proposed to efficiently solve this problem. As CARP is an NP-hard problem, heuristic and meta-heuristic approaches are adopted for medium to large-scale problems. Memetic algorithms are of particular interest with respect to CARP. In 2001, Lacomme introduced a memetic algorithm (known as the LMA) to solve this NP-hard problem, which proved to be an effective approach to solve this problem. Yi Mei et al. further improved this to the Improved LMA (ILMA). Tang et al. proposed a memetic algorithm that scans the extended neighborhood in search for better solutions, using the Merge-Split operator. From the study of these algorithms (and memetic algorithms in general), it is clear that local search is one of the key factors distinguishing algorithm performance. Parameters of local search such as step size play an important role in determining the quality of the solution, and the computational cost of the algorithm. Keeping that in mind, this project looks at a Rank Based Memetic Algorithm that suggests a new edge selection criteria for local search, and also improves the capability of the search operation to search within a larger neighborhood, thereby discovering new search schemas within the scope of local search itself. The proposed Rank-based Neighborhood Search operator can search for solutions in a larger neighborhood, which can then be refined using the classical local search operators. This algorithm has been tested on seven benchmark test sets for CARP, and it outperforms several state-of-the-art algorithms.