摘 要

在近些年，中国电子商务蓬勃发展，与此同时中国电子商务工作中最为核心的环节——物流配送服务也越来越受到人们的关注。其中，物流配送路径的合理规划是提高物流配送效率和收益的关键因素，这对于物流行业的发展有着重要的影响。本系统针对考虑车辆开销、车辆载重限制以及车辆满载率的多配送点多车辆物流配送路径规划问题，依据蚁群算法来实现系统。论文的主要工作如下：

（1）利用两阶段启发式算法，先对配送点按车辆载重量进行分组，再对车辆配送路径进行规划；

（2）利用蚁群算法，在对信息素的更新处理过程中加入了对配送车辆总开销和车辆满载率之和的倒数两个要素进行加权处理得到目标权重；为了克服蚁群算法存在的容易陷入局部最优的缺点，在蚂蚁任务分配时采用信息素最高的分配策略和随机分配策略相结合的方法，来达到尽快获得全局最优解的目的；

（3）基于上述算法，实现了基于蚁群算法的多车种车辆最优化路径的配送路线系统，在考虑配送中心已有的配送车辆，他们各自的油耗开销以及载重等约束条件的情况下，实现提高车辆满载率和减少车辆总开销的目标。

关键词：蚁群算法；配送路径优化；多车种配送路径规划

Abstract

In recent years, Chinese e-commerce has been booming. At the same time, Chinese e-commerce work is the most core link - logistics and distribution services are getting more and more attention. Among them, the rational planning of logistics distribution path is the key factor to improve the efficiency and profitability of logistics distribution, which has an important impact on the development of logistics industry. This system is based on the ant colony algorithm to realize the multi-vehicle logistics distribution route planning of multi-distribution points considering the vehicle cost, vehicle load limit and vehicle full load rate. The main work of this paper is as follows:

(1) By using the two-stage heuristic algorithm, the distribution points are first grouped according to the vehicle load, and then the vehicle distribution path is planned.

(2) Using the ant colony algorithm, the target weight is obtained by weighting the weighting of the two elements of the total cost of the distribution vehicle and the sum of the vehicle's full load rate, and in order to overcome the disadvantage struck by the ant colony algorithm, the method of combining the most common allocation strategy and random allocation strategy in the assignment of ant task is used to achieve the goal of obtaining the global optimal solution as soon as possible.

(3) Based on the above algorithm, the distribution route system of the optimal route of multi-vehicle vehicles based on the ant colony algorithm is realized, and the goal of increasing vehicle load rate and reducing total vehicle overhead is realized in the light of the distribution vehicles already in the distribution center, their respective fuel consumption overhead and load constraints.

Key words: Ant colony algorithm; optimized distribution path; multi-vehicle distribution path planning

目 录

1 绪论 1

1.1课题研究背景 1

1.2 设计目的及意义 1

1.3 国内外研究现状 2

1.4课题研究内容 3

1.5预期目标 4

1.6本文组织结构 4

2基于蚁群算法的多车种车辆配送路径问题 5

2.1问题描述和假设条件 5

2.2配送模型的建立 6

2.2.1参数及变量 6

2.2.2配送总开销 6

2.2.3配送车辆满载率 6

2.2.4设定权值 7

2.3本章小结 7

3系统算法的实现 8

3.1基本蚁群算法 8

3.2基于蚁群算法的系统规划 9

3.2.1系统工作流程 9

3.2.2初始化信息 10

3.2.3迭代搜索过程 10

3.2.4规划配送点配送顺序方法 13

3.2.5信息素更新策略 15

3.3本章小结 18

4基于最优化路径的配送路线原型系统实现和测试 19

4.1系统实现功能 19

4.2系统路径规划功能 23

4.3测试环境 25

4.3.1实现的环境 25

4.3.2配送点数据集 25

4.3.3配送车辆及车辆相关信息集合 26

4.4测试结果 27

4.4.1测试用例1 27

4.4.2测试用例2 28

5总结展望 29

5.1总结 29

5.2展望 29

参考文献 30

致谢 32

1 绪论

1.1 课题研究背景

物流配送是一种现代的商品流通模式。目前，物流配送的目标是为各大电商平台的用户提供服务。随着电子商务的高速发展，物流仓储配送已经转变为我国电商工作中最核心的部分。可靠的仓库存储安排和物流配送方案也成为了很多个体经营户、线上综合购物平台以及各大品牌商高度关注的问题。由供应链服务商开发的物流仓储全网络配送系统已成为电子商务中最受欢迎的系统。其中最为重要的是它能够为不同需求的企业卖家提供不同约束条件下的最优仓储物流配送解决方案，比如提供最小成本的物流配送方案、最短配送时间的物流配送方案等等。

车辆路径问题（Vehicle Routing Problem ,VRP）于1959年被George Dantzig在解决汽油运输问题时提出。可以将这一问题定义为：存在有不同需求的配送点集合，配送中心向各配送点分配货物，配送车辆负责配送工作。在规划好合适的配送路径后，希望使得所有配送点的需求得到满足的同时，能够在约束条件下（如车辆容量限制、送货时间等），实现其他目标（如路程短、成本低等）。

1.2 设计目的及意义

随着移动宽带的不断普及、手机支付的崛起以及国家政策对电商的鼓励和指引，电子商务平台越来越受欢迎。越来越多的产品能够通过电商平台进行购买，大到3C产品、家电、传统家具、美妆个护，小到食品生鲜、零食干果等等。在电商供应链环节日益完善的同时，作为电商发展根本的基础服务更需要进一步优化，例如配送时间、配送范围以及客户支付方式等等。越来越成熟的基础服务也有助于电子购物平台吸引更多地区和年龄层的潜在客户。

物流企业要按照物流规律，采用管理学的知识和方法，对物流工作进行规划，从而实现物流活动最优协调配合的目标，提高整体效率和经济效益。优化路线是整个物流活动优化的核心。合理规划配送路径对配送总成本的影响要远大于其他因素造成的影响，因此物流企业应选择合适的配送车辆，规划高效低耗的运输路径。合理规划配送路径的目标通常是使得配送开销尽可能小，配送车辆以尽可能高的车辆满载率和尽可能短的时间把货物运送至配送点。

1.3 国内外研究现状

车辆路径问题自被提出以来，因其应用的广泛性和经济价值，各国学者一直对它进行深入的学习和研究。在几十年的研究中，车辆路径问题的解决方法主要分为两种，一种是精确算法，另一种是启发式算法。其中，精确算法有分支界限算法、分支切割算法、集合涵盖算法等；启发式算法有节约算法、模拟退火算法、确定性算法、禁忌搜寻算法、基因算法、神经网络算法、蚁群算法等。