三维装载约束下基于运输资源共享的车辆路径问题

针对车辆路径问题研究在三维装载方式和运输资源共享模式结合方面存在的不足,提出三维装载约束下基于运输资源共享的车辆路径优化策略。首先,结合客户点地理位置特征和服务时间窗属性确定多个服务周期,建立了多个服务周期内物流运营成本最小化和车辆使用数最小化的双目标优化模型。其次,设计了集成k-means时空聚类的Clarke-Wright—非支配排序遗传算法求解模型,该算法引入Clarke-Wright节约算法以提高初始解的质量,并结合非支配排序遗传算法提高了混合算法寻找优化解的全局和局部空间搜索能力。最后,结合实例数据对所提方法进行了计算验证,给出了三维装载约束下基于运输资源共享的车辆路径优化方案并探讨了不同车厢空间分区模式下物流运营总成本、车辆使用数、车辆平均装载率和车辆平均使用频次的变化情况。研究表明:根据客户需求货物种类数和货物规格划分配送车辆装载空间,可有效降低物流运营总成本,减少配送车辆使用数,增加车辆共享频次和有效提高车辆平均装载率,并可为基于运输资源共享的三维装载物流网络优化问题提供决策参考和方法支持。

分支定价方法求解带二维装箱约束的车辆路径问题

面向家具、电器等货物的物流配送场景,研究带二维装箱约束的车辆路径问题(2L–CVRP),构建了2L–CVRP的混合整数线性规划模型.为求解大规模2L–CVRP,构建了该问题集合划分模型,提出基于分支定价的方法.针对分支节点的松弛模型,基于列生成策略将其分解为线性规划主问题、带资源和二维装箱约束的最短路径子问题,并提出基于ng-route松弛策略的标签算法和基于禁忌搜索的装箱算法有效求解复杂子问题.仿真结果表明,提出的方法可高效求解大规模2L–CVRP,其中ng-route松弛策略能有效提升算法求解效率,研究成果为装箱约束下大规模车辆路径问题的高效求解提供了有效途径.

基于改进的禁忌搜索算法求解带2维装箱约束的低碳车辆路径问题

同时考虑2维装箱和车辆路径2个NP难问题,以碳排放量为目标函数,对低碳环境下带2维装箱约束的车辆路径问题进行研究.求解思路是以禁忌搜索算法(Tabu Search,TS)为主要框架,然后基于贪心的思想采用4种启发式装箱策略生成初始解,并通过改进编码解码方式以及使用动态增长的禁忌长度对TS算法进行改进;由给出算例的计算结果可知,改进的禁忌搜索算法对于求解该类问题具有一定的优越性.

混合模因算法在求解带装箱约束的车辆路径问题中的应用

带有回程取货约束的车辆路径问题(Vehicle Routing Problem with Backhauls, VRPB)和二维装箱问题(twodimensional Bin Packing Problem, 2L-BPP)是两个经典的组合优化问题,在融合两者的基础上,本文提出了一种新的组合最优化问题,即2L-VRPB.在该问题中,车队的最优路径规划和货物的最优装载设计需要同时进行考虑,该问题的优化目标是在满足所有客户的送货和取货需求的前提下,为车队中的车辆制定尽可能最优的行驶路线和货物装载方案,使得车队的总的服务成本最低.该问题在实际生活中有着广泛的应用场景,例如在设备维修和零售行业的货物运输中可经常遇到此类情形,但是文献中关于此类问题的研究论文仍然较少.为了求解2L-VRPB问题,我们提出了一种具有自适应性机制的混合模因算法(HMA),该算法采用改进的模因算法(IMA)来规划最优路径,并通过增强的组合装箱算法(Multi Pack)来设计货物的最优装载方案.在实验环节,通过在VRPB问题的Goetschalckx & Jacobs-Blecha测试算例和2L-VRPB问题的Gendreau测试算例上设计对比实验,我们验证了混合模因算法在求解VRPB和2L-VRPB问题时的鲁棒性和有效性.

