Abstract
The evolutionary algorithms are extensively adopted to resolve complex optimization problem. Genetic algorithm (GA), an evolutionary algorithm, has been proved capable of solving vehicle routing problems (VRPs). However, the resolution effectiveness of GA decreases with the increase of nodes within VRPs. Normally, a hybrid GA outperforms pure GA. This study attempts to solve a capacitated vehicle routing problem (CVRP) by applying a novel hybrid genetic algorithm (HGA) that is practical for use by manufacturers. The proposed HGA involves three stages. First, a diverse and well-structured initial chromosome population was constructed. Second, response surface methodology (RSM) experiments were conducted to optimize the crossover and mutation probabilities in performing GA. Finally, a combined heuristics containing improved insertion algorithm and random insertion mutation operator was established to stir over gene permutations and enhance the exploration capability of GA diversely. Furthermore, an elitism conservation strategy was implemented that replace inferior chromosomes with superior ones. As the proposed HGA is primarily used to solve practical problems, benchmark problems involving fewer than 100 nodes from an Internet website were utilized to confirm the feasibility of the proposed HGA. Two real cases one for locally active distribution and another for arms part transportation at a combined maintenance facility, both involving the Taiwanese armed forces are used to detail the analytical process and demonstrate the practicability of the proposed HGA for optimizing the CVRP.
Similar content being viewed by others
References
Angelov P. (2001) Supplementary crossover operator for genetic algorithms based on the center-of-gravity paradigm. Control Cybern 30: 159–176
Baker B.M., Ayechew M.A. (2003) A genetic algorithm for the vehicle routing problem. Computers & Operations Research 30: 787–800. doi:10.1016/S0305-0548(02)00051-5
Battiti R., Tecchiolli G. (1994) The reactive tabu search. ORSA Journal on Computing 6: 126–140
Bentley J.J. (1992) Fast algorithms for geometric traveling salesman problem. ORSA Journal on Computing 4: 387–411
Bodin L., Bruce G. (1981) Classification in vehicle routing and scheduling. Networks 11: 97–108. doi:10.1002/net.3230110204
Chen J.S., Pan J.C.H., Lin C.M. (2008) A hybrid genetic algorithm for the re-entrant flow-shop scheduling problem. Expert Systems with Applications 34: 570–577. doi:10.1016/j.eswa.2006.09.021
Cheng R., Gen M., Tsujimura Y. (1999) A tutorial survey of job-shop scheduling problems using genetic algorithms, Part II: Hybrid genetic search strategies. Computers & Industrial Engineering 36: 343–364. doi:10.1016/S0360-8352(99)00136-9
Gillett B.E., Miller L.R. (1974) A heuristic algorithm for the vehicle-dispatch problem. Operations Research 22: 340–349
Goldberg D.E. (1989) Genetic algorithms in search, optimization and machine learning. Addison-Wesley, Boston, MA
Grefenstette J. (1986) Optimization of control parameters for genetic algorithms. IEEE Transactions on Systems, Man, and Cybernetics 16: 122–128. doi:10.1109/TSMC.1986.289288
Montgomery D.C. (2005) Design and analysis of experiments (6th ed). Wiley, New York
Prins C. (2004) A simple and effective evolutionary algorithm for the vehicle routing problem. Computers & Operations Research 31: 1985–2002. doi:10.1016/S0305-0548(03)00158-8
Schaffer, J. D., Caruana, R. A., Eshelman, L. J., & Das, R. (1989). A study of control parameters affecting online performance of genetic algorithms for function optimization. In: Proceedings of the Third International Conference on Genetic algorithms, pp. 51–60.
Shieh H.M., May M.D. (2001) Solving the capacitated clustering problem with genetic algorithms. Journal of the Chinese Institute of Industrial Engineers 18: 1–12
Toth, P., & Vigo, D. (2002). The vehicle routing problem, Society for industrial and applied mathematics. Philadelphia.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Wang, CH., Lu, JZ. An effective evolutionary algorithm for the practical capacitated vehicle routing problems. J Intell Manuf 21, 363–375 (2010). https://doi.org/10.1007/s10845-008-0185-2
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10845-008-0185-2