不确定需求环境下的路径-装载协同优化研究

来源:《系统工程理论与实践》时间:2022-01-18

一、研究背景与意义

车辆路径问题 (Vehicle Routing Problem,VRP) 和背包装载问题 (Three-Dimensional Knapsack Loading Problem, 3D-KLP) 都是传统的物流优化问题,同时又都是典型的NP难题。国内外学者在早期研究中一般都作为独立问题分别研究。早在1959年,Dantzig和Ramser就在《Management Science》首次提出了车辆路径问题,他们研究了散装油库到各个服务站之间,油库车队的最佳路径选择问题。此后,各国学者在此基础上不断丰富VRP的模型和算法。对于3D-KLP,自从1965年Gilmore和Gomory做出了开创性工作以来,3D-KLP逐步成为各国学者关注的热点问题。

尽管VRP与3D-KLP作为两个独立的优化问题和NP难题发展至今,其理论及应用的研究均取得了引人注目的成绩。然而,运输的“路径”和“装载”在实际物流运输调度中是两个密切关联的问题,只有协同优化这两方面问题才既能保证车辆的运输成本最低、车辆的派遣数量最少,还能保证货物合理的装入车厢并具有较高的车厢装载率。基于这种考虑,2006年Gendreau等人在美国管理运筹学会INFORMS会刊《Transportation Science》首次提出了VRP与3D-KLP协同优化问题,他们考虑了三维装载和带有容量约束的车辆路径协同优化问题,同时该问题考虑了装载过程中的许多实际约束,如易损性、支撑性和后进先出 (LIFO) 约束。此后,国内外许多学者不断对VRP与3D-KLP协同优化进行研究和完善,主要聚焦于三个方面:(1)确定优化目标方面的研究;(2)影响因素方面的研究;(3)求解算法方面的研究。然而,以上研究主要集中在确定性需求环境下的配送优化问题,而对于将VRP与3D-KLP协同应用于不确定需求环境和多车型运输的研究则较少。本文以不确定需求环境下的循环取货模式为研究对象,综合考虑多车型的车辆路径和多种类货物的车厢装载两个优化过程的协同优化调度问题,具有理论和现实双重研究意义。

二、主要内容

本文研究的不确定需求环境下的循环取货问题,是指有一个集拼中心、多个供应点,每个供应点可能供应一种货物也可能供应多种货物,集拼中心拥有多种不同类型的箱式取货车辆,每种类型的车辆有多台。主要内容如下:(1)在解决问题方面,在物流需求环境不确定情况下,将VRP与3D-KLP进行组合并建立协同优化调度方案;(2)在模型构建方面,确定每种车型的车辆路径和车厢装载的单车优化方案集合,将执行不同方案的车辆数作为物流调度的决策变量,根据实际需求量为装载约束条件,建立路径-装载协同物流调度优化模型 (3KL-CVRPCSO);(3)在求解算法方面,首先针对求解各车型车辆的单车最优路径-装载方案集,设计了基于遗传算法的混合粒子群优化算法和启发式正交二叉树搜索算法。其次针对求解3KL-CVRPCSO模型设计了多阶段算法HPGBT。通过与Bortfeldt A等人2020年在《European Journal of Operational Research》中的优化结果和企业实际案例的应用两方面进行了比较与验证,达到了理想的效果。研究问题的框架如图1所示。



图1   问题框架图

在考虑多车型车辆的行驶路径和车厢装载两个优化过程的基础上,建立了基于单车最优路径-装载复合方案为决策单元的协同优化模型3KL-CVRPCSO。该模型主要由三部分构成,第一部分以最小化取货车辆的总行驶路程作为目标函数,构建车辆路径模型;第二部以车厢的最大容积作为背包容量,建立以最大化装入车厢内货箱的总体积为目标函数的车厢装载模型;第三部分以各车型车辆的单车最优路径-装载方案作为决策变量,以实际货物需求量作为约束条件,建立以最小化派遣的总车辆数为目标函数的路径-装载协同优化模型。利用基于遗传算法的混合粒子群优化算法和启发式正交二叉树搜索算法构建了多阶段算法,对模型进行求解。多阶段算法的基本框架如图2所示,由车辆路径、车厢装载及协同优化3部分组成。



图2   多阶段算法的基本框架图

最后通过方法比较和实际案例的应用两方面的研究与验证,证明了本文所提出的模型和算法的突出的优化性能及解决实际问题的能力。

三、主要结论与建议

(1)本文提出的3KL-CVRPCSO多车型优化模型与传统的单一车型调度优化模型相比,能够以更少的车辆完成同样的取货任务;
(2)同时考虑车辆路径和车厢装载两个优化过程的3KL-CVRPCSO模型,能够显著的减少车辆的总行驶里程和提高车厢的装载率,能够有效地解决企业生产过程中的循环取货问题,可以根据企业在不确定情况下的实际需求提供多车型最优路径-装载复合最优调度方案。
(3)本文还提供了一种解决不确定性管理问题的思路和方法。

四、边际贡献与未来拓展

本文的边际贡献在于,提供了一种解决不确定性管理问题的思路和方法,可以概括为:以诸多确定性方案为“建筑砖块”,根据不确定需求,灵活搭建以方案数为决策变量的最优组合结构。

未来拓展,本文的思想和方法可以普遍运用于解决不确定性管理问题,特别是结合大数据沉淀的好方案作为基本单元(建筑砖块),根据不确定性实际问题,快速搭建以各个“好方案”为单元模块的最优组合,从而逐步建立“以确定性方案解决不确定性问题”的新的管理方法体系。

 

本文摘编自《系统工程理论与实践》第41卷第10期论文《不确定需求环境下的路径-装载协同优化研究》,点击链接下载全文:http://www.sysengi.com/CN/abstract/abstract112962.shtml

作者:李彤,大连理工大学经济与管理学院,商学院教授;崔晶,大连理工大学经济与管理学院,商学院硕士研究生。