两阶段优化算法求解绿色装箱车辆路径问题

带二维装箱约束的绿色开放式车辆路径问题(green open vehicle routing problem with twodimensional loading constraints,2L-GOVRP)是绿色开放式车辆路径问题和二维装箱问题的集成。以最小化燃油消耗量为优化目标建立了2L-GOVRP模型,并提出一种两阶段优化算法(two stage optimization algorithm,TSOA)进行求解。TSOA的第一阶段,针对车辆路径问题,设计自适应鲸鱼优化算法(adaptive whale optimization algorithm,AWOA)进行求解,从而确定车辆初步配送路径(即2L-GOVRP的初始解),并采用4种变邻域局部操作进行局部搜索。TSOA的第二阶段,针对二维装箱问题,设计融入扰动机制的天际线填充算法(skyline filling algorithm combined with disturbance mechanism,SFA-DM)优化装箱过程,从而确保所有货物能够合理装箱。通过对不同客户规模测试数例的仿真实验和算法比较,验证了TSOA可有效求解2L-GOVRP。

装载弱异性货物入厂物流的车辆路径方案优化决策

针对某工厂大量弱异性货物取货的物流实践,研究了入厂物流路径优化决策问题.根据弱异性中小尺寸货物装车堆码特点,通过分析路径-装箱复合问题的是否托盘单元化、托盘类型、装车方式和车型四种决策结点,建立了托盘单元化再装车、一维堆码装车和三维优化装车三种不同方案下的模型及算法,涉及制造托盘装箱问题、需求可拆分及带装载约束的车辆路径问题等.应用实例数据,给出了各模型总里程、车辆数和满载率结果的比较,并进行了物流作业成本的比较分析.这一分析基于多模型优化和物流作业频次、时间与成本综合模型,有助于多种不同约束条件下的车辆路径问题的决策与应用.

考虑随机旅行时间与二维装载约束的越库配送车辆路径优化

面向越库配送模式下二维装载和车辆路径联合优化,考虑现实配送过程的不确定性因素,提出考虑随机旅行时间和二维装载约束的越库配送车辆路径问题.基于蒙特卡洛模拟与场景分析方法,建立以运输成本、车辆固定成本以及时间窗期望惩罚成本之和最小化为目标的带修正随机规划模型.继而根据问题特征,设计改进的自适应禁忌搜索算法和基于禁忌搜索的多重排序最佳适应装箱算法进行求解.其中,改进的自适应禁忌搜索算法在禁忌搜索算法的基础上引入自适应机制,对不同邻域算子进行动态选择,并提出基于移除-修复策略的多样性机制以增强算法的寻优能力.数值实验表明,所提出的模型与方法能够有效求解考虑随机旅行时间和二维装载约束的越库配送车辆路径问题,自适应与多样性机制能一定程度上增强算法的全局搜索能力.

考虑车辆限行和装箱约束的车辆路径优化方法

在实际配送过程中,考虑到部分城市道路存在限制大型配送车辆通行的现状,以及运输途中车厢内物品满足后进先出等装载约束能有效提高装卸效率的特点,将车辆限行和二维装箱约束加入到需求可拆分车辆路径问题中。同时考虑到车辆的使用成本和行驶成本,以车辆总配送成本最小为目标构建考虑车辆限行和二维装箱约束的需求可拆分车辆路径问题数学模型,设计了启发式算法来求解该模型,其中模拟退火算法确定需求拆分下的车辆配送路径,且在当前最优解判断时调用BLF算法检验物品的二维装箱约束,来减少频繁调用BLF算法的时间。数值案例验证了模型和算法的实用性,且所提出的算法的求解结果波动不大于0.8%,能在合理的时间范围内求解得到较好的配送方案,在车辆限行区域内采用双车型配送能节省15.17%~31.27%的总配送成本。

带二维装箱约束的物流配送车辆路径问题

