果蔬采后分级和预冷车辆协同调度模型与算法

王旭坪,王 悦,李 娅,林 娜

(1.海南科技职业大学 财经学院,海南 海口 571126;2.大连理工大学智慧商务物流研究所,辽宁 大连 116024)

近年来,随着越来越多的农户采用B2C模式销售果蔬农产品,果蔬采后商品化处理及“最先一公里”冷链物流环节存在的问题日渐暴露,包括人工分级效率低下、预冷不及时、采后处理环节断链等。这些问题大大加剧了果蔬采后损耗,进一步造成生产资源巨大浪费与农民经济损失[1-3]。调研发现,我国果蔬产品采后损耗高达15%～25%,相当于8×106ha(1.2亿亩)耕地种植的产品被浪费,而美、日、西欧等发达国家这一比例在5%以下。针对我国果蔬农产品产地分散、小规模生产的特点,适合中国国情的移动式分级[4]、预冷设施[5]以及配套的运载车辆应运而生。移动式分级车、预冷车可开至田间地头对果蔬进行就地分级、预冷,解决了人工分级效率低、预冷站预冷不及时等问题,有助于降低果蔬采后损耗,也催生了“最先一公里”冷链物流环节协同运作优化问题。

以采后分级环节和预冷环节为例,果蔬采后通常需要先进行分级处理,后进行预冷处理,以便将预冷处理后的产品及时保存在冷藏环境中,维持预冷效果。同时,预冷环节具有强时效性,需要在果蔬采后较短时间内完成,以尽快去除田间热、抑制呼吸作用,保持产品质量。若分级环节与预冷环节独立运作优化,不仅难以保障果蔬产品的预冷效果,也容易造成服务资源浪费。因此,在果蔬收获时节,如何结合分级、预冷环节的先后服务顺序以及预冷环节的强时效性等特征,协同调度有限的移动式分级、预冷服务资源以满足小农户的多样化服务需求,在保障产品质量的同时尽可能降低运作成本,成为果蔬采后“最先一公里”冷链物流环节亟待解决的运作优化问题。

尽管移动式分级车、预冷车已开始应用于果蔬采后处理实践中,但由于农户对于果蔬采后分级、预冷处理的意识仍较为薄弱,移动式分级、预冷服务尚未形成规模化应用场景,鲜有学者关注果蔬采后“最先一公里”中的预冷分级环节运作优化问题。目前关于生鲜产品物流运作优化领域的研究较多聚焦于农产品采后“最先一公里”集货[6-8]、冷链网络布局[9-11]以及生鲜产品城市“最后一公里”配送等方面[12-14]。分析本研究问题特点,其属于一类带有双需求的车辆路径规划问题(Vehicle Routing Problem,VRP),这类问题的主要代表为同时取送货VRP[15-17]。然而,本研究中客户的分级、预冷需求属不同类别的需求,需要两辆车协同服务,这与带有协同约束的车辆路径问题(Vehicle Routing Problem with Synchronized Visits,VRPSV)相类似。Ali等[18]研究了同时考虑配送和安装两种服务需求的车辆路径问题,并通过分支定界算法进行求解。Qiu等[19]关注家居行业送货上门和安装路径问题,目标是确定车辆的最佳送货路线和技术人员的最佳服务路线,并提出深度强化学习方法进行求解。Liu等[20]研究了一类带时间窗和协同服务约束的特殊车辆路径问题,该问题的协同约束将不同车辆路径相互连接,考虑到计算时间的复杂性,设计了高效的改进大邻域搜索算法进行求解。Fink等[21]聚焦机场地勤运营规划问题,将其抽象为具有工人和车辆同步的车辆路径问题,并设计分支定价算法进行求解。Hintsch[22]研究了软集群车辆路径问题,考虑同一集群客户必须由同一车辆提供服务特点,设计了多邻域搜索算法进行求解。Aziez等[23]研究了具有动态需求AGV 协同的车队规模和路由问题,该问题中医院执行不同任务需要不同类型的手推车,这些手推车由AGV运输,目标是同时优化手推车和AGV 的类型和路线并满足服务时间限制。Erdem 等[24]研究了家庭医生日常路线协同规划问题,以便为分散区域的患者提供一系列服务,将其抽象为带时间窗与电车充电的VRPSV,基于此构建了混合整数规划模型,并设计了一种特定的自适应大邻域搜索算法进行求解。Doulabi等[25]将具有随机时间的VRPSV 表示为两阶段随机整数规划模型,并使用分支定界法对随机家庭医疗计划进行优化求解。上述研究在模型构建和方法求解方面为本研究的顺利开展奠定了重要的理论基础。然而,现有关于VRPSV的研究中仅以两个需求间的服务时间间隔作为协同条件。在本文中,除了考虑分级与预冷服务的时间间隔约束,还需要考虑果蔬最佳预冷时间约束,这进一步加剧了双需求VRP的协同复杂度。同时,本文研究对象为采后“最先一公里”果蔬农产品,导致该问题与传统生鲜产品车辆路径问题具有明显区别,主要体现在延迟预冷对果蔬新鲜度变化的独特影响。基于上述分析,研究果蔬农产品分级和预冷车辆协同调度优化问题需要对现有VRP模型进行拓展,并设计考虑多协同约束的求解算法。

