摘 要

在物流行业发展迅速的今天，物流配送作为物流系统中至关重要的环节，是物流配送领域的研究热点，其代表的车辆路径问题（Vehicle Routing Problem，VRP），也是运筹学和组合优化领域的热点问题。与此同时，近年来GIS（Geographic Information System）的发展使物流配送获得了更大的发展空间，使所研究的车辆路径规划问题更加贴近现实情况。

本文总结研究前人在路径规划算法方面的工作，以一种新型高效生物启发式算法-蝙蝠算法（Bat Algorithm，BA）为基础，设计并实现改进的蝙蝠算法，完成以下工作：

（1）提出了改进的蝙蝠算法。根据蝙蝠捕捉猎物时脉冲频率变化特点，提出自适应频率。通过分析蝙蝠算法的仿生原理，从蝙蝠的位置和速度更新公式方面分析了全局发散搜索因子和自身发散搜索因子对蝙蝠寻优的影响，并据此引入基于群体自适应的动态惯性权重和步长控制因子，以平衡蝙蝠算法的全局搜索能力和局部搜索能力。同时，本文将多种群的思想引入算法，改善了蝙蝠算法易陷入局部最优的问题。

（2）针对蝙蝠算法多用于连续优化问题的情况，本文设计了基于车辆参考点的编码和解码方式，将CVRP这一离散组合优化问题转化为了连续优化问题。同时，解码方法中利用了ISP算法对路径进行局部优化，在一定程度上加快了收敛速度，提高了收敛精度。

（3）利用基于GIS的CVRP基准测试数据集将改进的蝙蝠算法与标准蝙蝠算法、萤火虫算法进行横、纵方向的比较。从算法实验结果的收敛速度和最优解来看，改进的蝙蝠算法的寻优效果优于其他两种算法。最后基于GIS可视化物流配送路径规划。

关键词：物流配送；车辆路径规划算法；蝙蝠算法；地理信息系统

Abstract

Nowadays, under the background of logistics industry developing rapidly, logistics and distribution as a vital link in the logistics system, is a research hotspot in the field of logistics and distribution. It’s representative vehicle routing problem (VRP), is also a hot issue in the field of operations research and combinatorial optimization. In the meanwhile, in recent years, the development of GIS (Geographic Information System) has made the logistics distribution more development space, making the research of vehicle routing problem closer to the reality.

This thesis summarizes the work of predecessors in vehicle routing problem algorithms. Based on the Bat Algorithm (BA), a new efficient bio-heuristic algorithm, this thesis designs and implements an improved bat algorithm to, and accomplishes the following tasks:

(1) An improved bat algorithm is proposed. According to the characteristics of the pulse frequency change when the bat captures the prey, the adaptive frequency is proposed. Based on the bionic principle of bat algorithm, the effects of global divergence search factor and self-diverging search factor on bat optimization are analyzed from the aspects of the bat's position and velocity update formula. And accordingly, the dynamic inertia weight based on bat population and the control factor of step size are introduced into the algorithm to balance the global search capability and the local search capability of the bat algorithm. At the same time, this thesis applies the idea of ​​multiple groups to the bat algorithm, which solves the problem that the bat algorithm is easy to fall into local optimum.

(2) In terms of the fact that the bat algorithm is mostly used for continuous optimization problems, this thesis designs a coding and decoding method based on vehicle reference points, and transforms CVRP which is a discrete combination optimization problem into continuous optimization problem. At the same time, the ISP algorithm is used to locally optimize the path in the decoding method, which accelerates the convergence speed and improves the convergence precision to some extent.

(3) GIS-based CVRP benchmark data sets are adopted to compare the improved bat algorithm with the standard bat algorithm and the firefly algorithm respectively. The experimental results show that the improved bat algorithm is better than the other two algorithms in terms of the convergence speed and optimal solution.

Key Words：Logistics Distribution Path; Vehicle Path Planning Algorithm; Bat Algorithm; Geographic Information System

目 录

第1章 绪论 1

1.1 研究背景和意义 1

1.2 国内外研究现状 1

1.3 应用背景介绍 3

1.4 本文研究内容 3

1.5 研究内容组织结构 4

第2章 蝙蝠算法及其改进算法 6

2.1 蝙蝠算法 6

2.1.1 蝙蝠算法的生物学原理 6

2.1.2 标准蝙蝠算法的数学模型 6

2.1.3 标准蝙蝠算法的流程 7

2.2 蝙蝠算法的改进 8

2.2.1 自适应脉冲频率 8

2.2.2 基于群体自适应的动态惯性权重和步长控制因子 9

2.2.3 基于多种群的蝙蝠算法 11

2.2.4 改进蝙蝠算法流程 11

2.3 本章小结 12

第3章 改进的蝙蝠算法求解路径规划问题 13

3.1 CVRP基本概念及数学模型 13

3.2 改进的蝙蝠算法求解CVRP 14

3.2.1 基本求解思想 14

3.2.2 解的编码与解码 14

3.2.3 改进的蝙蝠算法求解CVRP实现步骤 17

