登录

  • 登录
  • 忘记密码?点击找回

注册

  • 获取手机验证码 60
  • 注册

找回密码

  • 获取手机验证码60
  • 找回
毕业论文网 > 开题报告 > 计算机类 > 计算机科学与技术 > 正文

基于GIS的物流配送路径规划算法设计和实现开题报告

 2020-02-20 07:02  

1. 研究目的与意义(文献综述)

现代物流业的发展目标是以现代制造业和服务业为基础,以现代运输业为重点,利用现代信息和通信技术来实现物流配送服务的标准化、信息化和智能化,其中智能化是现代物流发展的核心。随着“互联网 ”战略的实施和电子商务的快速发展,具有服务更加迅捷、精准和个性化等特点和优势的智慧物流将会发展成为支撑互联网经济、促进产业转型升级的先导行业。

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

不管在国内还是国外,物流配送路径规划算法已经广泛应用于生产和生活的各个方面,如报纸配送路径的优化,牛奶配送路径的优化,车辆装载及线路设计,垃圾车线路的优化,连锁店配送线路的优化,快递配送路径的优化等等[2]。在车辆配送环节,物流配送路径规划算法可以有效降低车辆使用数量和车辆行驶距离;在仓库内部拣选作业中,物流配送路径规划算法可以降低拣选人员的行走距离。此外,物流配送路径规划算法还可以帮助外卖配送员规划配送路线,从而提升客户体验、大幅度降低配送成本。中国有全球最大的物流市场,涉及到大量的车辆、人员的配送拣选路径优化,随着新物流时代的到来,即时送达需求旺盛,其中也涉及到大量外卖员的配送路径优化,我们如果能在路径规划中取得突破,将会在带来非常大的社会效应。所以,我们需要基于GIS(地理信息系统)研究出更为优秀的物流配送路径规划解决方案来满足人们日益增长的物质需求。

目前物流配送路径规划算法也不少,也比较成熟,多是启发式和元启发式搜索算法,但这是个NP难题,由于NP-hard在VRP(车辆路径规划问题)的特点,解决方案的复杂性随着需求节点的增加呈指数增长,所以我们需要不断探索,尝试提出更好的物流配送路径规划算法来达到减少运输成本等目标。

VRP问题是一个组合优化问题,按照不同的约束条件可分为多类问题。而由所读文献可知,国内外多用元启发式搜索算法(如遗传算法、蚁群算法)解决此类问题,遗传算法由于收敛速度快、全局收敛性和随机搜索性而被广泛采纳。VRP问题根据应用场景的不同,具体解决方案也不同,比如:

(1)冯亮、梁工谦设计了基于GPS/GlS协同的物流配送车辆监控和调度系统,基于该系统实时获取的配送车辆、运行环境及客户需求等相关信息对车辆调度和路径规划的影响,构建了带时间窗的动态车辆路径问题(Dynamic Vehicle Routing Problem with Time Windows,DVRPTW)混合整数规划(Mixed Integer Programming,MIP)模型,并采用混合遗传算法。

(2)王勇、周恒、王莹创建了CVRP数学模型,采用遗传算法对物流车辆的路径进行规划,以满足物流运输成本最小的要求。

(3)胡海峰,王晓慧创建了CVRP数学模型,提出了基于双层染色体编码方案和自适应交叉概率的改进遗传算法。

(4)丁丹、邹行利用 Dijkstra 算法和节约算法建立并求解了相应的配送路由优化模型。

(5)沈若男,苏有慧建立了不确定因素下最优路径模型,利用正态分布的可加性,得出各条路径的总行驶时间正态分布表达式,并进行标准化,解出行驶时间的表达式。当到达终点的概率确定时,最优路径为行驶时间最少的路径。并在此基础上设计了基于深度优先搜索的最优路径算法。

(6)潘国强,胡俊逸,洪敏针对大规模VRP配送问题,提出一种配送区域划分的启发式 - 模拟退火混合搜索算法。针对 GIS 中实际路网建立路网数学模型,并在大规模VRP路径规划问题研究中与实际 GIS 路网相融合。并对配送路径规划问题提出一种结合 GIS 模型约束的启发式路径搜索算法。

(7)葛斌,韩江洪,魏臻等人针对传统蚂蚁遗传混合算法中参数静态设置、冗余迭代及收敛速度慢等缺点,提出一种动态混合蚁群优化算法(DHACO)。该算法首先借助最大最小蚁群得到初始解,利用蚁群优化算法求解带时间窗车辆路径问题的基本可行解。然后采用遗传算法交叉和变异操作对局部解和全局最优解进行二次优化,从而得到最优解。最后利用蚂蚁遗传混合算法融合策略,动态交叉调用蚂蚁算法、遗传算法,根据云关联规则自适应控制蚁群算法参数。DHACO有效减少无效迭代次数,加快收敛速度。

(8)费腾,张立毅,孙云山将DNA算法中的交叉变异思想应用于基本蚁群算法中,提出一种新的DNA-蚁群算法,将基本蚁群算法中的参数进行DNA交叉变异,有效控制蚁群算法的参数选择,从而得到一组最优参数来求解VRP模型。

