循环取货VRP算法.ppt_第1页
循环取货VRP算法.ppt_第2页
循环取货VRP算法.ppt_第3页
循环取货VRP算法.ppt_第4页
循环取货VRP算法.ppt_第5页
已阅读5页，还剩5页未读， 继续免费阅读

下载本文档

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

文档简介

1、2020/6/19,车辆路径问题（VehicleRoutingProblem,VRP）,Dantzig和Ramser1959指一定数量的客户，各自有不同数量的货物需求，配送中心向客户提供货物，由一个车队负责分送货物，组织适当的行车路线，目标是使得客户的需求得到满足，并能在一定的约束下，达到诸如路程最短、成本最小、耗费时间最少等目的。,2020/6/19,旅行商问题（TravelingSalemanProblem，TSP）,Dantzig1959该问题是在寻求单一旅行者由起点出发，通过所有给定的需求点之后，最后再回到原点的最小路径成本。旅行商问题（TravelingSalemanProblem,

2、TSP）是VRP的特例,扫描法构造初始解,对起迄点重合问题，有一种简单有效的方法扫描法,扫描法,【例】某公司从其所属的仓库用送货车辆到各客户点提货，然后将客户的货物运回仓库，以便集运成大的批量再进行远程运输。全天的提货量见下图，提货量以件为单位。送货车每次可运载1万件，完成一次运行路线一般需要一天时间。该公司要求确定：需多少条路线（即多少辆送货车）；每条路线上有哪几个客户点；送货车辆途经有关客户点的顺序。,扫描法,2020/6/19,禁忌搜索（TabuSearch，TS，又称禁忌搜寻法）,FredGlover1986亚启发式(meta-heuristic)随机搜索算法它从一个初始可行解出发，选

3、择一系列的特定搜索方向（移动）作为试探，选择实现让特定的目标函数值变化最多的移动。为了避免陷入局部最优解-Tabu表的建立。,2020/6/19,tabu搜索算法的直观解释,兔子们找到了泰山，它们之中的一只就会留守在这里，其他的再去别的地方寻找。当兔子们再寻找的时候，一般地会有意识地避开泰山，因为他们知道，这里已经找过，并且有一只兔子（“禁忌表（tabulist）”）在那里看着了，那只留在泰山的兔子一般不会就安家在那里了，它会在一定时间（“禁忌长度（tabulength）”）后重新回到找最高峰的大军，因为这个时候已经有了许多新的消息，泰山毕竟也有一个不错的高度，需要重新考虑，如果在搜索的过程中

4、，留守泰山的兔子还没有归队，但是找到的地方全是华北平原等比较低的地方，兔子们就不得不再次考虑选中泰山，也就是说，当一个有兔子留守的地方优越性太突出，超过了“bestsofar”的状态，就可以不顾及有没有兔子留守，都把这个地方考虑进来（“特赦准则（aspirationcriterion）”）。,2020/6/19,tabu搜索算法的基本步骤,第一步选定一个初始解xnow;令禁忌表；第二步若满足终止准则,转第四步；否则,在xnow的邻域N(xnow)中选出满足禁忌要求的候选集C-N(xnow),转第三步；第三步在C-N(xnow)中选一个评价值最好的解xbest,令xnow=xbest,更新禁忌表H,转

人人文库> 全部分类> 应用文书 > 技术指导

温馨提示

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

最新文档

评论

0/150

提交评论