3.3 本章小结 18

第4章 基于GIS的改进蝙蝠算法实验对比与分析 19

4.1 实验环境和数据来源 19

4.1.1 实验环境 19

4.1.2 数据来源 19

4.2 基于GIS技术的算法的实现 19

4.3 改进蝙蝠算法对比实验及结果分析 20

4.4 基于GIS的物流规划路径呈现 22

4.5 本章小结 25

第5章 总结与展望 26

5.1全文总结 26

5.2 不足与展望 26

参考文献 28

致 谢 30

第1章 绪论

1.1 研究背景和意义

现代物流业的发展目标是以现代制造业和服务业为基础，以现代运输业为重点，利用现代信息和通信技术来实现物流配送服务的标准化、信息化和智能化^[7]。在网上购物普及全球的今天（比如淘宝、京东、天猫），物流配送环节更为重中之重。最近几年，B2C电商平台正在逐步完善,11月11日和12月12日的购物节相当火爆。在日常消费过程中，无论何时何地，人们都能感受到网上购物带来的便捷和实惠，对网上购物更加信任。因此，在中国网上购物交易规模迅速扩大的背景下，作为电子商务的 “最后一公里”，物流环节需要进一步提升服务质量和水平。如何安全、快速、方便地将所购买的商品发送给消费者，直接影响到消费者对整个物流乃至整个网上购物的满意度^[10]。因此，有必要做好整个物流的调度，提高物流的效率。而物流配送路径规划作为物流配送系统中的关键环节，对物流配送路径规划问题，具有较高的应用价值。

不管在国内还是国外，物流配送路径规划算法已经广泛应用于生产和生活的各个方面，如报纸配送路径的优化，牛奶配送路径的优化等等。在物流车辆配送的过程中，路径规划算法能大大地减少配送车的数量、降低车辆的总行驶距离。在如今如火如荼的外卖配送环节上，物流路径规划算法可优化外卖配送人员的配送路线，进而减少商家的配送成本，同时也提高了客户对商家的满意度。最重要的是，中国的物流市场有巨大的物流配送路径优化需求，如果能在路径规划中取得突破，将会带来非常大的社会效应。

就目前针对物流配送路径规划和优化方面的研究而言，基于GIS的路径规划算法更加贴近实际情况，更具有现实意义。

1.2 国内外研究现状

物流配送路径规划和优化问题可归为车辆路径问题，该问题由Dantzig和Ramser于1959年提出^[16]，至今仍处于组合优化研究领域的热点问题。VRP问题属于组合优化问题，同时是一个NP难题。至今为止，求解该问题的算法也比较成熟，主要分为精确算法（比如分枝界限法）和启发式算法。启发式算法又分为传统启发式算法（比如构造性方法、局部搜索算法）和元启发式算法（比如模拟退火算法（Simulated Annealing，SA）、遗传算法（Genetic Algorithm，GA））。

国外对VRP的研究比国内要早，比如经典的遗传算法、蚁群算法等，常用来求解VRP这类组合优化问题。国内后来也有相关研究，比如人工鱼群算法、伊藤算法。而由所读文献可知，国内外均多用群智能搜索算法解决此类问题，遗传算法、蚁群算法使用的最多，且单个算法求解的效果往往不如意，不同算法融合后可互补自身的不足之处，取得更好的效果。同时，VRP问题根据应用场景的不同，具体解决方案也不同，研究现状具体如下：

（1）Eneko Osaba，Xin-She Yang等人针对RVRP（rich vehicle routing problem）问题提出了离散型的改进蝙蝠算法（Discrete and Improved Bat Algorithm，DaIBA）。改进蝙蝠算法使用众所周知的汉明距离来计算蝙蝠之间的差异，同时存在两个不同的邻域结构，此结构根据蝙蝠对于群体最佳个体的距离进行探索。实验证明该改进算法优于进化算法，进化模拟退火算法和萤火虫算法^[1]。

（2）Eneko Osaba，Xin-She Yang等人针对RVRP问题，提出了离散型萤火虫算法（Discrete Firefly Algorithm，DFA），实验结果证明该算法优于进化算法和进化模拟退火算法，具有良好的发展前景^[2]。

（3）Yiyong Xiao，Abdullah Konak针对带分层目标和加权延迟的GVRSP（green vehicle routing and scheduling problem）问题，引入模拟退火算法来解决大型问题实例。为了减小搜索空间，SA算法仅搜索车辆路线和粗略的时间表，再使用简单的启发式过程来确定给定路线组的近乎最佳的详细时间表^[4]。

（4）R. J. Kuo，Ferani E. Zulvia考虑具有模糊需求的CVRP（Capacitated Vehicle Routing Problem），提出了一种混合遗传算法和蚁群优化算法（Ant Colony Algorithm，ACO）。它结合了GA，ACO和两种局部搜索方法，即Prim算法和2-opt算法^[5]。

以上是毕业论文大纲或资料介绍，该课题完整毕业论文、开题报告、任务书、程序设计、图纸设计等资料请添加微信获取，微信号：bysjorg。

相关图片展示：