Please use this identifier to cite or link to this item: https://hdl.handle.net/10356/52085
Full metadata record
DC FieldValueLanguage
dc.contributor.authorMittal, Sameer.
dc.date.accessioned2013-04-22T06:30:11Z
dc.date.available2013-04-22T06:30:11Z
dc.date.copyright2013en_US
dc.date.issued2013
dc.identifier.urihttp://hdl.handle.net/10356/52085
dc.description.abstractThe 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.en_US
dc.format.extent45 p.en_US
dc.language.isoenen_US
dc.rightsNanyang Technological University
dc.subjectDRNTU::Engineering::Computer science and engineering::Theory of computation::Analysis of algorithms and problem complexityen_US
dc.subjectDRNTU::Engineeringen_US
dc.titleRank-based memetic algorithm for capacitated arc routing problemsen_US
dc.typeFinal Year Project (FYP)en_US
dc.contributor.supervisorOng Yew Soonen_US
dc.contributor.schoolSchool of Computer Engineeringen_US
dc.description.degreeBachelor of Engineering (Computer Engineering)en_US
dc.contributor.researchCentre for Computational Intelligenceen_US
item.fulltextWith Fulltext-
item.grantfulltextrestricted-
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.