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

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

2、食搜索寻优时，先在整个搜索空间进行全局搜索，直到找到一个较优解。然后在较优解附近的区域（邻域进行集中搜索，直到搜索很多次也没有找到史优解，从而放弃局域搜索。然后再在整个搜索空间进行全局搜索.如此循环，直到找到最优解（或近似最优解为止，捕食搜索这种策略很好地协调了局部搜索和全局搜索之间的转换目前该算法己成功应用于组合优化领域的旅行商问题（travelingsalesmanproblem和超大规模集成电路设计问题（verylargescaleintegratedlayout。捕食搜索算法设计（1解的表达采用顺序编码，将无向图中的，n1个配送中心和n个顾客一起进行编码.例如，3个配送中心，10个顾客

3、，则编码可为: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电子商务企业在某时段由3个配送中心为17个顾客配送3类商品，配送网络如图2所示。0-E送中亡节点.O一顾客节点节盘之狗的边N2实辭倒送网恪用为计算简洁，设各配

4、送中心可用车辆数人Ap=3辆，最大载重量Q=10吨，车辆启动费用Bk=400元，单位距离费用Cij=5元，3类商品的重量系数分别为W1=0.2吨/件，W2=0.4吨/件，W3=0.3吨/件，其他相关参数见表1。衷|肋密鬧s类裔币的軽杀舄和配進中心悦应足傑谊：件TilkI(hakiMriddai;mdhdhddblrIjiiIij朝虑飾配最优配建配送审丰辆川观优II标値J氏中吃Lnjq1.51弘弘1Irk10-1肚丄1-2-亠IB530J22CW53斗5：|:；i79I.H-3-J-5-6-7-9-I&配送中心2171615Id1211141了-心15-W-12-11-19355Pl3-1配送路

5、径中黑体节点表示车辆配送的顾客和其次序少，这和实际配送情况亦是相符的。为了验证捕食搜索算法的有效性，利用捕食搜索算法与基于类顺序交叉和换位变异算子的遗传算法子编码相同，交叉率为变异率为迭代次数为soot对上述算例各随机计算10次，得到相应的目标值和计算时间如表3所示。表3摘您捏索算沬（I临“与遗传环法X计算结果比较3.ik3（iauipjlKCbii4i：l.niiin|inki1hnhI屮铁il卜h机办屮.口phdkbisKMirhaIgiill：iildJjdulk-anillnil（G?O目杯代炕讣n时间刑GAr-LGAESA1ZMflO2DA10045L041122&S0WiO竹睥2Q

6、4O3225Q02呃1)09UI(153112UA0amooaj0庇II522900ZCMiO09120461621010208iG0S21nn7231S0zoaiti0S3I0561H22R502jmoQ83J.。抽192342022M008510IRO102.IS5020fliOCUI10491平沟ffl22S*02O9TL0曲側20850元，而GA的最优值仅为21050元，计算平均值，从计算的时间来看，YSA的计算效率高于C从但是YSA的计算时间没有C、稳定，可以从它们计算时间的标准差上看出这一点，这是由于以在算法参数设定后计算时间波动很小（以最大迭代次数为停止准则，而YSA由于模仿动物

7、捕食的内在特点，除了算法参数外，其初始解亦会影响算法的计算时间。上述两种算法在多个算例上进行了实验，得到了相似的结论。因而，文中设计的YSA作为一类新的优化算法对模型的求解是可行和高效的。禁忌丁8匕口Search）算法是禁忌TabuSearch）算法一种亚启发式（meta-heuristic随机搜索算法1,它从一个初始可行解出发，选择一系列的特定搜索方向移动）作为试探，选择实现让特定的目标函数值变化最多的移动。为了避免陷入局部最优解，TS搜索中采用了一种灵活的“记忆”技术，对已经进行的优化过程进行记录和选择，指导下一步的搜索方向，这就是Tabu表的建立。为了找到“全局最优解”，就不应该执着于某

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

9、泰山毕竟也有一个不错的高度，需要重新考虑，这个归队时间，在禁忌搜索里面叫做“禁忌长度tabulength）”；如果在搜索的过程中，留守泰山的兔子还没有归队，但是找到的地方全是华北平原等比较低的地方，兔子们就不得不再次考虑选中泰山，也就是说，当一个有兔子留守的地方优越性太突出，超过了“bestsofar”的状态，就可以不顾及有没有兔子留守，都把这个地方考虑进来，这就叫“特赦准则aspirationcriterion）”。这三个概念是禁忌搜索和一般搜索准则最不同的地方，算法的优化也关键在这里遗传算法GeneticAlgorithm）是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模

10、型，是一种通过模拟自然进化过程搜索最优解的方法，它最初由美国Michigan大学J.Holland教授于1975年首先提出来的，并出版了颇有影响的专著AdaptationinNaturalandArtificialSystems，GA这个名称才逐渐为人所知，J.Holland教授所提出的GA通常为简单遗传算法SGA）。遗传算法vGeneticAlgorithm）是一类借鉴生物界的进化规律适者生存，优胜劣汰遗传机制）演化而来的随机化搜索方法。它是由美国的J.Holland教授1975年首先提出，其主要特点是直接对结构对象进行操作，不存在求导和函数连续性的限定；具有内在的隐并行性和更好的全局寻优能

11、力；采用概率化的寻优方法，能自动获取和指导优化的搜索空间，自适应地调整搜索方向，不需要确定的规则。遗传算法的这些性质，已被人们广泛地应用于组合优化、机器学习、信号处理、自适应控制和人工生命等领域。它是现代有关智能计算中的关键技术。对于一个求函数最大值的优化问题（求函数最小值也类同，一般可以描述为下列数学规划模型：遗传算法式中X为决策变量，式2-1为目标函数式，式2-2、2-3为约束条件，U是基本空间，R是U的子集。满足约束条件的解X称为可行解，集合R表示所有满足约束条件的解所组成的集合，称为可行解集合。遗传算法的基本运算过程如下：a初始化：设置进化代数计数器t=0，设置最大进化代数T,随机生成

12、M个个体作为初始群体P(0。b个体评价：计算群体P(t中各个个体的适应度。c选择运算:将选择算子作用于群体。选择的目的是把优化的个体直接遗传到下一代或通过配对交叉产生新的个体再遗传到下一代。选择操作是建立在群体中个体的适应度评估基础上的。d交叉运算：将交叉算子作用于群体。所谓交叉是指把两个父代个体的部分结构加以替换重组而生成新个体的操作。遗传算法中起核心作用的就是交叉算子。e变异运算：将变异算子作用于群体。即是对群体中的个体串的某些基因座上的基因值作变动。群体P(t经过选择、交叉、变异运算之后得到下一代群体P(t1。f终止条件判断:若t=T,则以进化过程中所得到的具有最大适应度个体作为最优解输

13、出，终止计算蚁群算法蚁群算法(antcolonyoptimization,AC0，又称蚂蚁算法，是一种用来在图中寻找优化路径的机率型技术。它由MarcoDorigo于1992年在他的博士论文中引入，其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。觅食规则在每只蚂蚁能感知的范围内寻找是否有食物，如果有就直接过去。否则看是否有信息素，并且比较在能感知的范围内哪一点的信息素最多，这样，它就朝信息素多的地方走，并且每只蚂蚁多会以小概率犯错误，从而并不是往信息素最多的点移动。蚂蚁找窝的规则和上面一样，只不过它对窝的信息素做出反应，而对食物信息素没反应。移动规则每只蚂蚁都朝向信息素最多的方向移，并且，当周

14、围没有信息素指引的时候，蚂蚁会按照自己原来运动的方向惯性的运动下去，并且，在运动的方向有一个随机的小的扰动。为了防止蚂蚁原地转圈，它会记住最近刚走过了哪些点，如果发现要走的下一点已经在最近走过了，它就会尽量避开。避障规则如果蚂蚁要移动的方向有障碍物挡住，它会随机的选择另一个方向，并且有信息素指引的话，它会按照觅食的规则行为。播撒信息素规则每只蚂蚁在刚找到食物或者窝的时候撒发的信息素最多，并随着它走远的距离，播撒的信息素越来越少。综述根据这几条规则，蚂蚁之间并没有直接的关系，但是每只蚂蚁都和环境发生交互，而通过信息素这个纽带，实际上把各个蚂蚁之间关联起来了。比如，当一只蚂蚁找到了食物，它并没有直

15、接告诉其它蚂蚁这儿有食物，而是向环境播撒信息素，当其它的蚂蚁经过它附近的时候，就会感觉到信息素的存在，进而根据信息素的指引找到了食物。说了这么多，蚂蚁究竟是怎么找到食物的呢？在没有蚂蚁找到食物的时候，环境没有有用的信息素，那么蚂蚁为什么会相对有效的找到食物呢？这要归功于蚂蚁的移动规则，尤其是在没有信息素时候的移动规则。首先，它要能尽量保持某种惯性，这样使得蚂蚁尽量向前方移动开始，这个前方是随机固定的一个方向)，而不是原地无谓的打转或者震动；其次，蚂蚁要有一定的随机性，虽然有了固定的方向，但它也不能像粒子一样直线运动下去，而是有一个随机的干扰。这样就使得蚂蚁运动起来具有了一定的目的性，尽量保持原

16、来的方向，但又有新的试探，尤其当碰到障碍物的时候它会立即改变方向，这可以看成一种选择的过程，也就是环境的障碍物让蚂蚁的某个方向正确，而其他方向则不对。这就解释了为什么单个蚂蚁在复杂的诸如迷宫的地图中仍然能找到隐蔽得很好的食物。当然，在有一只蚂蚁找到了食物的时候，其他蚂蚁会沿着信息素很快找到食物的。蚂蚁如何找到最短路径的？这一是要归功于信息素，另外要归功于环境，具体说是计算机时钟。信息素多的地方显然经过这里的蚂蚁会多，因而会有更多的蚂蚁聚集过来。假设有两条路从窝通向食物，开始的时候，走这两条路的蚂蚁数量同样多或者较长的路上蚂蚁多，这也无关紧要)。当蚂蚁沿着一条路到达终点以后会马上返回来，这样，短

17、的路蚂蚁来回一次的时间就短，这也意味着重复的频率就快，因而在单位时间里走过的蚂蚁数目就多，洒下的信息素自然也会多，自然会有更多的蚂蚁被吸引过来，从而洒下更多的信息素；而长的路正相反，因此，越来越多地蚂蚁聚集到较短的路径上来，最短的路径就近似找到了。也许有人会问局部最短路径和全局最短路的问题，实际上蚂蚁逐渐接近全局最短路的，为什么呢？这源于蚂蚁会犯错误，也就是它会按照一定的概率不往信息素高的地方走而另辟蹊径，这可以理解为一种创新，这种创新如果能缩短路途，那么根据刚才叙述的原多的蚂蚁会被吸引过来。粒子群算法，也称粒子群优化算法ParticleSwarmOptimization)，缩写为PSO，是近

18、年来发展起来的一种新的进化算法(操作，它通过追随当前搜索到的最优值来寻找全局最优。这种算法以其实现容易、精度高、收敛快等优点引起了学术界的重视，并且在解决实际问题中展示了其优越性。优化问题一是要求寻找全局最优点，二是要求有较高的收敛速度.约束优化问题近年来，一些学者将PSO算法推广到约束优化问题，其关键在于如何处理好约束，即解的可行性。如果约束处理的不好，其优化的结果往往会出现不能够收敛和结果是空集的状况。基于PSO算法的约束优化工作主要分为两类：1）罚函数法。罚函数的目的是将约束优化问题转化成无约束优化问题。2）将粒子群的搜索范围都限制在条件约束簇内，即在可行解范围内寻优。根据文献介绍，Parsopoulos等采用罚函数法，利用非固定多段映射函数对约束优化问题进行转化，再利用PSO算法求解转化后问题，仿真结果显示PSO算法相对遗传算法更具有优越性，但其罚函数的设计过于