针对果蔬农产品分级和预冷环节协同优化问题,本文综合考虑分级和预冷的先后服务顺序约束、最大时间间隔约束以及最佳预冷时间约束,结合预冷环节的时效性特点,将延迟预冷产生的新鲜度变化转化为三阶段成本函数,构建了移动式分级和预冷车辆协同调度模型,进而结合问题的关键协同约束条件设计了混合遗传算法进行求解。该算法融合了遗传算法的全局寻优能力与邻域搜索算法的局部寻优能力。最后,基于VRP 基准算例的数值实验验证了本文所设计算法在求解大规模算例时可以快速收敛到高质量的解,基于陕西省洛川县水蜜桃产业的分级预冷数据证明了本文模型的合理性。

1 数学模型

1.1 问题描述

为便于后续存储、销售和运输,农产品在采摘后均将进行分级,是否进行预冷则需根据农产品类型和农户需要进行取舍。根据农户的分级、预冷需求差异,可将农户点分为两类:一类是仅有分级需求的农户点,另一类是具有分级和预冷的双需求农户点。对于仅有分级需求的农户点,由一辆分级车服务一次,且分级车需要在给定的软时间窗内到达,否则将产生早到等待和晚到惩罚成本。对于双需求农户点,由一辆分级车和一辆预冷车分别服务一次,且分级车需要在给定的软时间窗内到达,预冷车则需要在分级车完成分级服务之后到达,且与分级服务的间隔不能超过最大允许间隔时间(见图1),否则将产生对应的惩罚成本。这是因为首先按照分级、预冷的作业特点,分级服务应先于预冷服务。其次,为保证顾客满意度,两类服务间隔时间不宜过长。此外,为保证预冷的及时性和有效性,预冷服务需在农产品采摘后的一定时间内完成,否则会影响预冷效果,产生延迟预冷成本。如何在满足上述时间窗约束的条件下,兼顾两类农户点的分级、预冷需求,协同规划分级车和预冷车的服务路径,实现系统资源的最优配置,是本文所要解决的关键问题(见图2)。

图1 分级-预冷服务时间线Fig.1 Timeline of grading and pre-cooling services

图2 移动式分级和预冷资源协同调度问题Fig.2 Collaborative scheduling of mobile grading and pre-cooling resources

基于上述分析,本文从系统成本最优角度对果蔬农产品分级和预冷环节协同优化问题进行研究,决策内容包括:①分级车、预冷车分配;②分级车、预冷车服务路径;③分级车、预冷车服务时间规划。

1.2 模型设定

为便于讨论且不失一般性,本文做出如下假定:

(1) 所有分级车和预冷车均以冷链物流中心为起始点,且所有车辆每天仅往返一次。

(2) 农户点需求均为小批量,且不超过分级车、预冷车的最大服务工作量。

