Premium
Edge assembly‐based memetic algorithm for the capacitated vehicle routing problem
Author(s) -
Nagata Yuichi,
Bräysy Olli
Publication year - 2009
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.20333
Subject(s) - memetic algorithm , vehicle routing problem , crossover , mathematical optimization , computer science , constraint (computer aided design) , routing (electronic design automation) , set (abstract data type) , enhanced data rates for gsm evolution , local search (optimization) , algorithm , mathematics , artificial intelligence , computer network , geometry , programming language
Vehicle routing problems are at the heart of most decision support systems for real‐life distribution problems. In vehicle routing problem a set of routes must be determined at lowest total cost for a number of resources (i.e., fleet of vehicles) located at one or several points (e.g., depots, warehouses) to efficiently service a number of demand or supply points. In this article a new memetic algorithm is suggested for the standard capacitated vehicle routing problem. The proposed algorithm combines the edge assembly (EAX) crossover with well‐known local searches and allows for infeasible solutions with respect to capacity and route duration constraints after invoking the crossover. To address the constraint violation, an efficient modification algorithm is also suggested. Experimental tests on 47 standard benchmarks demonstrate that the suggested method is robust and competitive, finding new best‐known solution to 20 well‐studied instances and repeating the existing best‐known solution for 24 problems in a reasonable computing time. © 2009 Wiley Periodicals, Inc. NETWORKS, 2009