论文部分内容阅读
随着科技的迅速发展和社会的不断进步,物流企业获得的利润不断提高,物流的合理化以及高效化也备受人们重视。合理的制定物流配送方案,有效降低配送成本,具有至关重要的理论价值和现实意义。传统的车辆路径问题(Vehicle Routing Problem,VRP)中货物的配送和回收是单独进行的,车辆在这种单独的作业模式下很容易出现空载、重复运输等造成浪费资源的情况,为了避免出现这种情况,许多企业考虑同时对货物进行配送和回收两项工作内容,因此本文对装卸一体化车辆路径问题(Vehicle Routing Problem With Simultaneous Delivery and Pickup,VRPSDP)进行了研究。在对车辆路径问题国内外研究现况进行综述的基础上,本文对VRP问题的相关理论以及各类算法进行了梳理。针对VRP问题是NP难题,使用智能启发式算法来对其进行求解。主要研究内容如下:(1)基本装卸一体化车辆路径问题研究。首先,给出VRPSDP的数学模型,提出一种改进的细菌觅食算法求解此问题。针对装卸一体化车辆路径规划问题中容易出现超载情况,同时也为了更有效利用车辆的装载能力,在构造初始解时,依据优先安排送货需求较大且取货需求较小或推迟安排取货需求较大且送货需求较小的客户,我们对所有客户,按照“送货量/取货量”由大到小进行预排序,按照预排序次序使用插入算法将客户依次插入到路径中;在后期优化阶段,将细菌觅食算法的趋化操作与设计的路径间搜索算子和路径内搜索算子结合进行寻优,随机选择路径间搜索算子与路径内搜索算子作为趋化操作的方向,进行游动,不断更新路径,找到最优解;最后使用MATLAB软件进行仿真实验,通过Salhi和Nagy标准测试集来验证改进算法的性能,并与改进粒子群优化算法、节约启发式算法、广义节约启发式算法、扩展并行启发式算法进行对比分析,从整体上看,CMTX类算例有92%的算例优于对比算法,CMTY类算例有85%的算例优于对比算法,证明改进后的细菌觅食优化算法在求解VRPSDP问题上是可行的,为各个物流企业的路径规划问题提供一个较好的指导方案。(2)带时间窗的装卸一体化车辆路径问题(Vehicle Routing Problem with Simultaneous Delivery-Pickup and Time Windows,VRPSDPTW)研究。首先,建立了VRPSDPTW的数学模型,并提出基于模拟退火机制的自适应大邻域搜索算法来求解此问题。初始解构造时,基于客户节点位置分布的不同,本文使用两种方法进行构造,一种是基于K-means的贪婪插入法,一种是基于距离与时间加权的插入算法;在优化阶段,用自适应大邻域搜索算法中设计的删除算子和插入算子对初始解动态寻优,使用模拟退火机制控制解的更新;最后使用MATLAB软件进行仿真实验,运用VRPSDPTW的标准数据集验证算法的可行性,与遗传算法、并行模拟退火算法、离散布谷鸟算法以及基本人工鱼群算法、改进全局人工鱼群算法和两阶段算法进行对比,在与以上算法进行对比时,综合来看,在测试集Solomon算例中,R类算例有85%的算例优于对比算法,C类算例有91%的算例优于对比算法或与对比算法取得了一样的结果,RC类算例有77%的算例优于对比算法。因此,本文算法的性能是有效的,对于物流企业的配送方案可以提供一定意义的指导意见。