摘 要

配送是物流结构中必不可少的一环，近几年在电子商务蓬勃发展的刺激与促进下，物流业不断发展，物流配送的作用也随之更加明显。目前，配送活动中的车辆路径规划问题的研究主要集中于单向的配送业务或集货业务，本文研究的是允许在顾客需求点同时进行集货与配货作业，配送车辆仅需服务顾客一次，就能满足顾客配货和集货需求的集配货一体化模式下的车辆路径规划问题，以充分减少车辆的运输距离，降低车辆空载率，进而减少运输成本，节约运输时间，提高顾客服务水平与企业经济效益。

本文首先阐明了研究背景及研究意义，分析并总结集配货一体化VRP问题的主要研究内容及研究思路；进而结合实际情况，综合考虑配送车辆的固定成本和可变成本的前提下，加入了软时间窗成本和服务成本等因素，以配送总成本最小为优化目标，构建集配货一体化的车辆路径优化模型；然后对常用的四种启发式算法进行分析对比，最终选用遗传算法解决本文模型，并基于数学模型合理地改进传统的遗传算法以提高算法可行性及计算效率，并求得最优解或逼近最优解；接着利用MATLAB编程，选取权威数据进行算例分析，证明算法的可行性；最后，利用相同的方法及数据，计算集配货分开情况下的车辆路径规划问题，将集货与配货情况下的结果之和与集配货一体化情况下的结果对比分析，结果证明在集配货一体化的前提下优化车辆路径能大幅度减少配送成本。

关键词：集配货一体化；物流配送；车辆路径规划；遗传算法

Abstract

Distribution is a necessary part of the logistics structure. In recent years, under the stimulation and promotion of the vigorous development of electronic commerce, the logistics industry develops continuously, and the role of logistics distribution is more obvious. At present, the study of vehicle routing problem in former research mainly focuses on unidirectional logistics distribution or collection. In this paper, in order to fully reduce the transportation distance and the empty loading rate, then save the transportation cost and transportation time which is helpful to improve the level of customer service and enhance profits for enterprises, we study the vehicle routing problem in the situation where customers are allowed to delivery and pick up goods at the time, and one customer demand of distribution and collection can be met by one car at only one time.

In this paper, we first illustrate the research background and research significance, then analyze and summarize the main research content and idea. According to the practical situation, under the premise of considering the variable cost and fixed cost of distribution vehicles, we add soft time window and service cost. And we see the minimum total distribution cost as our optimization target to construct the mathematical model of vehicle routing problem with pick-up and delivery. Then analyzing and comparing the commonly used four heuristic algorithms, we finally choose genetic algorithm to solve the mathematical model in this paper. In order to enhance the feasibility and efficiency of this algorithm and get the optimal solution or near-optimal solution, we make some reasonable improvements to the general genetic algorithm based on the mathematical model above. Next, we program in MATLAB, select authoritative data to prove the feasibility of the algorithm. Finally, using the same method and data, we compute the vehicle routing problems where the distribution and collection are separate, and compare the two results above to prove indeed that on the premise of pick-up and delivery at the same time, optimizing vehicle routing can significantly reduce distribution costs.

Keywords: pick-up and delivery; logistics distribution; vehicle routing problem; genetic algorithm

目录

第1章 绪论 1

1.1研究背景及意义 1

1.2国内外相关文献综述 2

1.2.1 对车辆路径问题的研究 2

1.2.2 对集配货一体化的车辆路径问题研究 3

1.3研究内容及研究思路 4

1.3.1研究目标 4

1.3.2研究内容 4

1.3.3研究重难点 4

1.3.4拟采用的技术方案及措施 4

1.4论文内容组织 5

第2章 配货与集货一体化的VRP数学模型构建 7

2.1问题描述 7

2.2模型假设 7

2.3模型优化目标 8

2.3.1模型优化目标选择 8

2.3.2模型目标函数 8

2.4模型构建 9

2.5本章小结 11

第3章 集配货一体化VRP问题的遗传算法求解与实现 12