(9)Wenjuan Gu,Diego Cattaruzza, Maxime Ogier等人创建了C-SDVRP模型,提出了一个自适应大邻域搜索方法,目标是在小型实例上获得非常好的解决方案,并且能够实现有效地解决大型实例。

(10) R. J. Kuo,Ferani E. Zulvia考虑具有模糊需求的CVRP(CVRPFD),提出了一种混合遗传算法(GA)和蚁群优化(ACO)。它结合了GA,ACO和两种局部搜索方法,即Prim算法和2-opt。

(11)张湘博,李文敬,周杰等人提出了基于深度学习的物流配送路径优化算法。首先构建基于自编码网络的模型,依据样本数据对模型进行训练,预测路段代价值ω,然后与城市干道网络相结合,建立带权重交通网络。

(12)张立毅,王迎,费腾等人针对物流配送中碳排放的度量方法,以VRP问题为基本模型,以碳排放成本为目标函数,建立了低碳物流配送路径优化模型。为了避免基本蚁群算法出现停滞及早熟现象,本文提出了带混沌扰动的模拟退火蚁群算法来求解低碳物流配送路径优化模型。该算法将混沌系统及模拟退火机制引入基本蚁群算法,避免了算法陷入局部最优,增强了全局搜索能力,提高了求解效率。

2. 研究的基本内容与方案

基本内容:

(1)通过阅读相关文献,创建CVRP数学模型,分析目前常见的路径规划算法,如遗传算法、模拟退火算法、粒子群算法、蚁群算法等,比较这些算法的优劣,并结合物流配送的特性,设计出可求解CVRP模型的路径规划优化算法。

(2)实现所设计的算法,并用数据集验证所设计的算法的有效性,以及有更好的性能。

(3)构建基于GIS的物流配送路径规划原型系统,对配送路径进行调整和优化,以最小化配送路径和物流运输成本,从而提高物流配送效率。

技术方案:

大体上分为四个步骤:

(1)结合GIS路网建立CVRP数学模型

物流配送问题描述:已知存在C个客户点,给定每个客户点的需求量和坐标点,为了使配送总成本(距离、时间等)能达到最小,配送车辆的载重量不变,每辆车从配送中心出发,到达相应客户点并完成配送任务后,最终返回配送中心。同时,要求合理安排配送路径,使得运输距离达到最短,运输成本最低,且同时满足以下约束条件:①每条路径上客户点的需求量之和不超过汽车的载重量;②每条配送线路的总长度不超过汽车配送一次的最大行驶距离;③只允许一辆汽车经过某一个客户点。根据问题描述定义所需的符号(如路网模型和客户需求),构建CVRP问题的模型图,根据约束条件建立等式或者不等式,最后定义目标函数。

(2)设计出求解CVRP数学模型的混合路径规划算法

针对目前已创建的CVRP数学模型,以基本蚁群算法为基础,设计出改进的蚁群算法。由于蚁群算法在解决车辆路径问题(VRP)时存在过早收敛于局部最优解、收敛速度慢等问题,并且由于蚁群算法的参数选择没有严格规定,如果参数选择不当,将影响其寻找最优解的效率。所以,主要对蚁群算法作以下方面的改进:首先,在初始化信息素浓度时使用爬山算法产生物流路径问题的初始信息素分布;其次,结合禁忌搜索算法的特点,对于找到的一部分局部最优解,有意识地避开它,从而或得更多的搜索区域,最终找到全局最优解。

(3)验证算法

针对特定的区域,根据实际路网情况建立 GIS 路网模型。使用python语言编写算法程序,并用CVRP基准数据集测试设计出的算法的有效性和性能。由于创建出的CVRP模型在满足车辆最短路径和客户需求下,目标是减少运输成本,所以以成本目标函数的测试值和算法运行时间作为验证指标。

(4)结果分析

分析测试结果,将设计出的改进的物流配送路径规划算法与基本蚁群算法、禁忌搜索算法等算法相比较,计算出设计的算法相对于其他算法的性能提高比,最后给出基于GIS的物流配送路径规划原型系统。

3. 研究计划与安排

第一阶段(2019/1/14—2019/2/22):明确选题,查阅相关文献,外文翻译和撰写开题报告;

第二阶段(2019/2/23—2019/4/30):算法研究与设计,算法优化、测试;

剩余内容已隐藏,您需要先支付后才能查看该篇文章全部内容!

4. 参考文献(12篇以上)


[1] 冯亮,梁工谦. 基于gps/gis协同的动态车辆调度和路径规划问题研究[j].计算机科学,2017,44(9):272-276.

[2] zou hao,zhang tiantian. research onvehicle routing algorithm for supply chain logistics distribution[c]. matec web of conferences,2018,227-233,publishedonline,doi:

剩余内容已隐藏,您需要先支付 10元 才能查看该篇文章全部内容!立即支付

企业微信

Copyright © 2010-2022 毕业论文网 站点地图