(3) 为每个农户点提供分级服务的时间窗固定且已知。

(4) 同类型车辆之间是同质的,且车辆行驶速度均为匀速。

(5) 果蔬采摘结束便有分级需求,将农户分级时间窗下限视为果蔬采摘结束时间。

符号说明:

决策变量

参数

1.3 成本分析

(1) 车辆固定启动成本。车辆固定启动成本是分级车、预冷车启动时所需的固定启动费用,包括车辆的折旧成本、司机的驾驶成本等,即

(2) 车辆行驶成本。车辆行驶成本是分级车和预冷车在行驶过程中产生的油耗成本,即

(3) 分级和预冷服务总成本。在田间地头提供分级或预冷服务,需要人工和自动化设备的相互配合,将产生相应的能耗和人工成本。因此,分级和预冷服务总成本可按照下式计算:

(4) 早到等待和晚到惩罚成本。对于分级车,早到等待和晚到惩罚成本是指车辆早于和晚于规定的分级时间窗到达产生的惩罚成本。对于预冷车,当其早于分级车到达时需要等待至分级车结束服务才能开始服务,因此会产生相应的早到等待成本。此外,当预冷车晚于分级-预冷最大允许间隔时间到达时,亦会产生相应的晚到惩罚成本。因此,早到等待和晚到惩罚成本为

(5) 延迟预冷成本。延迟预冷成本是指延迟预冷时间过长时造成预冷效果不佳所产生的损失成本。果蔬农产品采摘后,若延迟预冷时间在tdelay内完成预冷,其预冷效果最佳,否则预冷效果将随时间逐步减弱,且当延迟预冷时间超过临界值t F时,预冷将失去意义[26]。可近似用下式表示预冷效果随时间变化的规律:

式中,α为折损率,且α=1/tdelay。

对Q(t)进行成本转化,可得到果蔬农产品延迟预冷成本随时间变化的函数,即

式中:a为单位质量果蔬因延迟预冷产生的货损成本为客户点i的预冷需求量。

1.4 模型建立

综合式(1)～(6),可得如下移动式分级-预冷资源协同调度优化模型:

其中:式(7)表示最小化系统总运营成本z,包含车辆固定启动成本z1、车辆行驶成本z2、分级和预冷服务总成本z3、超出分级时间窗、早到等待和晚到惩罚成本z4以及延迟预冷成本z5;式(8)表示所有启动的预冷车辆和分级车辆均从冷链物流中心(闭合单车场)出发,服务完成后返回车场;式(9)表示同一路径上某种类型服务车辆服务的农户需求量不得超过该车辆最大服务工作量;式(10)表示每个农户点的每种需求仅由对应类型下的同一辆车完成服务,且相应需求不可拆;式(11)、(12)分别表示分级车和预冷车的数量限制;式(13)、(14)分别表示分级车和预冷车到达时间和开始服务时间的关系;式(15)～(18)分别表示分级车和预冷车的早到等待时长和晚到延迟时长;式(19)表示任意类型车辆到达相邻农户点之间的时间间隔关系;式(20)为农户分级时间窗约束;式(21)表示具有双重需求的农户点服务时,必须先进行分级服务、后进行预冷服务;式(22)表示具有双重需求的农户点服务时,预冷车到达时间与分级车分级服务结束的间隔不能超过最大允许间隔时间;式(23)表示所有分级农户点的分级服务结束时间不得超过果蔬最佳预冷时间;式(24)表示每种类型车辆的总行驶时间不得超过其对应的最大行驶时间;式(25)表示分级车和预冷车不得晚于物流中心最大服务时间返回;式(26)、(27)为车辆的进出平衡关系;式(28)为决策变量的取值约束。

2 算法设计

