Advances in Applied Mathematics
Vol.3 No.04(2014), Article ID:14395,8 pages
DOI:10.12677/AAM.2014.34032

A New Genetic Algorithm for the Capacity Constraints Vehicle Routing Problem

Xiaolu Ma1, Hecheng Li1,2

1Department of Computer, Qinghai Normal University, Xi’ning

2Department of Mathematics, Qinghai Normal University, Xi’ning

Email: mxl13844195073@163.com

Copyright © 2014 by authors and Hans Publishers Inc.

Received: Sep. 8th, 2014; revised: Oct. 10th, 2014; accepted: Oct. 19th, 2014

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.

Keywords:Vehicle Routing Problem, Genetic Algorithm, Local Search

1青海师范大学，计算机学院，西宁

2青海师范大学，数学系，西宁

Email: mxl13844195073@163.com

1. 引言

Lenstra和Rinnooy Kan [5] 证明了几乎所有类型的VRP均为NP-Hard问题。Savelsbergh [6] 和Solomon [7] 指出带时间窗的VRP由于要考虑送货时间，所以比一般的VRP更复杂。车辆路径问题被提出来后，设计高效的求解算法一直是该问题研究的重点和难点。车辆路径问题的传统算法大致分为两大类：精确法和近似法。精确法指可以求出其精确最优解的算法，包括分支定界法(Branch and Bound, BB) [8] 、动态规划法(Dynamic Programming Method, DP) [9] 等；近似法包括分散搜索算法(Scatter Search, SS) [10] 、遗传算法(Genetic Algorithm, GA) [11] 等。由于该问题是NP难问题，因此，对于规模较大的情形，分支定界法、动态规划法等精确算法一般无法在指定时间内给出全局最优解，而近似法虽然无法保证给出精确的全局最优解，但能在指定时间内获得一个满意解或近似解。基于群体搜索的最优化算法，在求解复杂优化问题时，能有效跳出局部最优解，有较强的全局搜索能力。近年来，以遗传算法为代表的智能优化算法已成为求解该类复杂组合优化问题的有效算法之一。

2. CVRP的数学模型

(1)

(2)

(3)

(4)

(5)

(6)

(7)

.

3. 算法设计

3.1. 个体编码

3.2. 解码方式

3.3. 初始种群

3.4. 适应度函数

3.5. 交叉算子

1) 部分匹配杂交按如下方式进行：随机选两个交叉点，介于之间的位置称为匹配区，列出匹配区内两个个体基因的对应关系。交换匹配区的元素，并按照匹配区内的对应关系换掉匹配区外的重复位，得两个后代个体。如，为两个父代个体

2) 循环杂交算子按如下方式杂交：子代中的第一位取父代个体1的第1位。设子代中的第位已经确定，在父代个体1中找出与父代个体2的第位相同的数，并复制到子代的相应位置。如此反复直到产生出子代，或产生一个循环。若产生一个循环，则找出父代2中与子代中已产生的数不同的数，并按父代2中的顺序填入到子代的剩余位置。如：父代个体为：

(出现循环)

3.6. 变异算子

3.7. 局部搜索

1) 在给定的配送方案(个体)中，任选两辆车，车辆和车辆。对车辆中的任意两个元素置换一次,得到一个新个体；对车辆中的任意两个数置换一次，得到另一个新个体。

2) 新个体选择：若两个新个体均使行车距离缩短，则以较大概率选择缩小幅度大的个体。令缩小幅度分别为：，则选择概率分别为：；若行车距离均增加或一增一减，则选择概率按如下标准给出：第一种情况中增加幅度小的和第二种情况中行车距离减小的，取大概率，对应另一个的选择概率取。按赌轮选择选出个体。

3) 个体改进：对(2)中选出个体对应的车辆路径全排列，找出最好的一个，得到一个不差于原个体的配送方案。

4. 设计的遗传算法

5. 仿真计算及分析

Table 1. Customer’s distance and demand

Figure 1. The result of Algorithm optimization

Table 2. Comparison of the calculation results of GA/LASS and GA

Table 3. Comparison of the function value of assessment number

Table 4. The statistical result

6. 结束语

1. [1]   Dantzig, G. and Ramser, J. (1959) The truck dispatching problem. Management Science, 13, 80-91.

2. [2]   Banos, R., Ortega, J., Gil, C., Fernandez, A. and Toro, F.D. (2013) A Simulated Annealing-based parallel multi-objective approach to vehicle routing problems with time windows. Expert Systems with Application, 4, 1696-1707.

3. [3]   潘立军, 符卓 (2004) 求解带时间窗车辆路径问题的插入检测法. 系统工程理论与实践, 2, 319-322.

4. [4]   张涛, 余绰亚, 刘岚, 等 (2011) 同时送取货的随机旅行时间车辆路径问题方法. 系统工程理论与实践, 10, 1912-1920.

5. [5]   Lenstra, J.K. and Rinnooy Kan, A.H.G. (1981) Complexity of vehicle routing and scheduling problem. Networks, 2, 221-227.

6. [6]   Savelsbergh, M.W.P. (1985) Local search in routing problems with time windows. Operations Research, 33, 285-305.

7. [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. [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. [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. [10]   Keskin, B.B. and Uster, H. (2007) A scater-based heuristic to locate capacitated transshipment points. Computers & Operations Research, 34, 3112-3125.

11. [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. [12]   谢秉磊 (2003) 随机车辆路径问题研究. 博士论文, 西南交通大学, 成都.

13. [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. [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. [15]   屈援, 汪波, 钟石泉 (2007) 单车场多送货点车辆路径问题的改进遗传算法. 计算机工程与应用, 25, 237-243.

16. [16]   张丽萍, 柴跃廷 (2002) 车辆路径问题的改进遗传算法. 系统工程理论与实践, 8, 79-84.

17. [17]   王宇平 (2011) 进化计算的理论和方法. 科学出版社, 北京.

18. [18]   姜昌华, 戴树贵, 胡幼华 (2007) 求解车辆路径问题的混合遗传算法. 计算机集成制造系统, 10, 2047-2053.

19. [19]   李向阳 (2004) 遗传算法求解VRP问题. 计算机工程与设计, 2, 271-276.