# 带容量约束车辆路径问题的一个新遗传算法A New Genetic Algorithm for the Capacity Constraints Vehicle Routing Problem

DOI: 10.12677/AAM.2014.34032, PDF, HTML, 下载: 2,844  浏览: 7,932  国家自然科学基金支持

Abstract: In this paper, a capacitated vehicle routing problem is studied, in which a distribution center and multiple customers are involved, and the optimization objective is to minimize the distance. For this kind of problem, a genetic algorithm based on a local search scheme is proposed. First, a crossover operator is investigated by the sum of parents. The crossover operator is different from most of traditional crossover procedures in that it can generate new offspring when parents are same, thus maintaining the diversity of population. In addition, in order to efficiently improve the offspring individuals in the iteration process, a local search scheme based on probability selection is presented. The simulation results show that the proposed algorithm is efficient.

 [1] Dantzig, G. and Ramser, J. (1959) The truck dispatching problem. Management Science, 13, 80-91. [2] Banos, R., Ortega, J., Gil, C., Fernandez, A. and Toro, F.D. (2013) A Simulated Annealing-based parallel multi-objec- tive approach to vehicle routing problems with time windows. Expert Systems with Application, 4, 1696-1707. [3] 潘立军, 符卓 (2004) 求解带时间窗车辆路径问题的插入检测法. 系统工程理论与实践, 2, 319-322. [4] 张涛, 余绰亚, 刘岚, 等 (2011) 同时送取货的随机旅行时间车辆路径问题方法. 系统工程理论与实践, 10, 1912-1920. [5] Lenstra, J.K. and Rinnooy Kan, A.H.G. (1981) Complexity of vehicle routing and scheduling problem. Networks, 2, 221-227. [6] Savelsbergh, M.W.P. (1985) Local search in routing problems with time windows. Operations Research, 33, 285-305. [7] Solomon, M.M. (1985) On the worst-case performance of some heuristics for the vehicle routing and scheduling problem with time window constraints. Networks, 1, 285-305. [8] Almoustafa, S., Hanafi, S. and Mladenovic, N. (2013) New exact method for large asymmetric distance-constrained vehicle routing problem. European Journal of Operational Research, 40, 386-394. [9] Christofides, N., Mingozzi, A. and Toth, P. (1981) Exact algorithms for the vehicle routing problem, based on spanning tree and shortest path relaxation. Mathematical Programming, 1, 255-282. [10] Keskin, B.B. and Uster, H. (2007) A scater-based heuristic to locate capacitated transshipment points. Computers & Operations Research, 34, 3112-3125. [11] Barkaoui, M. and Gendereau, M. (2013) An adaptive evolutionary approach for real-time vehicle routing and dispatching. Computers & Operations Research, 40, 1766-1776. [12] 谢秉磊 (2003) 随机车辆路径问题研究. 博士论文, 西南交通大学, 成都. [13] Lau, H.C.W. and Chan, T.M. (2010) Application of genetic algorithms to solve the multi-depot vehicle routing problem. IEEE Transactions on Automation Science and Engineering, 2, 383-392. [14] Kytojoki, J., Nuortio, T., Braysy, O. and Gendreau, M. (2007) An efficient variable neighborhood search heuristic for very large scale vehicle routing problems. Computers & Operations Research, 34, 2743- 2757. [15] 屈援, 汪波, 钟石泉 (2007) 单车场多送货点车辆路径问题的改进遗传算法. 计算机工程与应用, 25, 237-243. [16] 张丽萍, 柴跃廷 (2002) 车辆路径问题的改进遗传算法. 系统工程理论与实践, 8, 79-84. [17] 王宇平 (2011) 进化计算的理论和方法. 科学出版社, 北京. [18] 姜昌华, 戴树贵, 胡幼华 (2007) 求解车辆路径问题的混合遗传算法. 计算机集成制造系统, 10, 2047-2053. [19] 李向阳 (2004) 遗传算法求解VRP问题. 计算机工程与设计, 2, 271-276.