物流配送车辆调度优化方法比较研究(3)

物流配送车辆调度优化方法比较研究

!

!化的第一目标。

３．３．２遗传算法（ＧｅｎｅｔｉｃＡｌｇｏｒｉｔｈｍｓ，ＧＡ）

遗传算法是借用适者生存规律进行局部搜索改进的一类算法。最早是由Ｈｏｌｌａｎｄ在１９７５年提出，并首先被ＤｅＪｏｎｇ用来解决复杂问题。该算法通过染色体的配对和变异过程实现种群的进化，每一次进化则对应解的一次迭代。当迭代次数达到最大次数限制或群体中的个体无显著差异时，迭代终止。

１９９１年，Ｔｈａｎｇｉａｈ首先将遗传算法用于求解ＶＲＰＴＷ问题。该文将遗传算法用于点的分组。其中，每一种分组方案被编码为一个染色体，适应性函数值定义为根据相应的分组方案所构造的路线总成本，而交配则指通过随机选取染色体的两个位串（即两个组）进行的点的互换，最后以小概率事件改变其中某些位的值来实现变异。

１９９９年，Ｈｏｍｂｅｒｇｅｒ和Ｇｅｈｒｉｎｇ提出了应用遗传算法求解ＶＲＰＴＷ问题的进化策略。具体地，将所谓的策略参数与解向量一同编码，并通过重组和变异来实现进化。对于ＶＲＰＴＷ问题，策略参数包括某种局部搜索方法的使用频率，以及在车辆数和总路长这两个目标之间交替改进的一个二进制参数。同年，Ｇｅｈｒｉｎｇ和Ｈｏｍｂｅｒｇｅｒ采用一种协同自治的方式在车辆数优化方法与总路长优化方法之间建立一种协作关系。

３．３．３模拟退火算法（ＳｉｍｕｌａｔｅｄＡｎｎｅａｌｉｎｇ，ＳＡ）

１９９６年，Ｃｈｉａｎｇ和Ｒｕｓｓｅｌｌ提出ＶＲＰＴＷ问题的模拟退火算法。模拟退火算法实际上是一种随机松弛技巧，它模拟了退火过程。在搜索的初始阶段，算法跳向远点，随着时间的延伸或“降温”，跳跃幅度逐渐减小，最终转向局部搜索下降方法。

２０００年，Ｔａｎ等基于２－ｉｎｔｅｒｃｈａｎｇｅ法和单调降的降温表提出一种快速模拟退火算法。当到达最低温度后，通过参考初始温度和到达最好解时的温度设置一个新的温度，然后重新启动模拟退火搜索过程。２００１年，Ｌｉ等在应用插入算法和扫除算法初始化路线后，将邻域搜索方法与模拟退火程序相结合实现路线改进。

３．３．４蚁群算法（ＡｎｔＣｏｌｏｎｙＯｐｔｉｍｉｚａｔｉｏｎ，ＡＣＯ）

蚁群算法模拟了蚁群搜索食物的行为。在寻找食物时，蚂蚁会在它所经过的路径通过排放一种外激素（ｐｈｅｒｏｍｏｎｅ，在算法中称为信息素）作出标记，排放的量则根据路径长度和食物的等级决定。这些外激素为其它蚂蚁提供信息，并吸引他们前去搬运食物。对于ＶＲＰＴＷ问题，也可以根据蚂蚁觅食原理来进行搜索。１９９９年，Ｇａｍｂａｒｄｅｌｌａｅｔａｌ．应用蚁群算法对ＶＲＰＴＷ进行路线改进。算法中，首先构造两组相互协作的人工蚁群，其中第一个蚁群用于最小化车辆数，第二个蚁群用于最小化总路长。并以共用解的方式建立协作关系。

３．４各种优化方法的比较分析

综上所述，各种优化方法在一定时期、一定情况下都有各自的优点，都有解决某一类问题的优越性，但随着发展的需要，对优化方法要求也越来越高，下面对各种方法进行比较分析，通过表格的形式来展现各自的特点。

通过表格的分析比较，可以看出各种方法的特点，ＶＲＰＴＷ问题的最优化算法有一个共同的特点就是可以求得最优解，但不适应现在的复杂的车辆优化问题，尤其是对多配送点的大型配送服务，相对求得最优解比较费时

各种优化方法的比较分析表

类别基本方法优点缺点应用时间适用性

计算时间过长且占用内存

动态规划法可以求得最优解量随变量的增加成指数倍

增长１９８７年适用于规模较小的问题

ＶＲＰＴＷ

的最优

化算法分枝定界法求得最优解计算时间长且内存使用常

有不足现象发生用于解组合优化的小型问题

切平面法可以求得最优解计算时间长且所需内存大适用于解小规模

问题

４８

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库物流配送车辆调度优化方法比较研究(3)在线全文阅读。