Hybrid Quantum Genetic Algorithm for Vehicle Routing Problem with Time Window

Abstract

Vehicle Routing Problem with Time Window (VRPTW) considered being the most popular and most widespread widely studied, because it includes the time windows constraint, which represents factual life situations. A large number of algorithms have been suggested to deal with VRPTW, which shows its importance, but none of them succeeded to be implemented efficiently on all situations of the problem. Therefore, the need to apply new or advanced algorithms to the VRPTW still exists. Recently, “Quantum Genetic Algorithm”(QGA) has been presented as an powerful method to handle many real difficult problems and it has not been applied to solve the VRPTW. Therefore, in this work, the performance of QGA for solving the VRPTW is investigated. The obtained results show that the QGA capability of enhancing the solution quality decreases gradually during the search. That’s mean the QGA stuck in local optima. In order to improve the quality of generated solution, a hybrid QGA (HQGA) is proposed. In this hybridization a Hill-Climbing algorithm (HC) is integrated with the QGA. This integration enables the QGA to explore the search space and the HC to exploit the search space. The experimental results show that the HQGA has attained competitive results in comparison to other compared approaches.