论文部分内容阅读
随着物流业的迅速发展及信息一体化的介入,配送环节在整个物流系统的竞争中占据着决定性的作用。运输费用占据着物流费用的很大比例,设计合理有效的配送方案是降低物流费用的关键点[1]。对车辆科学的使用和调度可以缩短行驶路径、节约物流作业的时间、降低物流运作的成本,同时提高物流系统的管理效率、增强客户对物流环节的满意度[2]。因此,车辆路径问题(Vehicle Routing Problem,VRP)自从1959年被提出以来,一直成为热点研究领域[3]。目前在大规模VRP求解上还有很多问题值得探讨,为了使算法具有简单性有效性,本文以大规模单车场VRP和大规模多车场VRP为两类研究对象,针对在解决此类问题时算法较复杂的问题,对扫描法在VRP中的应用和改进展开研究。主要工作如下:1.为了解决包含大规模需求点的VRP中多个配送中心的选址问题,本文基于优化的思想,将扫描法应用在选址问题中提出了二次重心法,建立了一种数学模型,并用算例进行算法的仿真,验证了本文算法的有效性。2.针对大规模单车场和大规模多车场VRP中需求点覆盖区域过大的问题,本文以降低问题规模为阶段性目标,同时加入“需求点分布”这一考虑因素,设计了一种划分区域的环形分区法,并根据这种分区思路给出几组具体参数的举例。3.针对单车场VRP问题,本文结合环形分区法,对扫描法在单车场VRP中的应用进行了改进,提出了一种新算法,并用算例进行算法的仿真,对比了新算法与传统扫描法的路程结果,验证了本文算法的有效性。4.针对多车场VRP问题,建立了一种数学模型,分别针对非开放型VRP和开放型VRP问题设计了两种扫描法应用在此类问题中的两阶段算法,并对比了新算法与传统两阶段算法的路程结果,验证了本文算法的有效性。