A Two-Phase Distributed Ruin-and-Recreate Genetic Algorithm for Solving the Vehicle Routing Problem With Time Windows
Open Access
- 14 September 2020
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Access
- Vol. 8, 169851-169871
- https://doi.org/10.1109/access.2020.3023741
Abstract
Developing an algorithm that can solve the vehicle routing problem with time windows (VRPTW) and create near-optimal solutions with the least difference in magnitude is a challenging task. This task is evident from the fact that when an algorithm runs multiple times based on a given instance, the generated solutions deviate from each other and may not near-optimal. For this reason, an algorithm that can solve these problems is effective and highly sought after. This paper proposes a novel systematic framework using a two-phase distributed ruin-and-recreate genetic algorithm (RRGA). The two-phase consists of the RRGA phase and ruin-and-recreate (RR) phase, which is designed to run in the distributed computing environment that leveraging these networked resources. This combination of algorithms harnesses the strength of the search diversification and intensification, thereby producing very high-quality solutions. Experiments with Solomon’s benchmark show the RRGA can produce results superior to the recently published hybrid algorithms, best-known solutions, and nine leading hybrid algorithms.Funding Information
- Universiti Tunku Abdul Rahman, UTAR Research Fund (IPSR/RMC/UTARRF/2019-C2/M01)
This publication has 39 references indexed in Scilit:
- A hybrid algorithm for vehicle routing problem with time windowsExpert Systems with Applications, 2011
- Multi-objective vehicle routing problem with time windows using goal programming and genetic algorithmApplied Soft Computing, 2010
- A branch‐and‐price‐based large neighborhood search algorithm for the vehicle routing problem with time windowsNetworks, 2009
- Solving a vehicle routing problem with time windows by a decomposition technique and a genetic algorithmExpert Systems with Applications, 2009
- A memetic algorithm for the vehicle routing problem with time windowsRAIRO - Operations Research, 2008
- Multi-Objective Genetic Algorithms for Vehicle Routing Problem with Time WindowsApplied Intelligence, 2006
- A Hybrid Multiobjective Evolutionary Algorithm for Solving Vehicle Routing Problem with Time WindowsComputational Optimization and Applications, 2005
- A unified tabu search heuristic for vehicle routing problems with time windowsJournal of the Operational Research Society, 2001
- Record Breaking Optimization Results Using the Ruin and Recreate PrincipleJournal of Computational Physics, 2000
- Complexity of vehicle routing and scheduling problemsNetworks, 1981