带软时间窗约束的车辆路径问题的混合算法研究及其应用_第1页
带软时间窗约束的车辆路径问题的混合算法研究及其应用_第2页
带软时间窗约束的车辆路径问题的混合算法研究及其应用_第3页
带软时间窗约束的车辆路径问题的混合算法研究及其应用_第4页
带软时间窗约束的车辆路径问题的混合算法研究及其应用_第5页
已阅读5页，还剩4页未读， 继续免费阅读

付费下载

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

带软时间窗约束的车辆路径问题的混合算法研究及其应用车辆路径问题(VehicleRoutingProblems,VRP)是一个NP难问题,是物流领域中具有重要理论和实际意义的问题。在现实生活中,有很多问题可以抽象为VRP问题,如银行押款车的行驶路线、快递分发包裹、工业垃圾回收、校车接送学生、餐馆送餐等。选择合理的物流配送方案,可以降低企业物流开支,节约成本,提高效率,加速货物的流通过程,赚取更多的利润,对于一个企业的成败具有关键性意义。在中国物流业快速发展的今天,对VRP问题的研究愈发重要。带时间窗约束的VRP问题(VehicleRoutingProblemswithTimeWindows,VRPTW)是在基本VRP问题的基础上衍生而来,有着很高的研究价值。本文致力于研究带重量约束和软时间窗约束的VRP问题(CapacitatedVehicleRoutingProblemswithSoftTimeWindows,CVRPSTW)。长期以来,国内外许多学者对这个问题进行了大量的研究和阐述,产生了许多优秀的算法。在他们工作的基础上,利用VRP问题的数学模型,本文提出了一种分布式的多阶段混合启发式算法,目标是在合理的时间内取得较好的结果。本文的主要工作包括:第一,实现单机版的多阶段混合启发式算法,包括使用模拟退火算法(SimulatedAnnealing,SA)对车辆数目进行优化,使用禁忌搜索算法(TabuSearch,TS)对违反时间窗代价和路线总行程距离进行优化。在求解过程中,使用了多种不同的邻域生成方法,包括对部分元素的交换和重置的小邻域生成法、基于摧毁和重建思想的大邻域生成法,以减少在局部最优附近的重复搜索。加入自适应存储(AdaptiveMemory,AM)算法,当搜索陷入瓶颈时,从AM中产生新的邻域搜索中心,开始新一轮迭代搜索,使得搜索及时跳出瓶颈并向着好的方向前进,保证搜索的有效性和多样性。第二,基于Spark分布式框架,实现算法的分布式版本,比较单机版本与分布式版本的解的质量和求解效率。第三,开发实现一个AndroidAPPdemo,将VRPSTW问题与当下活跃的外卖配送相结合,将算法理论与实际应用相结合。文中采用Solomon的benchmark数据集进行算法测试。实验结果表明,提出的SA算法和TS搜索算法有着不错的表现;分布式的混合算法取得了良好的效果,保证能在较短的可接受时间内取得不错的结果。A

人人文库> 全部分类> 应用文书 > 作业报告

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论