摘 要

物流作为当今社会各种经济活动的载体，在各行业中是很重要的一部分，是当今社会上普遍存在的一种需求，成为了“第三利润源泉”，是社会经济发展中很重要的一个环节。车辆路径问题作为物流行业的核心部分，普遍存在于我们的生活中。研究车辆路径优化问题不仅能解决当今社会上存在的社会问题，如大气污染、能源紧缺等，还能提高配送效率，降低成本，提高经济效益。本文以减少车辆行驶总距离为目标，结合遗传算法研究车辆路径优化问题。本论文的主要内容如下：

本文以物流行业中车辆路径问题为背景，阐述了研究背景、现状及目的意义，说明了车辆路径问题的重要性，并对车辆路径问题概念和分类进行了详细的说明和介绍。然后建立了车辆路径问题的数学模型，并对求解车辆路径问题的算法信息及分类进行了简要的说明。接着，详细地介绍和说明了遗传算法的基本原理和步骤，再根据车辆路径问题的数学模型进行了算法的设计，而且在基本的遗传算法基础上，增加了逆转操作，以增加遗传算法的局部搜索能力，并运用设计好的遗传算法进行算例的计算与结果分析。最后根据结果的分析与比较，通过调整参数设置达到算法优化并使结果优化。

关键词：物流；车辆路径问题；遗传算法；算法优化；参数设置

Abstract

As a carrier of various economic activities in today's society, logistics is a very important part of various industries. It is a demand which is prevalent in today's society and becomes a "third profit source", which is very important in social and economic development. Of a link. Vehicle routing problems as the core of the logistics industry, the prevalence of our lives. The study of vehicle path optimization can not only solve the social problems existing in the society, such as air pollution, energy shortage, but also improve the efficiency of distribution, reduce costs and improve economic efficiency. In this paper, we aim at reducing the total distance of vehicle travel, and combine the genetic algorithm to study vehicle routing optimization. The main contents of this paper are as follows:

Based on the background of vehicle routing in logistics industry, this paper expounds the research background, current situation and purpose significance, and explains the importance of vehicle routing problem. The concept and classification of vehicle routing problem are described and introduced in detail. Then the mathematical model of vehicle routing problem is established, and the algorithm information and classification of vehicle routing problem are briefly described. Then, the basic principle and steps of the genetic algorithm are introduced and explained in detail. Then, the algorithm is designed according to the mathematical model of the vehicle path problem. On the basis of the basic genetic algorithm, the reversal operation is added to increase the local Search ability, and use the designed genetic algorithm to calculate and analyze the results. Finally, according to the results of the analysis and comparison, by adjusting the parameter settings to optimize the algorithm and optimize the results.

Key words: logistics; vehicle routing problem; genetic algorithm; algorithm optimization; parameter setting

目录

第一章 绪论 1

1.1 目的及意义 1

1.2 国内外研究现状 1

1.3 论文主要内容 2

1.3.1 技术方案路线图 2

1.3.2 论文的主要结构 2

第二章 VRP问题建模与求解 4

2.1 VRP问题及分类 4

2.1.1 多配送中心的车辆路径问题 4

2.1.2 带集货送货需求的车辆路径问题 5

2.1.3 动态车辆路径问题 5

2.1.4 带时间窗口约束的车辆路径问题 5

2.1.5 开放式车辆路径问题 6

2.2 车辆路径问题的模型 6

2.3 求解车辆路径问题的算法 7

2.3.1 遗传算法 8

2.3.2 蚁群算法 8

2.3.3 粒子群算法 9

2.3.4 蝙蝠算法 9

2.3.5 模拟退火算法 9

2.4 本章小结 9

第三章 求解车辆路径问题的遗传算法的设计 10

3.1 遗传算法的基本原理 10

3.2 遗传算法的算法设计 10

3.2.1 遗传算法的步骤 10

3.2.2 求解车辆路径问题的遗传算法参数的设置 11

3.3 遗传算法求解车辆路径问题在MATLAB中的实现 12

3.3.1 初始化种群 12

3.3.2 计算个体的适应度值 12

3.3.3 选择操作 12

3.3.4 交叉操作 13

3.3.5 变异操作 13

3.3.6 逆转操作 14

3.4 本章小结 14

第四章 算例计算与分析 15

4.1 算例计算与分析 15

