论文部分内容阅读
物流是一个新兴学科,配送是现代物流的一个重要内容,合理安排车辆配送路线可以降低运输成本,提高经济效益。车辆路径问题(VRP)是一类在物流配送调度中具有广泛应用的组合优化问题,属于NP难题。为了便于对VRP进行系统的研究,运筹学界将其分为两大类:闭合式VRP和开放式VRP。当车辆完成运输任务后必须返回原出发点时,称之为闭合式VRP,一般就简称为车辆路径问题(VRP);当不要求车辆完成任务后返回原出发点,或者是要求其沿原去程路线返回时,称之为开放式VRP(OVRP)。在不需要严格区分的场合,统称为车辆路径问题(VRP)。由于OVRP问题也是NP难题,高效的精确算法存在的可能性不大,所以寻找近似算法是必要和现实的。遗传算法就是其中一种很好的解决方法。遗传算法是一种借鉴生物界自然选择和进化机制发展起来的高度并行、随机搜索算法。本文的重点是研究如何利用遗传算法求解开放式车辆路径问题。首先,分析了目前开放式车辆路径问题的研究现状,并在此基础上简述了本文要重点研究的最基础的问题类型——带装载能力限制的开放式车辆路径问题(COVRP)。然后,介绍遗传算法的基本理论和算法,并以COVRP为例,进行了问题分析、算法设计并且实现了此算法。特别地,在该算法中使用了一种新的交叉算子和几种改进策略。最后,分别比较和探索了使用该交叉算子后和使用各种改进策略后算法性能的改变情况,证明了该交叉算子和某些改进策略能有效提高遗传算法的性能。更进一步地,将结果与目前已有的其他算法结果相比较,分析了遗传算法解决OVRP的可行性和优劣程度。通过论文工作的研究与实现,作者认为:遗传算法在物流配送路径规划方面的优良特性,能够使问题得到较优满意解。但是,由于现实问题的复杂性,满足具体情况的遗传算法设计还有待进一步提高,理论分析有待进一步加深。