物流中心货物调度分配的最优规划及算法研究

摘要

如今，物流业的发展已成为推动我国经济发展的重要因素。目前，有许多物流中心在进行货物调度时仍旧采取人工的方法，靠人工的管理经验来处理物流问题，这往往使得物流的成本过高，效益降低。在物流管理上运用信息化技术，使用计算机来进行管理逐渐成为一个新的课题。“信息化物流”将逐渐占据着主导地位。
　　 物流中心在进行货物调度时，最主要的两个问题就是车辆的调度和路线的安排。目前，解决这一问题普遍使用遗传算法。但是，利用单纯的遗传算法解决这一问题时，往往容易陷入局部最优解，而退火算法在寻求问题的全局最优解时不失为一种优秀的算法。
　　 基于这一点，本文所做的主要工作和创新点如下：
　　 文章首先介绍了有关物流的基本知识，国外配送中心计算机管理信息系统的发展情况及国内配送中心计算机管理信息系统的发展情况。
　　 其次，建立了货物调度模型并比较了各种算法及模型算法的复杂性分析。
　　 然后对模型建立了遗传算法并从两种方案出发分析了它们各自的优缺点。在第一种方案中，使用二进制数据作为编码，这一方案的优点主要体现在能在较短时间内找到最优解、其适应度函数起到了较好的优化作用等；主要缺点体现在没有考虑到车辆二次分配、对规模较大的配货难以适应。在方案二中使用自然数作为编码，主要做法是首先随机生成一条染色体，然后将其中的基因一个一个加入，根据一定的停止准则判断它加入后是否是一条可行的子路径。该方案主要的缺点是未对相似染色体采取有效的操作、解易陷入局部最优。
　　 紧接着研究了模拟退火算法在物流调度模型上的应用，主要做法是运用了Metropolis算法思想：从某个初始解出发，经过多次解的变换后，在某个控制参数T确定相对的最优解。然后适当减小T的值，循环执行Metropolis算法，当T→0时，组合问题的整体最优解就可以最终求出。
　　 然后，提出了一种改进的算法-遗传模拟退火算法。在算法中增加了一个记忆装置，该记忆器引进了两个变量ii和ff，其中变量ii用来存放当前遇到的最优解，ff用来保存它的返回值。首先初始化ii为一个初始解ii0，ff0做为它对应的函数值，即在搜索新解前，令ii=ii0，ff=ff0(ff0是由ii0确定的)；在循环过程中，每次求得一个新的解，(假设为ix)，都将其对应的目标函数值fx与当前的ff函数值比较，如果fx函数值比当前ff函数值优，那么ii和ff函数值都用ix和fx函数值代替。在算法结束时，再将最后所得到的所谓最优解与记忆装置中的最好结果比较，看那一个更优就取那一个，从而获得真正的最终最优解。
　　 文中的两个实验分析表明：本文所述的这一改进的遗传算法一方面可以将算法的收敛速度显著提高；另一方面可以保证所求得的结果是全局最优；最后一点就是因为算法采用的是自然数的编码方案，可以将较多的客户点信息用较小的一部分空间来存储。
　　 从这两个实验还可以看出：本文所述算法与传统的遗传算法相比较的优势在于：一方面要得到相同的结果可以缩短进化代数，从而节约运算时间；另一方面就是即便采用相同的进化代数，虽然在进化代数较少时对结果的改进并不明显，但是随着进化代数的增加，本文所述算法比传统的遗传算法所获得的结果相对更优。
　　 在文章的最后，我把自己做的工作总结了一下，而且对今后的打算做了一个展望。