3.1集配货一体化VRP问题的求解算法选择 12

3.2集配货一体化VRP问题的遗传算法编程 13

3.2.1遗传算法简述 13

3.2.2遗传算法的改进与实现 14

3.3本章小结 19

第4章 算例分析 20

4.1 算例概述 20

4.2参数设定 20

4.2.1模型参数设定 21

4.2.2算法参数设定 21

4.3改进遗传算法源程序 22

4.4结果分析 27

4.4.1算例结果分析 27

4.4.2对比分析 29

4.5本章小结 30

第5章 总结与展望 31

5.1总结 31

5.2展望 32

参考文献 33

附录 34

致谢 40

第1章 绪论

1.1研究背景及意义

随着物流业在我国逐渐发展壮大以及物流专业化水平的逐渐提高，物流业在社会发展中的地位逐渐提高。现代物流是经济全球化的产物之一，同时也极大地推进了经济全球化。如今，全球物流业呈现出平稳增长的趋势，特别是欧美地区，已发展为当今全球首要的物流基地。虽然我国物流业起步较晚，但随着国民经济快速发展，我国物流业的增长速度较为稳定，物流体系也在逐渐完善。配送是现代物流的重要组成部分，指的是为满足顾客需求，对货物进行拣选、加工、分类及装配等工作，最后及时运至目的地的一系列活动。部分配送企业在研发物流信息系统和配送管理方法等方面硕果累累，极大地促进了我国物流业的发展。

实际上物流业有两大基本目标：降低总成本和满足顾客需求，即要在及时有效地满足顾客需求的前提下控制成本。那么，由配送的定义可以看出，有效的物流配送体系希望基于最短距离、最少时间及最低成本的目标，合理安排配送路径，以及时满足身处各地的顾客需求。因此，配送车辆路径规划问题是配送优化中的一个关键环节，对于企业提升顾客满意度，降低总成本，增加经济效益有积极作用。而目前，我国大部分配送中心还在用人工分配的方法安排配送路径，仅仅根据配送人员对目的地的了解，随意选择路径，人为主观性太大，因此，配送路径的选择往往具有较大盲目性^[1]。但面对越来越多的顾客与相应的各种需求，客观约束条件繁多，人工分配的方法要在一定时间内规划出合适的路径确实很难，甚至不可能用枚举法在可被允许的时间内得到最优解或者逼近最优解。因此配送车辆路径规划问题是一个公认的物流难题，对配送企业来说，也急需一种高效简便的车辆配送路径规划方法。

目前，配送活动中的车辆路径规划问题的研究方向主要偏向于单向的配送业务或集货业务，每个配送单位或集货单位只分配给单个顾客，即仓库——单个顾客——仓库模式，即使允许配送车辆集货，也必须等所有的配送工作结束再返程开始集货，这种模式下的回程车辆便会造成时间和成本上的浪费，非常不合理。针对上述情况，本文研究的是考虑某个顾客同时存在集货与配货需求，允许配送车辆同时开展集货与配货业务，即每辆车仅服务顾客一次，就能同时满足顾客集货和配货需求，这种模式被称为集配货一体化的车辆路径规划问题（VRP with pick-up and delivering，VRPPD）。随着现代物流的不断发展，一方面，越来越多的客户同时拥有送货与收货需求；另一方面，随着客户量的增大，物流企业的配送和收货业务都不断增大^[2]。因此，集配货一体化将成为现代配送活动的发展方向，集配货一体化的车辆路径问题成为提高回程车辆空闲容量，降低成本和减少浪费的重要问题。对企业来说，合理规划配送路径，能充分缩短配送距离，降低车辆空载率，进而缩短运输时间，降低企业配送成本，提升顾客满意度，保持优秀的企业形象，最终提高企业经济效益。另外，相对于众多研究车辆路径规划问题的文献，研究配送和集货同时发生模型的文献较少，可见VRPPD问题较为复杂并具有一定的理论价值和现实意义^[3]。