摘 要

怎样高效地解决“最后一公里”的配送难题，是当今社会的研究热门之一。利用无人车来完成末端配送是其中的一个解决方案。本文针对无人车末端配送中遇到的特定情境，开展多点配送的路径规划选择。

本文基于特定的区域设定配送点以及配送中心，构建时间和距离加权（侧重于时间）的问题模型，并加入容积约束，使之更符合实际的配送问题。通过百度地图搜索和实地考察收集数据，综合考虑小车的运行速度，路况等因素实现对时间权重的求解。

本文改进A*算法，使之能够完成对基本多点配送问题的求解。在加入容积约束后，其可行解会形成多个回路，对改进的A*算法进行处理，结合贪心算法编程实现对容积限定的多点配送问题的求解

本文针对于多点配送问题，提出用遗传算法求解所需要的编码方式，改进适应度函数，选取合适的遗传操作方式（部分匹配交叉、贪心对换变异、轮盘赌选择），在加入容积约束后，利用求解多车配送问题的思想改进编码方式，并改进选择算子（淘汰劣质个体），加快算法的收敛速度。

本文利用matlab编程实现两种算法，并将求解结果进行对比分析。结论：针对本文所提出的问题模型求解，用遗传算法求解会比用A*算法求解更有优势，会得到更优的路径，但如果加入实时反馈用来调整路径选择，需要着重考虑算法的快速响应，那么利用A*算法这样的启发式搜索会更好一些。

关键字：多点配送；无人小车；A*算法；遗传算法

Abstract

How to efficiently solve the "last mile" distribution problem is one of the hot topics in today's society. The use of unmanned vehicles to complete the delivery of the end is one of the solutions. Based on the specific situations encountered in the terminal delivery of unmanned vehicles, this paper carries out path planning choices for multi-point distribution.

This paper sets distribution points and distribution centers based on specific regions, builds time and distance weighted (focus on time) problem models, and adds volume constraints to make them more in line with actual distribution issues. Through Baidu map search and field trips to collect data, comprehensive consideration of the car's operating speed, road conditions and other factors to achieve the solution of the time weight.

This paper improves the A* algorithm so that it can solve the basic multi-point distribution problem. After the volume constraint is added, the feasible solution will form multiple loops. The improved A* algorithm is processed and the volume algorithm is realized by the greedy algorithm programming. Multi-point distribution problem solving

This paper aims at the multi-point distribution problem, proposes to use the genetic algorithm to solve the required coding method, improve the fitness function, select the appropriate genetic operation methods (partial match cross, greedy swap variation, roulette selection), in the volume constraint Afterwards, the idea of solving multi-vehicle delivery problem was used to improve the coding method, and the selection operator was improved (eliminating outdated individuals) to speed up the convergence of the algorithm.

In this paper, the results of the two algorithms are compared and analyzed by matlab programming, and the conclusion is drawn: for solving the problem model proposed in this paper, solving with the genetic algorithm will have more advantages than solving with the A* algorithm and will get a better path. However, if real-time feedback is used to adjust the path selection and the fast response of the algorithm needs to be considered, then heuristic search using A* algorithm will be better.

Key words: multi-point distribution; unmanned dolly; A* algorithm; genetic algorithm

目 录

摘 要 I

Abstract II

第1章 绪论 1

1.1课题的研究背景及意义 1

1.2国内外研究现状 2

1.2.1无人配送车的发展 2

1.2.2多点配送最短路径的研究 3

1.3论文主要研究内容 4

1.4本章小结 5

第2章 多点配送问题路径规划方法研究 6

2.1多点配送问题的描述与分析 6

2.2基于改进A*算法的多点配送路径规划研究 8

2.2.1A*算法介绍 8

2.2.2基于改进A*算法解决多点配送问题的研究 9

2.3基于遗传算法的多点配送路径规划研究 10

2.3.1标准遗传算法介绍 10

2.3.2遗传算法求解多点配送问题 11

2.4本章小结 12

第3章 多点配送问题路径规划的实现 13

3.1基于路径距离的时间权重的研究 13

3.2基于改进A*算法的多点配送路径规划实现 14

3.3基于遗传算法的多点配送路径规划实现 16

3.3.1基因编码与种群的初始化 16

3.3.2适应度函数的选取 17

3.3.3遗传操作的实现 18

3.4本章小结 19

第4章 多点配送问题路径规划结果对比分析 20

4.1容积限定多点配送问题的模型改进 20

4.2容积限定多点配送问题的算法处理 21

4.2.1基于A*算法的处理 21

4.2.2基于遗传算法的处理 22

4.3多点配送问题路径规划结果分析 23

4.4本章小结 27

第5章 经济性分析与环保性分析 28

第6章 总结与展望 29

6.1总结 29

6.2展望 29

参考文献 30

致 谢 32

第1章 绪论

1.1课题的研究背景及意义

在近二十年的时间里，电子商务也越来越普及，网购逐渐的成为人们的日常生活方式。快递物流行业发生了翻天覆地的变化，但大步前进的同时也承担着巨大压力，传统的快递物流模式已经落后，很难满足现在的生产生活需求。随着近年物联网的兴起，信息技术也被逐渐应用到快递行业中去，便催生了“智能物流”的新兴概念。有资料显示，仅去年一年，国内智能物流市场的规模就达到2000亿元，并且预计到2025年可能超过万亿元。智能物流市场发展前景广阔，无人车配送、无人机配送的研究，无人智慧配送站的设立都预示着智能物流时代的到来。亚马逊、京东、唯品会、菜鸟网络等大型企业都在争相布局。比如说，亚马逊斥巨资收购Kiva systems公司的机器人项目，装备Kiva机器人在他们的智能化仓库当中用于拣货处理。对比之前传统的纯人工拣货，在装备Kiva机器人之后，亚马逊智能化仓库中拣货效率提升了两倍，给亚马逊带来了巨大的经济效益；今年3月份，菜鸟ET实验室联合天猫将无人机运用茶叶运输当中。以往利用人工运输茶叶的时候，由于狮驼峰地势的限制，往返一趟可能需要一个小时左右的时间，利用无人机则只需要2分钟。使得狮驼峰的茶叶能够提前两个小时上市，提高了经济效益。

无人配送车也是“智能物流”的一个典型代表。作为短途自主配送机器人，它需要实时动态地进行路径规划，通过各式传感器感知周围地路况信息，避开障碍物，完成配送任务，并且能够达到一定的性能指标，类似时间与距离最短，耗能最小等。路径规划是一个NP难题，很难得到一个最优的解，在对各个目标进行权衡考虑之后，往往最后得到的是一个协调的折中解。针对于路径规划问题的研究现在已经有了一定的成果，但至今也没有一个非常高效的解决方法和理论。