本文问题是考虑客户双需求带有的双时间窗、双需求服务先后顺序、服务延迟时间等对分级车辆和预冷车辆服务路径进行协同优化的经典VRP的拓展问题,属于NP-hard问题。采用精确算法求解困难,因而本研究结合问题特点,设计了一种特定的启发式算法进行求解。遗传算法具有较好的全局搜索能力,但该算法存在局部搜索能力差的缺点。同时,遗传算法可扩展性强,因而较容易与其他算法进行结合,而邻域搜索算法具有局部搜索能力强的特点。因此,为提高算法的收敛速度与求解质量,本研究综合考虑遗传算法的全局搜索能力与邻域搜索算法的局部搜索能力,采用遗传算法的框架,引入邻域搜索算法嵌入遗传算法中的变异操作,设计混合遗传算法求解上述模型。所设计算法的创新点主要包括3个方面:①结合问题的双需求特点,设计基于双序列的解的表达方式,其中一条序列表示分级车辆路径,另一条序列表示预冷车辆路径,并结合双时间窗、服务先后顺序等问题特点设计特定的初始种群生成机制与解码机制;②设计基于最佳插入策略的顺序交叉算子,以最小化运作成本为评估机制,结合模型的相关协同约束条件进行可行性检查,保证生成高质量的可行子代,以加速算法收敛;③结合双需求服务的协同条件,设计基于大路径-相邻路径-子路径三阶段邻域搜索的变异操作,对种群中部分个体进行变异,提高算法的局部搜索能力。

图3所示为算法运行框架。其中,生成初始种群、种群个体交叉和种群个体变异3个部分为本研究关键创新环节。

图3 混合遗传算法流程Fig.3 Flow chart of the hybrid genetic algorithm

2.1 基于双序列染色体的解的表达与初始种群生成

该研究问题中客户具有两类需求,且分别需要不同类型车辆进行服务。为了表示不同类型车辆的服务路径,设计了基于双序列染色体的编码方式,并基于此设计了解码及初始种群生成机制,如图4所示。其中:序列G r为所有的分级服务需求点,通过将其解码得到分级车辆服务路径(解码机制见步骤2);序列P r为所有的预冷服务需求点,结合分级预冷服务最大时间间隔约束得到预冷车辆服务路径(解码机制见步骤5)。

图4 初始个体生成过程示意图Fig.4 An example of the initial individual generation

基于所设计的双序列编码方式及对应的解码机制,初始种群生成步骤如下:

步骤1基于客户聚类生成分级服务需求点序列G r。随机选择K1个分级客户点作为聚类簇中心,将剩余N1-K1个客户点分配给距离最近的聚类簇。随机选择一个聚类簇中心i作为G r序列的起始点,依次排列属于聚类簇i的客户点,继而选择距离聚类簇中心i最近的聚类簇中心j进行排列,并依次排列属于聚类簇j的客户点。重复此步骤,直至完成所有客户点排列。

步骤2解码得到分级车辆服务路径G v。以冷链物流中心0点作为第一条分级车辆路径的起始点,将G r中的点依次添加至当前路径,并基于约束式(9)检查分级车辆载重约束是否满足。若不满足,则在当前路径末尾添加0 作为路径终点;若满足,则按照客户点分级时间窗下限E1i自小到大的顺序对当前路径进行排序。基于约束式(23)检查分级服务结束时间是否满足果蔬最佳预冷时间约束。若不满足,将当前客户点移至序列G r末尾;若满足,基于约束式(24)、(25)分别检查分级车辆工作时间约束、分级车辆到达冷链物流中心的时间约束。若不满足,则在当前路径末尾添加0作为路径终点;若满足,则继续从序列G r中添加点至当前路径。重复上述步骤,直至序列G r为空。

步骤3基于分级车辆服务路径G v得到预冷服务需求点序列P r。按照预冷服务需求点在分级车辆服务路径G v中出现的顺序,将其依次插入序列P r。

步骤4基于分级车辆服务路径G v计算预冷订单的服务时间窗。在求解分级预冷车辆协同调度问题时,关键是寻求两种服务的协同优化。在本研究中,分级服务在预冷服务之前完成,且两者之间的服务间隔不能超过一定的限制。由于分级车辆服务路径已知,则预冷订单服务时间窗上下限均可基于分级服务完成时间与两者之间的最大间隔时间得到,如式(22)所示。

