循环取货VRP算法.ppt

《循环取货VRP算法.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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

2、emanProblem,TSP）是VRP的特例扫描法构造初始解对起迄点重合问题，有一种简单有效的方法—扫描法是是开始将所有的停留点位置画在地图上选择最大的车辆装载这个停留点的货物然后顺时针或逆时针方向转动直尺，直到直尺交到一个停留点。通过仓库位置放置一直尺，直尺指向任何方向均可是否超过车辆容积或体积的限度是否扫描完所有停留点安排下一辆车装载货物，得到一条运行线路结束继续转动直尺，扫描到下一个停留点，分配该车辆装载货物优化每条运行路线的停留点顺序，以求运行距离最小化否否扫描法【例】某公司从其所属的仓库用送货车辆到各客户点提货，

3、然后将客户的货物运回仓库，以便集运成大的批量再进行远程运输。全天的提货量见下图，提货量以件为单位。送货车每次可运载1万件，完成一次运行路线一般需要一天时间。该公司要求确定：需多少条路线（即多少辆送货车）；每条路线上有哪几个客户点；送货车辆途经有关客户点的顺序。扫描法400010003000200010002000200020002000300020003000禁忌搜索（TabuSearch，TS，又称禁忌搜寻法）FredGlover1986亚启发式(meta-heuristic)随机搜索算法它从一个初始可行解出发，选择一系列

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

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

6、-N(xnow)中选一个评价值最好的解xbest,令xnow=xbest,更新禁忌表H,转第二步；第四步输出计算结果,停止。VRP中tabu算法的邻域2-OPT交换法1-0交换法1-1交换法