梁桂云，陈淮莉

(上海海事大学物流科学与工程研究院，上海 201306)

近年来,随着互联网技术日益成熟、用户消费习惯和理念的转变,生鲜电商行业得到迅速发展。2020年受新冠疫情影响，消费者对于生鲜到家的需求急速增长,中国生鲜电商交易额达到1 821.2亿元。由于生鲜品具有易腐性和保质期短的特点，生鲜电商企业须在完成对生鲜品的流通加工后立即组织安排配送。然而,目前生鲜电商企业大多凭经验来判定各岗位的员工调度，由此带来加工环节混乱、配送延迟和各种资源的紧缺与冲突等众多问题。因此，如何协同优化流通加工与配送这两个环节，在降低总成本的同时保证交付产品的新鲜度,一直是生鲜电商企业关注的问题。

关于生鲜品的生产加工和配送联合调度(production and distribution integrated scheduling，pdis)问题的研究如下：amorim等研究分批和批量两种生产模式下的生鲜品pdis问题，通过算例验证了批量生产能够降低总成本。belo-filho等设计了一种自适应大邻域搜索算法求解生鲜品pdis问题。seyedhosseini等提出了一种考虑批量生产和库存路径的生鲜品pdis模型，并开发了启发式算法进行求解。devapriya等研究了保质期约束下的生鲜品pdis问题，通过遗传算法对所构建的生鲜品pdis模型进行求解。吴瑶等基于路网交通状况的时变性，构建了以配送成本与产品价值损耗总和最小为目标的优化模型，并设计了混合遗传算法进行求解。马雪丽等考虑生鲜品的需求和配送时间的随机性，研究了生产商和零售商两级供应链模式下的生鲜品pdis问题，并利用基于随机模拟的混合遗传算法进行求解。lacomme等研究了单一生鲜品生产和多车运输一体化问题。王旭坪等根据在线订餐问题特点，将生产环节和配送环节分别抽象为并行机调度问题和带时间窗的车辆路径问题(vehicle routing problem with time window, vrptw)，以服务所有订单需要的总时间之和最小为目标，构建并行机生产多车多任务配送联合优化模型，并设计了三阶段启发式在线调度算法进行求解。李畅等在关于生鲜品pdis问题中考虑了生鲜品保质期和客户购买行为，并通过算例验证了所建模型的有效性。dayarian等根据生产人员配置建立了生鲜品pdis优化模型，再根据模型特点设计了新的分支定价算法进行求解。liu等以最小化配送时间为目标建立了生鲜品pdis优化模型，并设计了一种改进的大邻域搜索算法进行求解。li等研究了考虑食品包装因素影响的生鲜品pdis问题,利用混合整数线性规划方法来描述这个新问题，提出了两种分支切割算法，计算结果表明包装与生产路线的集成优化可以带来经济效益。solina等考虑生产加工的转换时间和产品易腐性约束，以最小化生产和配送成本为目标建立了一个生产和分销的综合调度优化模型。

以上关于生鲜品pdis的文献大多考虑单目标或者将多个目标转化为单目标进行研究。经济的发展和生活质量的改善使得人们对商品品质的要求逐渐提高，而新鲜度作为决定生鲜品品质的重要指标越来越受到重视。少数学者开始在关于多目标生鲜品配送路径优化的研究中考虑产品交付时的新鲜度：李畅等在生鲜品配送路径优化的研究中构建了以最大化新鲜度和最小化配送成本为目标的生鲜品配送路径优化模型，并利用基本自适应差分进化算法进行求解；李善俊等将生鲜品新鲜度与多目标vrptw进行结合，建立最大化生鲜品新鲜度和最小化配送成本的多目标车辆路径优化模型，并设计了非支配排序遗传算法(non-dominated sorting genetic algorithm，nsga)进行求解。然而，少有文献将生鲜品的新鲜度与多目标生鲜品冷链配送联合调度问题相结合。因此，本文在以往文献研究成果的基础上，以产品交付时新鲜度最大和总成本最低为目标，建立多目标生鲜品冷链配送联合调度优化模型，并利用第二代非支配排序遗传算法(nsga Ⅱ)，获得满足产品交付时新鲜度最大和总成本最低的相对较优解。

结合生鲜品加工和配送的特点，将多目标生鲜品冷链配送联合调度问题描述为：如图1所示，一个生鲜电商配送中心向多个客户提供生鲜品送货上门服务。生鲜电商企业在平台接收客户订单后，根据订单需求安排多名加工人员进行加工，每个订单产品种类不同且不可拆分。订单加工完成后立即分批组织车辆进行配送，忽略装车时间。针对生鲜品易腐和保质期短的特点，需要将流通加工环节与配送环节进行联合调度。同时，为了提高客户满意度和生鲜电商企业的利润，需要在追求产品交付时新鲜度最大和总成本最低两个目标的基础上决策：订单分配给加工人员、各加工人员的订单加工顺序、已完成加工的订单生成合理的配送车次，以及各车次的订单交付顺序。本文采用文献[15]中定义的()表示产品新鲜度。根据生鲜品价值随运输时间加速递减的特点，令()为生鲜品的价值损耗系数，为订单产品的保质期，则()=eln(2)-1，从而()=1-()。

