论文摘要
近年来,随着我国经济的迅猛发展和计算机技术在各行业的广泛运用,现代物流在我国也得到了前所未有的发展。我国是贸易大国,交易规模大,产品利润低,而物流成本的费用却越来越高,在竞争日益激烈的现代商业社会,通过优化物流配送路线来节约成本,提高效率,可使企业立于不败之地。优化物流配送路线的主要任务是调配合适数量的车辆,确定配送路线、时间和服务对象,即确定最佳的配送路线,使企业降低配送成本和改善客户服务水平。优化物流配送路线属于NP难题问题之一。遗传算法(Genetic Algorithm)是一类借鉴生物界的进化规律(适者生存,优胜劣汰遗传机制)演化而来的随机化搜索方法,已经成功运用在很多大规模的组合优化问题中。“固有并行性”是遗传算法的一个重要的特性,利用如今流行的并行计算机系统,对遗传算法进行并行化,可解决标准遗传算法的速度瓶颈问题。基于高性能计算技术的并行程序设计模式MPI (Message Passing Interface)是目前一种比较著名的应用于并行环境的消息传递标准。MPICH是MPI标准的一个完全实现,也是应用范围最广的一种并行及分布式环境。通过MPICH可以非常容易的连接现有的计算机组建集群进行高性能计算。本文研究了在基于MPI构建的PC机群环境下实现并行遗传算法的相关问题,并成功应用于物流配送路线的优化。论文首先对并行计算进行讨论,阐述了并行计算机体系结构、并行编程理论和并行算法；接着介绍了目前流行的用于并行环境编程的消息传递标准MPI及其基本函数,用MPICH搭建了一个基于Windows操作系统的小型机群系统。论文详细介绍了遗传算法以及基于MPI对遗传算法进行粗粒度并行化的程序设计,利用设计好的一种粗粒度并行遗传算法对优化物流配送路径问题进行了程序设计分析和完全的程序实现。最后,论文用标准遗传算法和并行遗传算法程序对有25个客户点的物流配送路线问题进行了优化,通过对其结果的比较和分析,发现并行遗传算法对问题的求解速度和质量都有显著提高。