Please use this identifier to cite or link to this item: https://hdl.handle.net/10356/52085
Title: Rank-based memetic algorithm for capacitated arc routing problems
Authors: Mittal, Sameer.
Keywords: DRNTU::Engineering::Computer science and engineering::Theory of computation::Analysis of algorithms and problem complexity
DRNTU::Engineering
Issue Date: 2013
Abstract: 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.
URI: http://hdl.handle.net/10356/52085
Rights: Nanyang Technological University
Fulltext Permission: restricted
Fulltext Availability: With Fulltext
Appears in Collections:SCSE Student Reports (FYP/IA/PA/PI)

Files in This Item:
File Description SizeFormat 
SCE0120235.pdf
  Restricted Access
1.91 MBAdobe PDFView/Open

Google ScholarTM

Check

Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.