A Hybrid Natural Computing Approach for the VRP Problem Based on PSO, GA and Quantum Computation
In this paper, a novel hybrid natural computing approach, called PGQ, combining Particle Swarm Optimization (PSO), Genetic Algorithm (GA) and quantum computation, is introduced to solve the Vehicle Routing Problem (VRP). We propose a quantum approach, cal
- PDF / 208,909 Bytes
- 6 Pages / 439.37 x 666.142 pts Page_size
- 59 Downloads / 175 Views
Abstract In this paper, a novel hybrid natural computing approach, called PGQ, combining Particle Swarm Optimization (PSO), Genetic Algorithm (GA) and quantum computation, is introduced to solve the Vehicle Routing Problem (VRP). We propose a quantum approach, called QUP, to update the particles in PSO. And, we add GA operators to improve population quality. The simulation results show that the PGQ algorithm is very effective, and is better than simple PSO and GA, as well as PSO and GA mixed algorithm. Keywords VRP
PSO GA Quantum computation
1 Introduction The Vehicle Routing Problem (VRP), as known as a hot topic since it was discovered, has many significant applications in economics, logistics and industry engineering. In general, a solution to VRP is a set of tours for several vehicles K. Zeng (&) G. Peng Z. Cai Z. Huang X. Yang Department of Computer Science, Huizhou University, Huizhou 516007, People’s Republic of China e-mail: [email protected] G. Peng e-mail: [email protected] Z. Cai e-mail: [email protected] Z. Huang e-mail: [email protected] X. Yang e-mail: [email protected]
S.-S. Yeo et al. (eds.), Computer Science and its Applications, Lecture Notes in Electrical Engineering 203, DOI: 10.1007/978-94-007-5699-1_3, Ó Springer Science+Business Media Dordrecht 2012
23
24
K. Zeng et al.
from a depot to customers and return to the depot without exceeding the capacity constraints of each vehicle, at the minimum cost. Among the approaches solving the VRP, natural computing based algorithms show standout effectiveness and efficiency, and gradually predominates the trend of solutions for the VRP. Some state-of-the-art algorithms are listed as follows. Yu Bin et al. proposed an improved ant colony optimization for the VRP, which is better than some other meta-heuristic approaches [1]. Humberto César Brandão de Oliveira and Germano Crispim Vasconcelos proposed a hybrid search method associating non-monotonic Simulated Annealing to Hill-Climbing and Random Restart. They compared their algorithm with the best results published in the literature for the 56 Solomon instances, and it was shown how statistical methods can be used to boost the performance of the method [2]. Gong et al. proposed an discrete PSO approach for the VRP with Time Windows (VRPTW), and the simulation results and comparisons illustrated the effectiveness and efficiency of the algorithm by Solomon’s benchmarks testing [3]. Yucenur and Nihan proposed a geometric shape-based genetic clustering algorithm for the multi-depot vehicle routing problem [4] and which is much more effective and timesaving than the nearest neighbor algorithm. Lau et al. proposed a fuzzy logic guided genetic algorithms (FLGA) to solve the VRP with Multiple Depots [5]. The role of fuzzy logic is to dynamically adjust the crossover rate and mutation rate. They compared the algorithm with some benchmarks and which showed that FLGA outperforms other search methods. Christos D. Tarantilis et al. proposed a template-based tuba search algorithm for consisten
Data Loading...