步骤5解码得到预冷车辆服务路径P v。在得到预冷订单服务时间窗后,可基于此进行解码得到预冷车辆服务路径,该过程与步骤2类似。首先,以冷链物流中心0点作为第一条预冷车辆路径的起始点,将P r中的点依次添加至当前路径,并基于约束式(9)检查预冷车辆服务能力是否满足。若不满足,则在当前路径末尾添加0 作为路径终点;若满足,则按照预冷时间窗下限自小至大的顺序对当前路径进行排序。基于约束式(24)、(25)分别检查预冷车辆工作时间约束、预冷车辆到达冷链物流中心的时间约束。若不满足,则在当前路径末尾添加0作为路径终点;若满足,则继续从序列P r中添加点至当前路径。重复上述步骤,直至序列P r为空。

步骤6重复步骤1～5,直至生成G个初始个体。

2.2 基于轮盘赌机制的选择操作

采用轮盘赌的方式,根据适应度值选择个体进入下一次迭代。具体如下:将每条染色体一对一映射到[0,Sum]的连续区间(Sum 为所有染色体的适应度之和),每条染色体区间的大小与其适应度值相匹配,因而适应度值越大的染色体被选中的概率越大。染色体i的适应度f i等于其对应解的目标函数值Z i的倒数,即

2.3 基于最佳插入策略的顺序交叉操作

交叉操作采用经典的顺序交叉算子,融合最佳插入算子以生成高质量的可行后代。首先选择父代个体A 和B,在其分级服务需求点序列中随机选择两个基因位点P1和P2,顺序交换父代个体A、B中P1～P2序列,进而对交换后的个体进行冲突检测,删除重复的需求点,并基于最佳插入策略插入缺失的需求点

以图5为例,在父代个体的分级服务需求点序列中选择第4～第7个位点进行交换,得到中间父代A1和B1。在交换后,父代A1中需求点7、9、10重复,需求点1、5、6缺失;同时,父代B1中需求点1、5、6 重复,需求点7、9、10 缺失。在父代A1、B1中删除重复点,进而基于最佳插入策略插入缺失点。

图5 交叉算子示意图Fig.5 The schematic of the crossover operator

具体步骤如下:

步骤1以父代A 为例,对删除重复点后的G r序列进行解码,得到分级车辆服务路径G v与预冷车辆服务路径P v,便于后续插入成本的计算。

步骤2插入缺失点至当前解(以需求点1为例)。将点1插入G v中的可行位置,这里每一条分级车辆路径至多只有一个可行位置。这是因为分级服务车辆开展服务时基本按照节点的时间窗先后顺序,无须将节点插入一条分级车辆路径中的所有位置,仅须将节点1插入E1i比其小的节点之后且E1i比其大的节点之前。插入位置的可行性判断基于约束式(9)以及式(23)～(25)。针对所有可行的插入位置,根据1.4节中式(7)计算插入点1前后成本A1和A2,得到点1的插入成本A2-A1。最后,将点1插入成本最小的位置。需要注意的是,在计算点1插入G v前后的成本时,只计算点1插入当前分级车辆路径的成本,无须计算所有分级车辆路径。

步骤3重复步骤(2),直到父代A 中所有缺失点均插入G v。

步骤4重复步骤(1)～(3),直到父代B 中所有缺失点均插入G v。

2.4 基于三阶段邻域搜索的变异操作

考虑到邻域搜索算法的局部搜索能力,本研究将其嵌入到遗传算法的变异操作中,结合双需求服务的协同条件,分别设计大路径-相邻路径-子路径3个层面的邻域搜索算子。邻域搜索算法的基本框架如下:假设x为问题的一个可行解,将x作为当前解,应用邻域搜索算子得到x的邻域解x',若x'的目标值更优,则将x'作为新的当前解继续进行邻域搜索,直到达到最大迭代次数。

由于3种算子的局部搜索过程按照由大至小的层级展开,故在操作时依序作用于待变异的个体。假设结束第一/二层邻域搜索后得到的局部最优解为x'/x″,则将x'/x″作为第二/三层邻域搜索的初始解,从而保证变异过程总是生成不劣于变异前的个体。