图1 生鲜品加工配送流程示意图

由于多目标生鲜品冷链配送联合调度的复杂性，为便于模型的构建和求解，假设：(1)客户地理位置、客户要求服务的时间窗、产品的需求量和保质期等信息已知；(2)每个客户只被服务一次，每个订单只包含同一类产品且加工时间均不同；(3)加工中心采取并行机加工模式，由多个能力相同的加工人员进行加工，不考虑订单加工的等待时间；(4)每个订单仅由一名加工人员负责加工，订单不可拆分且只被加工一次，忽略不同订单之间的切换时间和成本；(5)有多辆车(其容量是相等的)负责配送，不存在等待配送情况；(6)每车次负责配送一条路径，该车次从配送中心的发车时刻不早于对应路径上最后一个订单的加工完成时刻；(7)车辆完成一次配送后立即返回配送中心；(8)生鲜品离开配送中心时新鲜度最大。

本文将流通加工环节抽象为并行机调度问题，将配送环节抽象为vrptw。由于每个订单的加工成本是固定的，而配送成本不是固定的，因此将配送总成本作为目标之一。配送总成本主要包括运输成本、固定成本、延迟成本、等待成本和产品价值损耗成本。基于上述分析和参数定义，模型建立如下：

(1)

(2)

s.t.

(3)

(4)

(5)

(6)

?,∈,≠,∈

(7)

(8)

(9)

(10)

(11)

(12)

(13)

?,∈,∈

(14)

(15)

(16)

()≥

(17)

={0,1}, ?,∈,∈

(18)

={0,1}, ?,∈,∈

(19)

={0,1}, ?∈,∈

(20)

式(1)表示配送总成本最低；式(2)表示产品交付时平均新鲜度最大；式(3)表示最多只有一个订单是由加工人员第一个加工的；式(4)和(5)表示所有订单均被生产加工；式(6)表示加工人员的订单加工顺序；式(7)表示订单的后续紧邻订单的生产加工完成时间；式(8)和(9)表示所有客户均被服务且只访问一次；式(10)表示路径流量平衡；式(11)表示每辆车配送完成后必须返回配送中心；式(12)表示每条路径满足车辆容量约束；式(13)表示每条路径的开始配送时间不早于该路径上所有订单的生产完成时间；式(14)～(16)表示每条配送路径上的时间关系约束；式(17)表示交付的产品满足最低新鲜度要求；式(18)～(20)为0-1变量约束。

本文提出的多目标生鲜品冷链配送联合调度问题是传统pdis问题的延伸，pdis问题已被证明是np难问题，因此多目标生鲜品冷链配送联合调度问题也是np难问题。cplex只适合求解现实生活中较为简单的小规模算例，因此无法通过cplex在合理的时间内获得本文问题的解。而智能优化算法已被广泛地应用于大规模、复杂度高的算例中。与单目标优化问题的不同在于，在考虑多个目标时，这些目标通常都是相悖的，很难在不降低一个目标性能的前提下提高另一个目标性能。在实际的经营活动中，决策者会根据不同的场景和自身的经验以及偏好在所得的帕累托最优解集中选择一个或者多个相对合适的帕累托最优解作为实际问题的解决方案。因此，为得到多目标生鲜品冷链配送联合调度问题的帕累托最优解集，本文根据所提问题和模型的特点，利用nsga Ⅱ对构建的模型进行求解，算法流程见图2。

图2 nsga Ⅱ流程

根据所建模型的特点，设计以下编码方案：染色体采用自然数编码；染色体包含3个子串(订单加工顺序子串，负责加工各订单的加工人员子串和配送路径子串)。这种编码方式的优势在于可以十分便捷地将信息直接输入染色体中，不需要复杂的计算和解码过程。例如，加工配送中心有6个客户订单待服务，有2名加工人员，若生成的染色体如图3所示，则该染色体表示加工人员1需要依次加工订单3和6，加工人员2需要依次加工订单1、2、4、5，配送中心共需要发出3个车次。在配送路径子串3中0用于分隔不同车次，表示车辆从配送中心出发最终又回到配送中心。

图3 染色体示意图

2.2.1 快速非支配排序

快速非支配排序是nsga Ⅱ的关键步骤之一，其基本原理是根据种群中染色体之间的支配关系对种群进行等级划分，从而使算法可以快速向帕累托前沿方向进行搜索。将本文问题转换为最小化问题后，假设支配染色体的染色体的数量为，被染色体支配的染色体的集合为。快速非支配排序的主要步骤如下：

分别计算种群中每一个染色体的和，如果染色体支配染色体，即