在线组建协作配送联盟中企业成本节约相对量估算方法研究

企业参与在线协作配送联盟的重要决策依据是成本的节约程度,但计算该信息需要求解2~N-1个(N为企业数)类似多配送中心车辆路径问题的复杂难题,且在线协作联盟组建允许计算的时间十分有限.本文针对该难题,提出了一种估算协作配送问题结果的快速方法.首先,基于合作博弈中经典成本分摊方法,证明得出了计算过程中采用估算方法的可行性;然后,基于Beardwood研究的包含n个点的旅行商问题最优解路径长度,会近似等于α(An)~(1/2)的结论(α为参数,A为n个点的分布面积),提出了能够根据各企业顾客位置、分布区域面积等信息,预估协作配送问题目标函数结果的方法;最后,分别采用本文方法和传统优化方法求解了大量的实例和算例.结果表明:本文提出的方法计算速度迅速且质量准确,与传统方法相比耗时几乎可以忽略不计,能够满足在线实时计算的要求;估算的企业节约成本相对量误差均在10%之内,并且问题规模越大误差越小.     

协作车辆路径问题距离和能耗节约量理论边界研究

从理论角度研究协作车辆路径中能够节约的配送距离和能耗量，对协作配送的实际运营具有重要指导意义。提出了低碳协作车辆路径问题(LCCVRP)模型。从理论角度证明了在完全不协作状态下LCCVRP 的最优解与完全协作状态下相比，前者的最优路径长度为后者的倍，(为所有配送中心总数量)，由于能耗量与路径长度高度正相关，故能耗量指标具有类似规律。另外，设计了由贪婪算法和大邻域算法构成的两阶段算法。最后，基于多配送中心VRP (MDVRP)的标准算例，设计了33个LCCVRP 算例，并采用设计的两阶段算法求解，得到的求解结果验证了上述理论证明的合理性和模型与算法的有效性，设计的两阶段算法求解质量与已知最优解的平均偏差仅为0.1%左右。     

顾客参与企业协作回收物流的回馈积分激励机制研究

企业通过协作回收可以获得成本节约,但现实中,顾客可能偏好由原企业服务而拒绝协作,这会导致协作增益损失,甚至无法协作,因此企业有必要采取策略激励顾客参与协作.本文考虑企业回馈给顾客积分激励,通过合理量化顾客协作贡献,设计有效的顾客协作激励机制.首先,考虑顾客协作概率及协作贡献,以企业期望利润最大化为目标,构建激励模型及流程;其次,构建考虑顾客参与意愿的协作回收车辆路径问题模型,求解企业成本节约,量化顾客的协作成本节约贡献;然后,基于顾客协作贡献及激励模型,计算最优积分激励值,以实现顾客协作的有效激励;最后,通过数值实验对激励机制及模型的有效性进行了验证.结论如下:相较无激励情形,一般情况下,积分回馈激励机制下企业期望利润和顾客协作意愿具有显著提高;顾客对激励的敏感程度及初始协作意愿越高,经激励后,顾客协作意愿和企业期望利润也越高;此外,顾客对激励的敏感程度越高,初始协作意愿越低,企业越有必要提高激励预算,以获得更优激励效果.因此,在协作回收物流中,设计合理的顾客协作激励机制是有必要的,同时,本研究可以为企业实际协作中决策顾客激励值提供依据.     

考虑道路坡度因素的低碳VRP问题模型与求解策略

经典车辆路径问题（vehicle routing problem，VRP）模型不考虑道路的坡度，通常以最小化车辆行驶总距离、总耗时或派送车辆数为目标函数. 在考虑道路坡度因素的基础上，提出了以配送车辆总能耗最小为目标的低碳车辆路径问题模型 （energy consumption minimizing low-carbon VRP，ECM-LCVRP）；然后，以带能力约束的车辆路径问题 （capacitated VRP，CVRP）为参照，分析了 ECM-LCVRP 的解空间大小及基本算法改进法则在ECM-LCVRP 中的执行复杂度，发现ECM-LCVRP较CVRP更加难以求解，并且分析了不同坡度下 ECM-LCVRP 和 CVRP 的区别与联系；另外，基于配送方案的能耗值与行驶距离正相关的规律，提出了求解不同道路坡度环境下 ECM-LCVRP 的双目标策略 （two objective strategy，TOS）；最后，设计了40个 ECM-LCVRP 算例，并采用综合了算法基本改进规则的混合局部搜索算法 （hybrid local search，HLS）和HLS+TOS 两种方式求解，求解结果表明：在不同的运算时间内，TOS 策略均能够有效地提高HLS的求解质量，且求解时间越短，TOS的效果越明显.     