3种算子的具体过程如下:

(1) 最佳插入算子——大路径层。该算子旨在对大路径进行局部搜索,首先将个体A 的G r序列进行解码得到G v,然后随机删除G r序列中的部分点,并在G v中对应删除,最后按照2.3节步骤2中采用的最佳插入策略,将已删除的点插入G v。

(2)Reverse算子——相邻路径层。在本研究中,基于Reverse算子对个体进行局部搜索时,在个体A 的G r序列中随机选择点i、j,将点i、j间点的顺序进行倒序操作。这一操作将直接影响解码过程中相邻路径的生成过程,旨在通过交换相邻路径的节点实现局部搜索。

(3) 相似点交换算子——子路径层。随机交换个体A 的G r序列中两个相似的节点i、j,由于两个节点均来自某一条分级车辆路径,故该算子旨在实现子路径层面的局部优化。两点i、j的相似性R ij基于下式得到:

3 数值分析

3.1 算法有效性验证

目前有关双需求车辆协同调度问题尚未有可供参考的基准算例,为了测试所设计的混合遗传算法的有效性,本文以Solomon带时间窗的标准算例库[27]为基础,并根据本文问题所需对其进行了数据修改和补充。选取Solomon 算例库中的C101、C201、R101、R201、RC101、RC201等6类算例为实验对象,每类算例中分别随机选取25、50、100个客户点生成3组不同客户规模的算例,共组成18个测试算例。客户地理位置、需求量及时间窗信息保持不变,客户处的服务时间通过计算客户需求量与服务速度的比值得到,并对其含有25、50、100个客户点的算例分别随机生成10、25、50个双需求客户点。算例中分级车与预冷车的固定成本分别为200和300元/辆;分级车的早到与晚到惩罚系数为0.04和0.06;车辆最大行驶时间均为200 min。算法采用Matlab2016a进行编程,在Windows10操作系统8 GB 内存环境下运行。经过多次实验,设置相关参数如下:种群规模均为100;客户规模为25、50、100的算例最大迭代次数分别为1 000、1 000和2 000。

为测试混合遗传算法求解双需求车辆路径问题的性能,选取标准遗传算法和变邻域搜索算法与之进行对比。其中,标准遗传算法与本研究所设计的混合遗传算法主要区别在于交叉和变异操作部分,前者的交叉操作采用与本研究类似的步骤,但是在重新插入缺失点时仅将点插入可行位置而非最佳位置。变异操作采用一种经典的变异算子,即在染色体中随机选择两个基因点进行交换。标准遗传算法中初始种群生成及编解码机制、选择操作均与本研究所设计的混合遗传算法一致。变邻域搜索算法则按照该算法的标准框架进行基于单初始解的求解,其中邻域搜索部分采用本研究设计的三阶段邻域搜索算子。其初始解生成及编解码机制均与本研究所设计的混合遗传算法一致。基于全局搜索的遗传算法与基于局部搜索的邻域搜索算法结合后的混合遗传算法的效果将在本部分得到测试。

使用3种算法对每个算例求解20次,结果如表1所示。

表1 3种算法结果比较Tab.1 Comparison of results of three algorithms

由表1可以看出,在求解质量上,本文算法最优值较标准遗传算法平均改进幅度为12.32%,相较于变邻域搜索算法平均改进幅度为17.13%,且在求解大规模算例时改进幅度更大。在求解时间上,与变邻域搜索算法相比,本文算法在小规模、中等规模和大规模算例中具有显著优势;与标准遗传算法相比,本文算法在小规模算例中与之表现相当,但在大规模算例中优势凸显。综上所述,本文提出的混合遗传算法在求解质量与求解时间方面均优于现有的变邻域搜索算法与标准遗传算法,且在求解大规模算例时优势更加突出。

为了直观地显示本文算法在求解性能上的显著优势,以算例R101为例,将3种算法的收敛情况进行对比,如图6所示。

图6 3种算法求解R101算例的收敛过程Fig.6 The convergence process of three algorithms for solving the R101 instance

