基于改进蚁群算法求解带软时间窗的车辆路径问题

针对带软时间窗的车辆路径问题(VRPSTW),建立以配送成本为优化目标的混合整数规划模型,提出一种改进蚁群算法(IACO)求解该问题。在传统蚁群算法(ACO)的基础上,改进蚂蚁状态转移概率公式,通过自适应调整信息素挥发系数改进信息素更新策略,设计插入算子和交换算子嵌入变邻域局部搜索,并设置开始和退出局部搜索的条件,更新当前局部最优解。选取Solomon标准测试集里3类不同规模的算例,测试算法改进效果,以客户规模为100的C类算例验证所提算法求解较大规模算例的可行性,并与传统蚁群算法以及其他文献中的算例结果进行对比。实验结果表明,改进蚁群算法的寻优能力高于其他算法,求解得到的最优配送方案能够实现更低的车辆配送成本,从而验证了改进蚁群算法的有效性。

基于时空聚类的带时间窗车辆路径规划算法

针对带时间窗车辆路径问题,设计了一种同时考虑顾客的时间和空间邻近性的路径改进方法。首先设计了一种顾客间时空距离的表达方式,然后利用遗传算法对顾客点进行时空聚类,并将聚类结果应用于路径调整中,使得顾客尽可能被加入到时空距离近的顾客所在路径中,这样既能有效减小搜索范围,又能更快到达更好的解。以含1000个点的标准问题集作为算例,计算结果表明,与不采用时空聚类的方法相比,该算法能在更短的时间内取得更好的解,显示了在解决大规模车辆路径问题时具有很好的潜力。

带时间窗装卸一体化车辆路径问题的混合离散粒子群优化算法

为了同时实现总配送成本最低、车辆数最少和车辆行驶距离最短等目标,考虑车辆指派成本及运输路径成本的相对重要性,建立了带时间窗装卸一体化车辆路径问题的混合整数规划模型。针对该问题搜索空间的离散性和求解算法的局部收敛性,提出了一种混合离散粒子群求解算法。算法基于客户排列的直观无分段大路径解表示法,采用改进深度优先搜索分割法对问题解进行解码与评价;嵌入一种变邻域下降搜索程序并在个体粒子每次迭代时以一定概率选择执行,利用混合粒子群算法在多邻域深度搜索和在全局空间广度搜索进行寻优,同时应用模拟退火思想和比例选择性变异最差个体来改善个体搜索停滞现象。采用两个不同目标算例进行寻优测试,验证了所提算法的可行性和有效性。

求解VRPBTW的变邻域搜索算法

以电子商务环境下物流配送为背景,建立了带有时间窗和回程载货约束的车辆路径问题优化模型,设计了改进的变邻域搜索求解算法.该算法采用改进的Braysy顺序插入法生成问题初始解,再根据变邻域搜索算法机制应用4种不同搜索范围的局域搜索算子对初始解进行改进.通过对多个算例的求解实验,并与采用一般流程的变邻域搜索算法进行比较,结果表明所提出的变邻域搜索算法的求解效果明显优于采用一般流程的变邻域搜索算法,是求解该类问题的有效算法.

软硬时间窗共存装卸一体化车辆路径问题的混合离散粒子群优化算法

文章针对软硬时间窗共存装卸一体化车辆路径问题(vehicle routing problem with simultaneous delivery and pickup under coexistence of soft and hard time windows,VRPSDPCSHTW)建立了包含车辆固定出行成本、运输成本和惩罚成本的数学模型,提出了一种混合离散粒子群优化算法。针对基本离散粒子群算法容易早熟收敛而陷入局部最优等问题,内嵌一种变邻域下降局域搜索方法,并在一定概率下执行以加强种群搜索能力,最后通过3个算例的仿真分析进行了算法验证。

变邻域模拟退火算法求解速度时变的VRPTW问题

本文在经典的带时间窗的车辆路径问题(VRPTW)的基础上,考虑不同时间段车辆行驶速度不同的情况,研究速度时变的带时间窗车辆路径问题(TDVRPTW),使问题更具实际意义。本文用分段函数表示不同时间段下的车辆行驶速度,并解决了速度时变条件下行驶时间计算的问题。针对模拟退火算法(SA)在求解VRPTW问题时易陷入局部最优解,变邻域搜索算法(VNS)在求解VRPTW问题时收敛速度慢的问题,本文将模拟退火算法以一定概率接受非最优解的思想和变邻域搜索算法系统地改变当前解的邻域结构以拓展搜索范围的思想结合起来,提出了一种改进的算法--变邻域模拟退火算法(SAVN),使算法在退火过程中一陷入局部最优解就改变邻域结构,更换搜索范围,以此提升算法跳出局部最优解的能力,加快收敛速度。通过在仿真实验中将SAVN算法的求解结果与VNS算法、SA算法进行对比,验证了SAVN算法确实能显著提升算法跳出局部最优解的能力。

混合优化算法求解同时送取货车辆路径问题

为了给各物流企业在车辆配送路径规划方面提供合理有效的决策支持,针对单配送中心的配送模式,研究带时间窗约束的同时送取货车辆路径问题(VRPSDPTW),建立以总配送成本最小化为目标的数学模型。根据模型的特征,提出基于模拟退火(SA)与自适应大规模邻域搜索(ALNS)相结合的混合优化算法(SA-ALNS)。采用基于时间与距离加权的插入启发式算法构造问题的初始解;引入多种删除、插入算子,以自适应选择策略进行路径优化,并通过反馈机制,逐渐调整各操作算子被选择的概率,使算法更倾向于选择寻优效果较好的算子;使用模拟退火机制的Metropolis准则控制解的更新。仿真实验中测试了56个大规模算例,对比了p-SA算法、DCS算法和VNS-BSTS等其他智能优化算法并进行统计分析,结果证明该算法在求解带时间窗约束的同时送取货车辆路径问题的可行性和优越性,研究成果极大丰富了车辆路径问题(VRP)的相关研究。

