6533b81ffe1ef96bd1277da0
RESEARCH PRODUCT
A penalty-based edge assembly memetic algorithm for the vehicle routing problem with time windows
Olli BräysyWout DullaertYuichi Nagatasubject
Mathematical optimizationSDG 16 - PeaceGeneral Computer ScienceHeuristic (computer science)EconomicsSDG 16 - Peace Justice and Strong InstitutionsCrossoverMemetic algorithmManagement Science and Operations ResearchEAX mode/dk/atira/pure/sustainabledevelopmentgoals/peace_justice_and_strong_institutionsPenalty functionVehicle routingJustice and Strong InstitutionsModeling and SimulationVehicle routing problemMemetic algorithmPenalty methodEnhanced Data Rates for GSM EvolutionRouting (electronic design automation)AlgorithmTime windowsMathematicsdescription
In this paper, we present an effective memetic algorithm for the vehicle routing problem with time windows (VRPTW). The paper builds upon an existing edge assembly crossover (EAX) developed for the capacitated VRP. The adjustments of the EAX operator and the introduction of a novel penalty function to eliminate violations of the time window constraint as well as the capacity constraint from offspring solutions generated by the EAX operator have proven essential to the heuristic's performance. Experimental results on Solomon's and Gehring and Homberger benchmarks demonstrate that our algorithm outperforms previous approaches and is able to improve 184 best-known solutions out of 356 instances.
| year | journal | country | edition | language |
|---|---|---|---|---|
| 2010-04-01 | Computers and Operations Research |