论文部分内容阅读
在经济全球化和信息化的浪潮中,现代的物流业已经从为社会提供传统的运输服务,扩展到以现代科技、管理和信息技术为支柱的综合物流系统。随着信息技术的发展,物流调度的优化问题已成为研究的一个热点问题。车辆路径问题装卸货问题及其所属的物流调度问题的研究从上个世纪六十年代就开始已经开始。经过近半个世纪的研究先后提出了TSP、VRP、PDP等问题,并针对性的提出了多种算法取得了一定的成果。本文首先讨论了在实际应用中的车辆调度优化理论和方法,总结分析了近二十年VRP研究所取得的一些成果,包括算法的原理和适用范围,对该问题的精确解法和启发式解法进行了分析比较。然后在这个基础上,探索了在现实的复杂的约束、目标函数下的车辆调度模型和算法。主要的工作有以下几方面: 1.分析了现实物流配送系统的业务流程和存在的问题,分析了现实问题中存在的复杂约束和目标。并结合现实的需求,建立了配送车辆路径调度问题的一般模型。为下一步算法的展开打下了基础。 2.根据该问题的特点,提出了一种道路网络自动生成算法以得到更加贴近现实的算例。然后基于道路网络信息,设计了一种多层次的优化算法,先在基础地理信息数据上进行预处理,并采用稀疏矩阵压缩技术、离线搜索、建立最佳路径库等方法,大大提高了算法的效率和灵活性。 3.分析了现实问题的复杂约束和目标,建立了车辆调度问题的形式化模型,包括简单约束模型和复杂约束的模型。根据各个层次的模型,提出了改进的节约算法求解问题。然后提出了一种基于字典序的剪枝搜索算法实现了对复杂约束问题的高效率搜索。并对算法的性能作了深入的分析与比较。 4.在VRP问题的基础上研究了装卸货问题区别VRP和PDP的不同。并对实际的时间窗约束的装卸货问题做了重点研究,基于解决VRP问题的同样思想,提出了全局优化的剪枝搜索算法。 5.针对大规模的VRP问题和PDP问题,在分析了精确解法种种局限性之后引入了聚类思想。讨论了基于欧氏距离定义的聚类算法的局限性,提出了一种基