一种基于时空距离的带时间窗车辆路径问题算法

带时间窗的车辆路径问题是典型的NP难题,一种常用的求解方法是先对顾客分组,后进行路径优化的两阶段启发式算法. 传统算法在顾客分组时主要考虑顾客的空间位置关系,但是忽略了顾客对服务时间窗口的要求. 本文同时考虑顾客的时间和空间特性,提出了一种基于时空度量的顾客分组方法. 在路径优化阶段,本文提出了一种禁忌搜索算法来进行求解,该算法中禁忌的对象不是解,而是这些解的目标函数值的区间,以便于提高收敛效率. 作为验证,本文以Solomon标杆问题集为算例进行演算,结果表明,在窄时间窗约束下,基于时空距离的两阶段启发式算法明显优于基于空间距离的算法,且部分算例的解达到了国内外已发表的最好解.     

时变单车路径问题建模及算法设计

讨论了一类时变单车配送路径优化问题。综合考虑车辆行驶速度随时间、路段不同而变化的特点,及车辆为多条路线上的客户提供服务时对车辆路径优化的影响,建立了以配送完成时间最早为优化目标的时变单车配送路径优化模型。在行驶时间满足FIFO规则下,设计了基于Inver-over操作的PSO启发式算法及满足贪婪配送策略下的动态规划精确求解算法,并讨论了增加贪婪补货策略的单车配送路径问题解与原问题解的关系。最后分别用两种算法对算例进行求解,并通过对求解优化结果及计算时间的对比分析验证了IOPSO算法的有效性。     

时变单车路径问题建模及算法设计

讨论了一类时变单车配送路径优化问题。综合考虑车辆行驶速度随时间、路段不同而变化的特点,及车辆为多条路线上的客户提供服务时对车辆路径优化的影响,建立了以配送完成时间最早为优化目标的时变单车配送路径优化模型。在行驶时间满足FIFO规则下,设计了基于Inver-over操作的PSO启发式算法及满足贪婪配送策略下的动态规划精确求解算法,并讨论了增加贪婪补货策略的单车配送路径问题解与原问题解的关系。最后分别用两种算法对算例进行求解,并通过对求解优化结果及计算时间的对比分析验证了IOPSO算法的有效性。     

考虑一致性约束的车辆路径问题综述

车辆路径问题是物流和交通运输领域的研究热点.近年来,为应对激烈的市场竞争,越来越多的企业开始关注如何在降低成本的同时保证服务效率和服务质量.实践表明提高车辆路径方案的一致性不仅可以提高服务效率,还能显著提高客户满意度.因此,考虑一致性约束的车辆路径问题(又称一致性车辆路径问题)应运而生.一致性车辆路径问题是相对较新的车辆路径问题变种,相关成果具有重要的实践和学术价值.随着多样化一致性约束的提出以及相关数学模型和优化方法的迭代更新,目前针对一致性车辆路径问题已有一定数量的研究积累.本文从车辆路径问题的分类、一致性车辆路径问题的背景介绍、模型、求解算法等方面对该问题进行了综述.在一致性车辆路径问题中,一致性约束主要有时间一致性、人员一致性和路线一致性要求.时间一致性和人员一致性约束较为常见,路线一致性约束则相对更为新颖.一致性车辆路径问题的求解方法以启发式算法为主,尤其是大、中型实例(时间周期5d,客户数量50以上)的求解;而部分精确式算法对中小型实例(时间周期3～5d,客户数量50及以下)也展现了良好的性能.     

城市交通车辆模糊路径的柔性选择策略

基于有限理性的思想,通过引入决策者主观偏好的概念,阐述了给定时间约束下车辆模糊路径的柔性选择策略;建立了该问题的模糊机会规划模型,并给出了一种启发式算法.以最小化剩余旅行距离为目标,用随机模拟方法探讨了决策者主观偏好值P＊对最终目标的影响.结果表明,约束时间一定时,在特定的路网中,存在最优的P＊值.     

基于拉格朗日分解的电动汽车充电路径优化

针对电动汽车充电路径优化问题,构建简单有效的车辆充电网络,考虑车辆剩余电量和充电站服务能力约束,以车辆行驶总时间最小为优化目标,建立基于多商品流的0-1整数规划模型.在拉格朗日分解框架下,构造所建模型的对偶问题,并利用次梯度算法对其求解.次梯度迭代过程中,对偶问题能够被分解为易处理的最短路径问题和半指派问题.通过应用标号算法求解最短路问题,设计有效的启发式方法求解半指派问题.仿真计算表明,求解算法能够在很短时间内达到非常小的优化间隙,验证了所提方法的可行性.     

带时间窗的随机需求车辆路线问题的模型研究

车辆路线问题是考虑在车队为一些有需求的顾客运送货物时如何安排行驶路线，从而使服务效率达到最高，在原有车辆路线问题的基础上，着重考虑车辆路线问题中顾客需求的随机性及顾客接受服务的时间窗约束，运用机会约束规划的方法，建立了新的随机模型，并用遗传算法进行启发式求解，得到了良好的数值解，为车辆路线问题的进一步研究提供了参考．     

蚁群算法在西餐连锁店配送路径中应用

西餐连锁店的路径优化是各连锁店食品配送路线的优化,要求满足各连锁店时间窗的约束,可抽象为带时间窗的车辆路径问题（VRPTW）.文中采用启发式算法对VRPTW求解.为正确衡量信息素和期望值浓度在进化的不同阶段对算法的贡献,引入了一种自适应转移策略来提高算法的求解效率,并通过综合考虑全局和局部信息的更新策略——蚁权策略进行信息素更新,加快算法的收敛速度.最后,通过11个经典VRPTW对该算法的性能进行了检验.并以大连市西餐连锁店为研究对象,运用本文所提出的蚁群算法求解大连市西餐连锁店的配送路线.     

基于量子蚁群算法的随机需求的动态车辆路径问题

针对随机需求的动态车辆路径问题,以最小化成本和最大化客户满意度为目标,采用两阶段建模,把动态车辆路径问题转换为静态车辆路径问题,将量子理论与蚁群算法结合并加以改进,用量子Hε门代替传统的量子旋转门实现对蚁群的更新.用Matlab7. 0软件实现数据仿真,验证了本文改进的量子蚁群算法是求解该问题有效的方法之一.     

带软时间窗的集货与送货多车辆路径问题节约算法

研究了物流配送中多车运输的集货与送货车辆路径规划问题,以增加时间惩罚费用的方式插入软时间窗约束,将租车费用、货车运输费用和时间惩罚费用三者之和最小作为优化目标,建立数学模型。采用启发式节约算法求解该模型,考虑时间惩罚费用和运输费用,比较每一配送节点上直接送货和间接送货的节约费用关系,求出最优配送路径。试验结果表明:当配送次数达到50次时,货车平均装载率仍能达到80%以上,该节约算法能减少货车空程行驶和租车次数,优化了全局费用。