现实物流活动中大量存在的易损、易碎物品的运输问题属于带二维装箱约束的物流配送问题,该问题是二维装箱问题与车辆路径问题这两个经典难题融合之后的一个新问题.针对这一问题,在对其进行明确定义的基础上,建立了数学模型,提出了解决该问题一个Memetic算法,对算法中的几个关键算子:深度优先的启发式装箱方法、染色体的编码方式及其路径分割程序、初始解的生成方法、交叉算子、局部搜索算子,进行了详细的阐述.通过初步的实验,确定了Memetic算法的最佳参数配置;然后在Iori提出的30个顾客数在20-199个标准算例上对算法的鲁棒性、求解的质量、以及求解性能等几项指标进行了测试,并与文献中的求解结果进行了比较.试验结果表明,该Memetic算法大大提高了现有算法的性能及求解结果的质量.

考虑二维装箱约束的多车场带时间窗的车辆路径问题模型及算法研究

研究包含时间窗、多车场因素的二维装箱车辆路径问题,建立相应的数学模型,并提出求解该问题的一种新的混合算法,混合算法由量子粒子群算法和引导式局部搜索算法组成。其中,量子粒子群算法用于求解车辆路径问题,引导式局部搜索算法用于求解可行装箱方案。在引导式局部搜索算法中,提出一种基于最小浪费原则的启发式装箱规则,以灵活确定待装货物和装货空间之间的匹配关系,减少重复确定装箱方案所消耗的时间。设计了两组数值试验:第一组基于标准算例库,并将混合算法计算结果与已有文献中的结果进行对比;第二组基于随机生成的新算例,新算例给出多车场和时间窗数据,用于演示混合算法对新模型的计算过程和计算结果。两组数值试验的结果表明,混合算法在效率和性能方面均有较好的表现,计算结果和计算时间均优于已有文献,且混合算法能够较好的求解包含时间窗、多车场因素的二维装箱车辆路径问题模型。

考虑卸载顺序约束的成品油二次配送车辆路径问题

研究考虑卸载顺序约束的成品油二次配送车辆路径问题,已知油库使用容量有限的多隔舱运输槽车为加油站配送多种类型的成品油,每个隔舱只能装载一种特定的油品,且装载到各个隔舱中的油品具有固定的卸载顺序.已知加油站对各种油品的需求量,假设每个加油站对同一种油品的需求只能由一辆车配送,考虑配送车辆的固定动用成本和运输成本,以总配送成本极小化为目标建立该问题的混合整数规划模型,并设计求解模型的自适应大邻域搜索启发式算法.利用不同规模的算例进行模拟计算与分析,从而验证算法的有效性.实验结果显示:对于小规模算例,大邻域搜索启发式算法能够以较高的概率得到全局最优解;对于中、大规模算例,大邻域搜索启发式算法可以在短时间内得到近似最优解,近似比不超过1.2.所提出的模型和算法可为石油公司制定成品油二次配送计划提供理论依据和决策支持.

考虑LIFO约束的2L-CVRP优化

针对精准管控的现代物流需求,为实现二维装载约束下的车辆路径问题(2L-CVRP)求解,分别设计了最少开放空间(LOS)的货物装箱方法与带有回火过程的模拟退火操作(ISA),并开发了ISA-LOS算法。LOS装箱方法通过容器内的剩余开放空间数量与格局状态评价,构造综合适应度,引导货物循环装载。给出了基于Skyline的开放空间生成策略,能够迅速生成放置效果适应度,支撑LOS装箱方法高效运行。考虑车辆载重与装载的双重约束,ISA通过回火过程引入,增强了算法的全局搜索能力,有利于寻优质量的提升。结合不同模块的加速结构与参数设置,完成了整体算法的构建。针对标准算例的对比实验表明,ISA-LOS能够有效求解2|SO|L约束下的2L-CVRP,且运算结果接近于已知文献最优解。同时,算例的寻优过程与装载效果验证了ISA与LOS的有效性,其调度方法能够为相关问题优化提供参考。