求解TSP问题的最近邻域与插入混合算法

研究了求解旅行商问题(TSP)的构建型启发式算法中的最近邻域算法和插入算法的特点, 集最近邻域算法求解速度快、插入算法求解质量高的优点, 提出了一种最近邻域与插入混合算法. 分析了混合算法的合理性、复杂度及参数取值, 并分别采用以上三种算法求解了TSPLIB标准库中多个算例, 结果表明混合算法的求解速度接近最近邻域算法, 对城市数量小于1000的小规模TSP问题的求解质量与插入算法相当, 而对大规模TSP问题的求解质量明显优于插入算法.     

基于平台的在线大规模协作配送联盟拆分策略研究

基于平台的在线协作配送模式,容易形成大规模联盟,成本分摊时所需2n-1个子联盟成本值的数量呈指数增长,难以在合理时间内计算出成本分摊方案.基于此,文章构建成本最小化协作配送模型来分析联盟拆分的必要性,通过动态规划思想求解拆分方案种类,分析拆分的复杂性,借助网络图提出了先依据顾客地理位置分布、再根据配送区域重叠度,快速将大规模联盟拆分成数个小规模联盟的两阶段拆分策略,从而减少子联盟数量.最后,通过数值实验和实例分析,对两阶段拆分策略的有效性进行验证.结果表明:1)传统方法求解子联盟成本C(S)耗时28.15 h,而采用两阶段拆分策略后,在实验电脑上基于三阶段算法仅需64.57 s; 2)文章提出的第二阶段拆分策略所得方案与精确拆分方案的偏差不超过8%,求解质量较优; 3)采用第二阶段拆分策略将规模为30的大联盟拆分后,成本分摊输入数据计算耗时不到1 h.文章提出的大规模协作配送联盟两阶段拆分策略能够极大缩短耗时,在合理时间内计算出成本分摊方案.更重要的是,文章研究思路可以为其他大规模合作博弈问题提供启发.     

一种求解协作配送成本分摊问题核仁解的近似迭代算法

协作配送问题是典型的组合优化合作博弈问题,也可称为协作车辆路径问题,其核心问题之一是确定公平合理的成本分摊方案.其中核仁解由于具有唯一性和公平性等特点,是成本分摊领域中公认的科学分摊方案.本文提出了一种近似求解协作配送问题核仁解的方法.首先分析证明了当顾客位置分布均匀,从理论上协作配送成本分摊问题会是凸博弈问题,然后,基于凸博弈的核仁解会等同于预内核解的理论,提出了一个能够求解凸博弈问题核仁解的迭代逼近算法(approximate iterative algorithm,AIA),分析了AIA算法的复杂度为O(n~42~n),为此又提出了AIA的有效提速策略,可将AIA的复杂度降低至多项式.最后,通过求解协作配送算例和实例,验证了本文AIA算法能够准确求解得到协作配送成本分摊问题的核仁解,提出的求解策略能有效的减少求解耗时,并且得到的最终结果与实际核仁解的平均偏差不到0.02%,更重要的是AIA能够用于求解所有凸博弈问题的核仁解.     

基于SDVRPTW模型的项目设备优化调度方法

在大型工程项目的子项目或工序中,重要设备的优化调度对提高设备的利用率,确保项目按期完工具有重要作用。将大型项目设备调度问题(ESPLP)归结为任务需求可拆分、带有时间窗的车辆路径问题(SDVRPTW)。根据项目设备调度过程中的约束建立了项目设备调度模型,并分析了ESPLP最优调度方案所具备的性质特征与SDVRPTW问题的区别,针对模型特点提出了远缘杂交遗传算法(DCGA)。基于国内某大型建筑项目实际案例为测试对象,分别将DCGA的求解结果与项目现实调度数据进行了对比,并比较了DCGA与现有算法的性能,比较结果表明了本文模型与算法的有效性。