Hybrid Approach to Solve Vehicle Routing Problem with Time Window Based on Quantum and Evolutionary Computing

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. VRPTW is a problem to find the least distance for a range of ways to deliver goods using a combination of vehicles with a limited capacity and a specific service time window for each customer. Paths must be designed so that each point is visited once by one vehicle only within a certain time period , all routes are starting from one depot and ending with the same depot, and all customers' demands per particular route must not exceed the vehicle's capacity. The customer service must start within the specified time windows. Due to the importance of VRPTW, many algorithms have been proposed to address it, these algorithms can be classified into exact (exhaustive), heuristic and meta-heuristic algorithms. But, in one hand, none of these algorithms have succeeded in working efficiently in all instances of the problem. Consequently, more efficient algorithm that can significantly work well to improve the quality of obtained solution is highly required. In other hand, Quantum Genetic algorithm (QGA) has been presented as a powerful method to handle many real difficult problems and it has not been applied to the VRPTW. This thesis aims to investigate the performance of Quantum Genetic Algorithm (QGA) and enhance its ability in tackling the VRPTW via conducting several modifications. These modifications are concerned with QGA designing and hybridization. QGA is a product of the combination of quantum computation and genetic algorithms. The obtained results show that the behavior of QGA during the search that at the early periods of the search process, succeeds in tackling the VRPTW via enhancing the solution quality. However, the QGA capability of enhancing the solution quality decreases gradually. That’s mean the QGA stuck in local optima. This problem often occurred because of the QGA is effective in exploration but not in exploitation. In order to improve the QGA exploitation process and the quality of generated solution, a hybrid QGA (HQGA) is proposed. In this hybridization a single-based meta-heuristic Hill-Climbing (HC) II was 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, this is due to the fact that the hybrid QGA integrates the abilities of HC exploitation and the standard QGA exploration.