AAM  >> Vol. 3 No. 4 (November 2014)

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

  • 全文下载: PDF(489KB) HTML    PP.222-230   DOI: 10.12677/AAM.2014.34032  
  • 下载量: 1,071  浏览量: 3,849   国家自然科学基金支持

作者:  

马小璐,李和成:青海师范大学,计算机学院,西宁

关键词:
车辆路径问题遗传算法局部搜索Vehicle Routing Problem Genetic Algorithm Local Search

摘要:

本文研究了一个配送中心多个客户的带容量限制的车辆路径问题,该问题以总距离最短为目标。针对该问题,提出了一个带局部搜索程序的遗传算法。首先,设计了一个基于父代个体求和的杂交算子,该算子的特点是能在父代个体相同的情况下产生不同的后代个体,保持种群的多样性;其次,为了有效改进遗传算法产生的后代个体,引入了一个基于概率选择的局部搜索程序。数值实验表明该算法是有效的。

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.

文章引用:
马小璐, 李和成. 带容量约束车辆路径问题的一个新遗传算法[J]. 应用数学进展, 2014, 3(4): 222-230. http://dx.doi.org/10.12677/AAM.2014.34032

参考文献

[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.