物流配送中几种路径优化算法

《物流配送中几种路径优化算法》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、捕食搜索算法　　动物学家在研究动物的捕食行为时发现，尽管由于动物物种的不同而造成的身体结构的千差万别，但它们的捕食行为却惊人地相似.动物捕食时，在没有发现猎物和猎物的迹象时在整个捕食空间沿着一定的方向以很快的速度寻找猎物.一旦发现猎物或者发现有猎物的迹象，它们就放慢步伐，在发现猎物或者有猎物迹象的附近区域进行集中的区域搜索，以找到史多的猎物.在搜寻一段时间没有找到猎物后，捕食动物将放弃这种集中的区域，而继续在整个捕食空间寻找猎物。　　模拟动物的这种捕食策略，Alexandre于1998提出了一种新的仿生计算方法，即捕食搜索算法(predatorysearchal

2、gorithm,PSA)。基本思想如下：捕食搜索寻优时，先在整个搜索空间进行全局搜索，直到找到一个较优解;然后在较优解附近的区域(邻域)进行集中搜索，直到搜索很多次也没有找到史优解，从而放弃局域搜索;然后再在整个搜索空间进行全局搜索.如此循环，直到找到最优解(或近似最优解)为止，捕食搜索这种策略很好地协调了局部搜索和全局搜索之间的转换.目前该算法己成功应用于组合优化领域的旅行商问题(travelingsalesmanproblem)和超大规模集成电路设计问题(verylargescaleintegratedlayout)。　　捕食搜索算法设计　　(1)解的表达　

3、　采用顺序编码，将无向图中的，n一1个配送中心和n个顾客一起进行编码.例如，3个配送中心，10个顾客，则编码可为:1一2一3一4一0一5一6一7一0一8一9一10其中0表示配送中心，上述编码表示配送中心1负贡顾客1,2,3,4的配送，配送中心2负贡顾客5,6,7的配送，配送中心3负贡顾客8,9,10的配送.然后对于每个配送中心根据顾客编码中的顺序进行车辆的分配，这里主要考虑车辆的容量约束。依此编码方案，随机产生初始解。　　(2)邻域定义　　4仿真结果与比较分析(Simulationresultsandcomparisonanalysis)　　设某B2C电子商务企

4、业在某时段由3个配送中心为17个顾客配送3类商品，配送网络如图2所示。　　为计算简洁，设各配送中心可用车辆数人Ap=3辆，最大载重量Q=10吨，车辆启动费用Bk=400元，单位距离费用Cij=5元，3类商品的重量系数分别为W1=0.2吨/件，W2=0.4吨/件，W3=0.3吨/件，其他相关参数见表1。　　捕食搜索算法采用Java语言在Windows平台上(主频Y4N1/2.2G,内存512N)实现。求得最优解值和车辆配送路径如表2所示，可以看出此结果能直接得到基于配送网络的车辆实际配送路径。该类顾客仅在第一次被访问的时候配送服务了表2。　　配送路径中黑体节点表示

5、车辆配送的顾客和其次序少，这和实际配送情况亦是相符的。为了验证捕食搜索算法的有效性，利用捕食搜索算法与基于类顺序交叉和换位变异算子的遗传算法子编码相同，交叉率为变异率为迭代次数为soot对上述算例各随机计算10次，得到相应的目标值和计算时间如表3所示。由表3中可以看出，YSA求得的目标值全而优于GA,10次计算中9次得到了最优值(或近似最优值)20850元，而GA的最优值仅为21050元，计算平均值，从计算的时间来看，YSA的计算效率高于C从但是YSA的计算时间没有C、稳定，可以从它们计算时间的标准差上看出这一点，这是因为以在算法参数设定后计算时间波动很小(以最

6、大迭代次数为停止准则)，而YSA因为模仿动物捕食的内在特点，除了算法参数外，其初始解亦会影响算法的计算时间。上述两种算法在多个算例上进行了实验，得到了相似的结论。因而，文中设计的YSA作为一类新的优化算法对模型的求解是可行和高效的。禁忌（TabuSearch）算法是禁忌（TabuSearch）算法一种亚启发式(meta-heuristic)随机搜索算法1，它从一个初始可行解出发，选择一系列的特定搜索方向（移动）作为试探，选择实现让特定的目标函数值变化最多的移动。为了避免陷入局部最优解，TS搜索中采用了一种灵活的“记忆”技术，对已经进行的优化过程进行记录和选择，指

7、导下一步的搜索方向，这就是Tabu表的建立。为了找到“全局最优解”，就不应该执着于某一个特定的区域。局部搜索的缺点就是太贪婪地对某一个局部区域以及其邻域搜索，导致一叶障目，不见泰山。禁忌搜索就是对于找到的一部分局部最优解，有意识地避开它（但不是完全隔绝），从而获得更多的搜索区间。兔子们找到了泰山，它们之中的一只就会留守在这里，其他的再去别的地方寻找。就这样，一大圈后，把找到的几个山峰一比较，珠穆朗玛峰脱颖而出。当兔子们再寻找的时候，一般地会有意识地避开泰山，因为他们知道，这里已经找过，并且有一只兔子在那里看着了。这就是禁忌搜索中“禁忌表（tabulist）”的含

8、义。那只留在泰山的兔子一