摘 要

随着信息网络技术和虚拟购物的快速发展，物流客户的数量呈爆炸式增长，物流企业也发展的很快，而物流系统中非常重要的一部分是运输配送。配送就是将货物从配送中心送到客户的手中，它被称为“最后一公里物流”。配送车辆路径安排的好不但能提高客户对服务的满意度，同时也能降低运输成本。车辆路径问题（Vehicle Routing Problem,VRP）属于物流配送中首先要解决的问题。VRP是著名的NP问题，很难被完美的解决，但是因为在社会的很多方面都有应用，而且解决VRP问题具有重大的经济价值和理论价值，所以还是有许多专家在研究它。

本论文主要针对车辆配送路径问题来进行研究，先分析了车辆配送路径问题的研究背景和研究目的意义以及国内外对车辆配送路径问题和差分进化算法的研究现状。接着是对VRP的分析，介绍了车辆配送路径问题一般概述、要素、分类和一般解决方法这四个方面。然后对差分进化算法进行研究，主要从原理、操作步骤和改进方法三个方面来进行分析。最后是利用有能力约束车辆路径问题（只有容量限制）的数学模型，提出了基于差分进化算法的解决方案，通过实数编码中简单可行的序号编码，采用了贪婪算法初始化种群，变异则是直接采用相位加减的方法进行变异，得到的编码进行取整，再对变异过程后出现的不合法编码进行合法化操作，使用二项式交叉策略，最后按照保优思想选择适应度值更高的个体。在实际的案例分析中，使用本文所得的解决算法比原案例中基本差分进化算法的解决方案更优越，目标函数值小于基本差分进化算法所得的函数值。

关键字：差分进化算法 车辆路径问题 贪婪算法 边界修复操作

Abstract

With the development of information technology and electronic commerce, the number of logistics customers exploding, logistics enterprises are developing rapidly, and transportation play a very important part in the logistics system. The distribution goods is from the logistics center to customer goods delivered to the hands of customers, known as “the last one kilometer Logistics” . Good vehicle routing can not only improve the customer satisfaction of service, but also can reduce the transportation cost. The vehicle routing problem (VRP) is the first to solve the logistics problem in.VRP is the famous NP problem, it is difficult to Perfect solution, but because there are many aspects of the application, and solve the problem of VRP has great economic value and theoretical value, so there are still many experts in the study of it

This thesis focuses on the vehicle routing problem, firstly analyzes the research background and purpose and significance of the study at home and abroad as well as the vehicle routing problem and the differential evolution algorithm of vehicle routing problem.Then the research of VRP, analyzes the vehicle routing problem with general overview, elements, classification and general solutions of these three aspects. Then the differential evolution algorithm is analyzed, the main principle from three aspects, the operation steps and improvement methods to carry on the analysis. Finally, there is the use of mathematical model for capacity constrained vehicle routing problem, put forward the difference solution algorithm based on real number encoding by simple The serial number for encoding, using the greedy algorithm to initialize the population, the variation is directly using the modified method of phase variation, the encoding rounding, then the legalization of illegal operation of encoding variation occurs after the process, using the binomial crossover strategy, according to the idea of preserving good choice fitness higher in individuals. Actual case analysis, using this algorithm to solve the case than the original basic difference solution algorithm is more superior, the objective function value is less than the basic difference function algorithm the value.

Key words: differential evolution algorithm vehicle routing problem greedy algorithm boundary repair operation

目 录

第1章 绪论 1

1.1研究的意义和背景 1

1.1.1背景 1

1.1.2目的与意义 1

1.2国内外研究状况 2

1.2.1车辆路径优化问题国内外研究现状 2

1.2.2差分进化算法国内外研究现状 2

1.3研究内容和研究方法 3

1.3.1研究内容 3

1.3.2采用的技术方案 3

1.3.3研究的重点和难点 3

第2章 车辆路径问题的方法研究 5

2.1车辆路径问题基本概念 5

2.1.1车辆路径问题描述 5

2.1.2车辆路径问题构成要素 5

2.2车辆路径问题的分类 5

2.2.1基本模型 6

2.2.2衍生模型 6

2.3车辆路径问题的典型算法 7

2.4选择差分进化算法的理由 8

2.5本章小结 8

第3章 差分进化算法及其改进 9

3.1 差分进化算法基本概念 9

3.2差分进化基本操作及优缺点 9

3.2差分进化算法的改进 10

3.2.1种群结构改进 10

3.2.2操作算子改进 11

3.2.3与其他算法融合 11

3.3本章小结 11

第4章 车辆路径问题的改进差分进化算法设计 12

4.1标准差分进化算法的实施流程 12

4.2 改进差分进化算法的主要操作步骤 12

4.2.1 模型编码方案 13

4.2.2 贪婪种群初始化 13

4.2.3 差分变异操作和边界修复操作 13

4.2.4 交叉操作 14

4.2.5 选择操作 14

4.2.6 Matlab编程 14

4.3本章小结 14

第5章研究成果案例验证 16

5.1建立CVRP的数学模型 16

5.2实例分析 17

5.3本章小结 22

第6章总结与展望 23

6.1全文总结 23

6.2研究展望 23

参考文献 25

附录1 26

致谢 35

第1章 绪论

1.1 研究的意义和背景

1.1.1 背景

中国物流行业经过四个阶段：2012年前的起步阶段那时市场从政府垄断到开发阶段，竞争激烈度低。2013年的积累阶段市场变得更加分散竞争开始加剧。2015年的集中阶段物流行业整合，市场集合度增加再到如今的联盟阶段，大竞争者间开始联盟。物流行业也改善了最初的“散，乱，差，小”等问题，但是相比发达国家物流成本只占GDP的9%左右，我国的物流成本还是一直保持在一个较高的状态，这表明我国的物流水平仍处于较低的水平。对中国这个大国来说，降低1%的物流成本在GDP占比相当于减少了4000多亿的资源耗费。因此我们可以使用提高物流管理水平、科学化现代化物流系统等手段来降低物流总成本，这样可以增加企业的收益，改善国民经济，提高国家竞争力。因此国家也多次在发展战略上提到要“大力建设现代物流业”。

我国物流行业近几年的盈利点主要靠的是人工成本的低价和规模经济，随着人力成本的提升，像许多物流企业都受到了不小的影响。物流企业要降低物流成本，提高盈利水平不能仅仅通过削减物流从业人员的工资这一方面，还可以优化物流系统，提高物流效率，包括提高顾客满意度和降低物流过程中的损耗。在物流系统优化的各个环节中，非常重要的一个环节就是运输，因为物流总成本的百分之六十是运输过程中产生的。

1.1.2 目的与意义

车辆路径优化问题能通过有许多算法来解决，如差分进化算法，遗传算法等等。差分进化算法（different evolution，DE）作为一种更简单、所需调节的参数较少、易于理解和实现的随机实参数优化算法，它比较擅长解决全局最优化、多目标优化和复杂函数优化方面的问题，而且与遗传算法相比差别就是基于差分的简单变异（通过父代向量之间的差来探索目标函数）和一对一的保优选择操作，这样就降低了遗传算法的操作难度。而且差分进化算法凭借它记忆个体最优解的能力能够利用个体的局部信息和全局的信息来改进搜索方法，具有很强的收敛性和鲁棒性，且对问题的特征信息没有需求，能够用来解决那些较为复杂约束条件较多的优化问题。