改进模拟退火算法在物流优化中的应用

考虑到客户对送货时间的要求,在现有物流优化中无时间约束的选址-库存-路径模型上进行拓展,引入了软时间窗,建立了带软时间窗的选址-库存-路径问题模型,并设计了内嵌禁忌搜索的改进模拟退火算法对模型进行求解。最后,实例演算的结果证实了模型的科学性和算法的有效性,通过与禁忌搜索和模拟退火算法分别进行比较,表明了本文的算法较这两种算法的优越性。

开放式带时间窗车辆路径问题及变邻域搜索算法

针对配送服务中开放式带时间窗车辆路径问题,构建了最小化车辆行驶成本的集分割模型,并提出变邻域搜索算法进行求解。该算法包括抖动和邻域搜索两个阶段,其中,抖动阶段通过当前解与种群历史最优、与个体历史最优之间的路径重连来实现,邻域搜索阶段通过同一条路径内以及不同路径间的交换、插入、2-opt三个操作算子来实现。通过与已有文献进行对比,结果表明该算法在求解开放式带时间窗车辆路径问题时,能得到更高质量的解,而且算法的收敛性和稳定性均较好。由此验证了该算法的可行性和有效性。

基于聚类的变邻域模拟退火算法求解VRPTW

为求解带时间窗车辆路径问题(vehicle routing problem with time window,VRPTW),针对启发式算法求解路径优化问题的精确度低、时间长等缺点,提出了一种基于密度聚类方法的变邻域模拟退火算法(simulated annealing with variable neighborhood based on density-based spatial clustering of application with noise,DBSCAN/SAVN)。DBSCAN/SAVN算法首先用DBSCAN聚类算法确定出若干簇类来降低数据规模;针对模拟退火算法中的metropolis准则在求解VRPTW时收敛速度慢、容易陷入局部最优解的缺点,使用3种扰动算子构造出变邻域模拟退火算法的邻域结构;最后通过改进的模拟退火算法对簇类中的小规模车辆路径问题进行求解。通过仿真实验与其他优化启发式算法相比,DBSCAN/SAVN求得解的质量更好,具有可靠的全局稳定性。

带时间窗偏好的同时配集货且需求可拆分车辆路径问题

针对带时间窗偏好的同时配集货且需求可拆分车辆路径问题,最小化派遣成本、理货成本、时间窗惩罚成本以及油耗成本之和,建立数学模型。设计混合遗传变邻域搜索算法求解问题,在算法中引入时空距离的理念,首先用最近邻插入法和Logistic映射方程生成初始种群;然后利用变邻域搜索算法的深度搜索能力优化算法;提出自适应搜索策略,平衡种群进化所需的广度和深度;设计拆分准则,为各客户设置不同的拆分服务量;提出确定车辆最优出发时间的时差推移法,减少车辆在客户处的等待时间;最后通过多组算例验证本文模型和算法的有效性。

多车场带时间窗车辆路径问题的改良自适应大邻域搜索算法

针对多车场带时间窗车辆路径问题(MDVRPTW),提出一种改良自适应大邻域搜索算法(IALNS)。首先,在构造初始解阶段改进一种路径分割算法;其次,在优化阶段利用设计的移除和修复启发式算子相互竞争择优选取算子,为各算子引入评分机制,采用轮盘赌方式选取启发式算子;同时,将迭代周期分段,动态调整各周期内的算子权重信息,有效避免算法陷入局部最优;最后,采取模拟退火机制作为解的接受准则。在Cordeau规范算例上进行实验,确定IALNS的相关参数,将所提算法求解结果与该领域其他代表性研究成果对比。实验结果表明,所提算法与变邻域搜索(VNS)算法的求解误差不超过0.8%,在某些算例上甚至更优;与多相位改进的蛙跳算法相比,算法的平均耗时减少12.8%,所提算法在绝大多数算例上运行时间更短。因此,验证了所提算法是求解MDVRPTW的有效算法。

多车场带时间窗车辆路径问题的变邻域搜索算法

多车场带时间窗车辆路径问题是车辆路径问题集合中的一个极为复杂、且仍未得到较好解决的问题。针对这一问题,建立了它的整数规划数学模型,提出了一种改进型变邻域搜索算法。该算法在初始解的构造阶段采用聚类方法完成客户的分配,运用混合算子进行局部搜索,通过后优化过程增强寻优效果,引入模拟退火模型对新解的接受进行控制。最后,在Cordeau提出的标准用例上对改进型变邻域算法进行了实验,实验结果更新了大部分目前该问题的最优解,并在算法的稳定性和求解时间上体现出一定优势。实验表明,该算法是一种求解多车场带时间窗车辆路径问题的有效方法。

顾客时间窗变化的多车场车辆调度干扰管理模型研究

为解决物流配送过程中某顾客时间窗变化而导致的物流配送难以按照原计划实现的难题,运用干扰管理方法,针对多车场带时间窗的物流配送车辆路径问题,提出包含顾客配送时间总偏离度、配送总成本、新路径方案与初始路径计划偏差量、最长行驶时间违反总量4个因素的扰动程度度量方法;以顾客时间窗变化这类干扰事件发生时的问题状态为基础,以系统整体扰动最小化为目标,建立问题的目标规划数学模型;针对这一复杂模型,提出基于特定邻域结构及其寻优概率的变邻域搜索算法;最后在标准算例上使用变邻域搜索算法与其他文献算法进行比较分析,结果表明该变邻域搜索算法对于干扰事件发生后的车辆路线重排结果在系统整体扰动程度方面明显优于其他文献的算法。