图6结果显示,在求解小规模算例时,标准遗传算法和变邻域搜索算法均可得到与混合遗传算法相近的解,且标准遗传算法与本文算法收敛速度相当,这进一步解释了小规模算例中,标准遗传算法与本文算法求解时间相当。但在求解中等规模、大规模算例时,相较于另两种算法,混合遗传算法具有更快的收敛速度,可以在更短时间内收敛到更高质量的解,在求解质量和速度上具有显著优势。这进一步解释了在中等规模、大规模算例中,本文算法求解时间显著短于标准遗传算法和变邻域搜索算法。

3.2 实例分析

3.2.1基础数据与参数设定 根据实地调研,本部分选取陕西省洛川县25个典型村的水蜜桃种植数据进行实例研究。假设一家冷链物流中心拟在洛川县提供水蜜桃采后商品化处理服务,该中心同时配置有移动式分级车和预冷车,可为农户提供移动式分级与预冷服务。在每一典型村中选取一户典型户作为客户点,25个客户点的地理坐标、分级量、预冷量、分级服务时间窗等具体信息如表2 所示,其中,0表示冷链物流中心。客户分级需求量计算方式如下:根据调研得到的25个村落典型户2020年水蜜桃产量和种植面积数据,结合水蜜桃的采收时长(单位:d),计算得到每个典型户平均一天内采摘水蜜桃量。农户的分级时间窗根据果农实际采收时间生成,其服从U(14,18)的均匀分布(单位:h)。

表2 农户基本信息Tab.2 Basic information of farmers

其他实例参数结合调研数据设定如下:分级车的固定启动成本为500元/辆,预冷车为300元/辆;分级车的车辆行驶成本为2 元/km,预冷车为1.5元/km;分级车上设备的能耗成本为1.5元/min,预冷车为1.2元/min;分级车行驶速度为30 km/h,预冷车为40 km/h;分级车提供分级服务时的工作速度为30 kg/min,预冷车为15 kg/min;分级车的最大行驶时间为500 min,预冷车为600 min;农户所能接受的分级、预冷服务最大允许间隔时间(以农户分级车结束服务时间为起点计算)为100min;分级车的最大服务处理量为7t,预冷车为4 t;水蜜桃最大预冷延迟时间为6h;分级车早到等待和晚到惩罚系数分别为0.5 和1.5 元/min,预冷车分别为0.8和20元/min;预冷车预冷方式为差压预冷。

3.2.2模型求解与结果分析采用本文算法对该实例进行10次求解,最优方案如表3所示。冷链物流中心总计派出5辆分级车和4辆预冷车为25个农户提供服务,其总成本为9 448.91元。移动式分级服务的单位成本基本维持在0.2元/kg左右,移动式预冷服务的单位成本维持在0.3元/kg左右,该结果相对于调研中得到的人工分级成本0.4元/kg、预冷库预冷成本0.8 元/kg 均有所降低。这表明,使用移动式设备进行采后处理可以节约成本,当然这不排除参数理想化的结果。此外,分级车5由于只服务了一个农户,造成分级服务单位成本高于人工分级的情况。这表明,当农户点数量较少时,采用移动式服务设备进行采后处理无法实现规模经济。算例结果中延迟预冷成本均为0,这是因为分级时间窗设定较为集中,在服务最大允许间隔时间的约束下,可以确保水蜜桃采后预冷的及时性,也间接说明本文所提出的移动式分级与预冷资源协同调度模型可以有效避免预冷延迟。

表3 车辆调度方案Tab.3 Vehicle scheduling plan

3.3 灵敏度分析