4.1.1 算例data20的计算与分析 15

4.1.2 算例E-n30-k3的计算与分析 17

4.1.3 算例E01603的计算与分析 19

4.1.4 算例P-n22-k8的计算与分析 21

4.2 算法改进及优化 24

4.2.1 改进遗传算法在算例E01603中的改进和运行 25

4.2.2 改进遗传算法在算例P-n22-k8中的改进和运行 27

4.3 本章小结 30

第五章 总结与展望 31

5.1 经济性与环保性分析 31

5.2 总结 31

5.3 展望 32

附录 35

致谢 38

第一章 绪论

1.1 目的及意义

在现今迅速发展的社会，作为“第三利润源泉”的物流行业也随之迅速发展，影响着国内的各个行业。而配送是物流中的综合活动的特殊形式，作用也是显而易见的，也是影响力越来越大，良好的配送系统能推动整个社会经济的发展。因此，配送系统的优化成为了学者的研究对象。配送车的调度室配送的核心部分，优化配送车辆调度即提出合理的车辆路径配送方案，能优化配送系统。企业对车辆行驶路径进行合适的调度，选取合适的配送方案，可以提高配送效率，减少行驶距离和行驶成本，从而降低运输成本，提高服务质量，提高企业的经济效益^[1]。车辆路径问题从现实生活中的交通运输提炼出来,一直都是学者研究的对象，因此求解方法也是层出不穷，不断被提出来，遗传算法作为一种启发式的进化算法,在运算时间上虽然有点长，但是将其运用到车辆路径问题中，还是能较好地解决这一问题，提供更为恰当的解，降低成本，提高企业的服务质量和经济效益。然而，运用遗传算法进行VRP求解时，只能得到一个较优解。遗传算法的局部搜索能力不强，最终获取的解的质量并不是很高^[2]。因此，不断进行优化和改进基于遗传算法的车辆路径问题求解是很有必要的，使得运用遗传算法求出的解更加地合适，成本得到降低，提高运输效率及企业效益。

1.2 国内外研究现状

车辆路径问题是指由配送中心向有不同需求量的一定数量的客户提供货物，使用不同数量的车，按照适当的行车路线提供货物，使客户的需求得到满足的同时，使车行驶的路程最短、成本最小或消耗时间最少^[3]。车辆路径问题的研究最早在1959年提出，近 60 年来始终是学者们的研究热点，不仅受到了国内外研究者的广泛关注，世界各行业更是将目光投入VRP的研究上^[4]。车辆路径问题是一个现实生活交通运输中产生的问题，是生活中经常能碰到的问题，能合理地解决这一问题意味着能够有效地提高运输效率降低成本，关乎实际的利益和服务效率，是急需改进和求解的问题。不少的专家们致力于不同货物的车辆路径优化，如周咏^[5]等人进行了冷链物流同时送取货车辆路径优化；马向国^[3]等人则进行了基于随机需求的冷链物流车辆路径优化模型的研究。在物流领域中，物流配送的路径优化实际上是一个 NP 问题，传统的算法在解决这类问题特别是在配送节点较多的的情况下，求解的结果在满意程度上存在一定的不足^[6],因此很多的专家们则致力于运用不同的算法求解车辆路径问题的研究。遗传算法则是其中一种算法，作为启发式算法，遗传算法是一种较为有效的全局搜索算法，且具有运算简单、收敛速度快可以获得物流配送路径的近似最优解或满意解，但遗传算法的局部搜索能力不强，最终获取的解的质量并不是很高^[6]。因此改进遗传算法设计及参数设置是很有必要的，以求得到更优解，提高运输效率。

1.3 论文主要内容

1.3.1 技术方案路线图

1.3.2 论文的主要结构

研究技术方案路线图1-1，论文的主要结构如下：

1. 介绍车辆路径问题的定义、分类方式，介绍了车辆路径问题的相关数学模型的建立和解决车辆路径问题的相关启发式算法及其优缺点；
2. 介绍了遗传算法的基本原理、步骤流程，实现了解决车辆路径问题的遗传算法设计；
3. 运用设计好的算法计算参考文献和VRP算例库的相关算例，进行结果分析和比较，再通过参数设置调整达到结果优化，降低相关成本；
4. 论述论文在经济性和环保性方面的意义，总结论文工作，展望车辆路径问题和遗传算法的研究未来。

研究背景