3.3.1服务水平分析 分级和预冷环节的服务时间间隔在一定程度上反映了服务水平,该间隔越小,表明农户等待预冷服务的时间越短,对服务过程满意度越高,服务水平越高,但协同调度的困难就会越大。为了寻找最佳服务间隔时间,本文将其分别设定为60、80、100、120和140 min,其余参数不变,具体计算结果如表4所示。通过对比可以得出,改变服务时间间隔对固定成本和服务成本均不产生影响。这表明,改变服务时间间隔,其使用车辆数未产生变化;延迟预冷成本始终为0,表明本文模型能较好保证预冷及时性;随着服务时间间隔的增大,分级车和预冷车的协同服务时间窗更容易满足,故惩罚成本逐渐降低,当间隔时间为140 min时总成本最低。因此,考虑到农户对服务过程的满意度,本实例中应将其设定为100 min。

表4 服务水平分析Tab.4 Service level analysis

3.3.2预冷需求占比分析 为了寻找较优的预冷需求占比(总预冷需求量/总分级需求量),保持实例中其余参数不变,通过改变所有客户点中有预冷需求的客户点数,测试预冷车服务率(同一路径上预冷车总服务量/预冷车最大服务量)的影响,具体情况如图7所示。由图7可以得出,随着预冷需求占比的增加,预冷车服务率呈现先增加后减少的趋势,并在预冷需求占比为50%时预冷车服务率达到最高。

图7 预冷需求占比分析Fig.7 Analysis of pre-cooling demands’proportion

3.4 实验结果讨论

基于上述研究结果,可以得到以下管理启示:

(1) 与传统的人工分级和预冷库预冷模式相比,新兴的移动式分级和预冷资源协同调度有助于降低企业运作成本并有效缩短产品预冷延迟时间,这主要得益于协同优化思想对资源的有效整合与利用。生鲜农产品物流服务企业应逐步将果蔬采后移动式预处理技术应用于实际运作中,并积极开展多环节协同运作优化,以增强企业竞争力。

(2) 在开展分级、预冷服务协同运作优化时,增大两项服务之间的时间间隔有助于降低优化难度以及总运营成本,这是因为更宽的时间间隔增大了调度的柔性进而降低了协同的难度与服务延迟成本。然而,更宽的时间间隔会延长客户等待时间,并进一步导致客户满意度下降。因此,物流企业在开展服务前应充分调研客户对服务时间间隔的期望分布,以确定合理的折中。

(3) 当客户需求的种类及数量变化时,车辆的服务率也会随之变化。例如,随着预冷需求占比的增加,预冷车服务率先升高后降低,这主要是由于原有车辆未达到较高的服务率,故增加部分需求将会增加车辆的平均服务率。然而,当需求过大时,原有车辆无法满足所有需求,此时新增车辆将会降低平均服务率。因此,物流企业应综合考虑需求特点配置不同的车型,通过提高车辆服务率来减少车辆使用,最大限度降低总运作成本。

4 结论

本研究聚焦果蔬采后“最先一公里”冷链物流分级预冷环节协同运作优化问题,旨在为服务主体开展分级和预冷服务协同优化提供决策支持,主要贡献包括3个方面:

(1) 综合考虑果蔬最佳预冷时间、先分级后预冷的服务顺序等特有协同情景,构建了移动式分级预冷资源协同调度优化模型,拓展了VRPSV 的应用场景。

(2) 考虑延迟预冷带来的果蔬新鲜度的特殊变化,设计了延迟预冷成本函数,在保障产品质量的同时最小化服务运作成本。

(3) 结合问题的关键协同约束条件设计混合遗传算法求解该模型,并结合问题特点设计了特有的基于双序列的解的表达方式、基于最佳插入策略顺序交叉算子以及基于三阶段邻域搜索的变异操作,可实现大规模算例高效高质求解。

实验证明,本研究提出的移动式分级预冷资源协同调度模型及求解方法能有效解决果蔬采后人工分级效率低、预冷库预冷不及时以及“最先一公里”冷链物流环节断链问题。随着国家对农产品上行“最先一公里”建设力度的加大以及移动式预处理技术的发展成熟,基于协同优化思想开展“最先一公里”冷链物流环节协同运作优化研究对整合村镇冷链服务资源、降低果蔬采后损耗具有重大价值,并助力农产品冷链物流行业转型升级和高质量发展。未来将对多品类果蔬产品、不同车型的移动式分级预冷车辆协同调度展开研究。