电子商务生鲜农产品冷链配送耗时控制算法

杨正华，石俊萍

(吉首大学，湖南 吉首 416000)

1 引言

在电子商务冷链配送过程中，装卸、包装等环节均需在规定温度下操作，而冷链运输方式除了公路运输、铁路运输等，也可以多种运输方式合作。但是多运输方式会包含更多的运输风险。冷链运输中，生鲜食品冷链是一个以点和线为基础、以冷藏(冷冻)技术为依托、以提高配送效率、保证食品质量、强化服务质量为最终目标不断优化整体运作模式的过程。电商大环境背景下，生鲜农产品的冷链配送相比普通的配送模型更加复杂，人们对食品安全问题的关注也不断刺激冷链行业的发展。与普通物流相比，冷链物流对配送时效性要求更严格，冷链配送主要针对的是冷藏或者冷冻产品，相关农产品可分为两类，一类为新鲜蔬菜、水果、肉、水产等初级农产品，另一类为通过加工的物品为熟食、牛奶、果汁等。因为冷链配送对象均要求在低温环境下配送，而且对配送时间的控制也尤为重要。若货品的送达时间不符合客户要求，物品就可能会因在途时间过长导致其品质下降，甚至腐坏，增加电商货损。另一方面也可能导致客户评价降低，影响电商销售额。

因此，提出电子商务生鲜农产品冷链配送耗时控制算法。考虑到冷链配送的特殊性，对其各个决策要素如配送路线、货品质量、配送中心等进行了系统性的分析和合理地安排。为实现对配送耗时的控制，合理的按照客户要求和车辆额定载重量，安排每条路线中客户的配送路线，使配送耗时最小对各个相关因素的定义和目标函数建立基于配送耗时的数学模型，同时对模型进行约束，最后通过粒子群优化算法选择出耗时最短路径完成控制算法。实验验证了该算法能够有效地对冷链配送进行合理控制。

2 冷链配送耗时影响因素分析

冷链配送耗时问题[1]的决策要素有很多，主要包括车辆、运送路线、配送中心、货品质量、约束条件、目标函数等。

1)配送中心是集分捡、配送、组织送货为一体的物流配送点。在配送范围较广的情况下，为减少配送时间，提高服务质量，往往会采用多级配送，多级配送网络如下：

2)货物，即配送对象，不同的客户有不同的需求，同一需求的货物可以归为一类，为减少耗时，将货物品种、数量、体积、送货时间地点做好标注，一般情况下，一个客户的订单只需要使用一辆车配送，但是如果货物的质量或者体积超过了运输车辆的额定载重量，这时考虑到运输时间就要安排多辆运输车同时配送。

3)在冷链配送时必须使用有冷藏、冷冻功能的货车，以保证配送耗时过长时生鲜农产品的质量，同时提高运输效率。车辆需要考虑到的内容主要有车辆载重量、行驶距离等。不同车辆的额定载重量也不同，载重量较大的车辆能够一次完成大量配送任务，减少往返次数，节约了送货时间，但是同时会增加油耗，在配送任务较少的情况下，车内空间限制也会造成资源浪费，因此在实际状况允许的情况下，配送中心[2]应配备不同载重量的运输车辆，根据不同配送要求进行合理调度，合理的掌控运输成本和运输耗时。

4)运输路线即车辆在运输过程中的行驶路径，是运输耗时控制过程中最主要的考虑因素。运送路线直接影响着配送时间和货物质量。本文遵循以下原则对运输路线进行安排：严格执行客户的时间窗[3]要求，保证在客户要求的时间范围内到达配送目的地；在保证按时到达目的地的同时，使车辆的行驶总路程最短；每条运送路线的配送目标总量不得超过运输车辆的载重量。

带有时间窗的路径问题是指在配送路线的基础上，每个客户要求的送货时间都在一定的时间段内。时间窗可分为软时间窗[4]和硬时间窗[5]，软时间窗为除了规定的配送时间段[m，n]还给定了另外一个较为宽松的时间段[M，N]，即使到达配送目的地时不在[m，n]内，只要配送时间在[M，N]时间段范围内，则可以继续配送。硬时间段是指货物的送达时间必须在时间[m，n]范围内，也就是说若车辆提前到达，必须等到m时才能卸货；若车辆在规定时间不能准时到达，则不能够进行配送。

5)冷链配送耗时的约束条件主要为：

满足时间窗要求；

满足客户对货物质量及数量要求；

配送的货物运载量不超过车辆的额定运载量。

6)冷链配送耗时常用的目标函数[6]主要有：

①运输车辆的行驶路程最短。合理的保证车辆行驶里程数，可以在更短的时间内把更新鲜的生鲜产品送给客户，既保证了时效性，在另一方面又降低了配送成本；

②准时性最好。生鲜产品和普通农产品不同的是必须保证货物质量，所以在配送的过程中要充分考虑客户要求的配送时间窗，并且针对不同的时间要求对配送顺序进行合理安排；

③综合费用最低。在冷链配送的过程中，在考虑耗时的同时也要考虑到将费用降到最低，保障经济效益。

3 生鲜农产品冷链配送耗时控制算法

3.1 配送耗时数学模型

配送耗时问题[7]是指车辆从配送中心出发到将货物配送到目的地期间所花费的时间。合理的按照客户要求和车辆额定载重量，安排每条路线中客户的配送路线，使配送耗时最小是配送耗时模型的目标。可定义参数如下：t表示单位路程的运输耗时；Q表示车辆额定载重量；dij为客户i和j之间的距离，i，j=1，2，…，n，i≠j；xi为配送货物量；xijk为0，1变量，若车辆经过(Pi，Pj)路段xijk=1，反之xijk=0；则可得数学模型为

(1)

(2)

(3)

(4)

式(1)为模型目标函数；式(2)表示每个客户点只被相同车辆访问过一次；式(3)表示车辆的起始点和终点均为配送中心；式(4)表示需要运输货物总量不超过车辆的额定载重量。

3.2 算法实现

为了控制配送耗时，优化配送路径，在满足客户需求的同时选择出耗时最短的路径。本文采用粒子群算法[8]对路径进行寻优，粒子群算法为一种并行算法，该算法从随机解出发，通过迭代寻找最优解。

在粒子群算法中，由n个粒子组成种群X=(X1，X2，…，Xn)，种群在D维空间[9]内以速度Vi=(Vi1，Vi2，…ViD)T飞行，在粒子的飞行过程中，每经过一个位置都会产生一个解，其飞行过程即为搜索过程[10]，并根据单个粒子自身飞过的历史最优点Pi=(Pi1，Pi2，…，PiD)T和该区域内所有粒子飞过的最优点Pg=(Pg1，Pg2，…，PgD)T来更新位置和速度，较为常用的更新方式如式(5)

(5)

式(5)中，c1、c2分别表示加速因子，r1、r2为[0，1]之间的随机数，ω代表惯性系数；

每一维的速度限制在vmax(vmax>0)内，当vk=-vmax，vk>vmax时，vk=vmax；当vk<-vmax时，vk=-vmax。

其算法流程如下：

步骤1：对粒子的位置和速度进行初始化；

步骤2：计算该区域内所有粒子的适应度值[11]；

步骤3：通过下式更新个体最优和群体最优；

(6)

步骤4：通过式(5)更新粒子的位置和速度[12]；

步骤5：若满足终止条件，算法结束；否则返回步骤2。

在粒子群算法中，在搜索后期可能会出现过早收敛于局值问题，因此可以在初始搜索中使用较大的加速因子C1，后续搜索中使用较小的加速因子C2，使粒子能够在搜索空间分散的比较自由。随着迭代次数的不断增加，使C1线性递减，C2线性递增从而加强粒子全局的收敛能力，其表达式如下

C1=C1s+k(C1e-C1s)/kmax

(7)

C2=C2s+k(C2e-C2s)/kmax

(8)

式(7)、(8)中，C1e、C2e代表加速因子C1、C2的终值，C1s、C2s表示C1、C2的初值，k表示当前迭代次数，kmax表示最大迭代次数。

粒子群优化算法的关键是找到粒子的位置与问题的解相对应，通过构造2n维的空间对应n个客户点的物流配送路径优化问题，即粒子i对应的2n维向量Z分成两个n维向量分别Zix和Ziy。对粒子i的向量Zix取整，表示为int(Zix)，可得到配送中心分配给客户点i的车辆J。J行驶路径可取决于向量Ziy的大小，即寻找完成配送的需求点，按照i对应的Ziy的大小，从小到大进行编号，完成配送路径选择。

例如，若有7个需求点，其第i个粒子的位置；向量如表1所示：

表1 解码前粒子i的2n维向量

根据解码可配送车辆在每个配送目标的具体情况，如表2所示：

表2 解码后的粒子i的2n维向量

则车辆的行驶路径为(0代表配送中心)：

1)车辆1：0-1-6-0

2)车辆2：0-7-2-3-0

3)车辆3：0-4-5-0

4 算法验证

为验证所提算法的有效性，进行实际案例分析。某农产品冷链运输公司接到任务，现有10个需要服务的客户，相关参数如下表：

表3 客户需求量及时间窗

表4 各项参数数值

表5 各需求之间距离

所有客户中，客户p2要求的配送时间最早，因此将其作为路线一的第一个配送目标，若第二个客户为Pj，则p2至Pj的配送耗时为：

maxJ2，j=max[tXjS2，j-T5(j)]

(9)

通过所提控制算法计算结果得maxJ2,j=J2,5=13.2，因此第二个客户为p5，再设第三个客户为Pj，则p5到Pj的配送耗时为：

maxJ5，j=max[tXjS5，j-T5(j)]

(10)

通过计算得maxJ5，j=J5，10=8.4，因此第三个配送目标为p10，根据上述算法重复计算，最终获得第一条路线为P0-P2-P5-P10-P0，总载重量为2.5吨。

除去线路一的目标客户，要求配送时间最早的客户为p8，因此p8是线路二的第一个配送目标。若第二个目标为Pj，则p8到Pj的配送耗时为：

maxJ8，j=max[tXjS8，j-T5(j)]

(11)

根据计算获得maxJ8，j=J8，4=7，因此路线二的第二个客户为P4。按照上述算法依次计算获得路线二为P0-P8-P4-P9-P0，车辆的总载重量为2.8吨。

除去路线一、路线二的目标客户，根据要求配送时间最早的客户为P3，根据上方法计算，得出第三条路线为P0-P3-P7-P6-P0，车辆的总载重量为2.1吨。

综上，为将配送耗时控制到最低，将配送路径分为3条，共需要三辆配送车辆，其路线图如图2，通过实例证明了所提算法能够对配送耗时进行合理控制。

为对比所提算法的耗时改进效果，设定文献[3]提出的基于离散布谷鸟的车辆路径优化方法以及文献[4]提出的带软时间窗的连锁超市配送车辆路径优化算法的冷链配送条件与所提算法的实验条件相同，对上述实验中的十个用户进行冷链配送，得到配送路径如图3、图4所示：

图3 文献[3]算法配送路线图

图4 文献[4]算法配送路线图

根据图2、图3与图4的对比可以明显看出，传统算法的冷链配送路径比所提算法的路径更长，由于配送车辆的平均速度是一致的，路径越长，算法的耗时也越长。且从图3、图4中可以看出，传统算法下，车辆出现重复配送路径，说明传统算法的应用效果不够理想。

5 结论

为保证生鲜农产品配送质量，提出新的冷链配送耗时控制算法。以最短配送耗时为目标，采用粒子群优化算法获取耗时最短的配送路径。为验证所提方法下的配送耗时，设计实验。实验证明了所提冷链配送耗时控制算法具有可行性，且路径规划效果更好，配送耗时更短。但本文为简化模型运算忽略了一些偶然性影响因素，比如部分道路维修会使路径选择发生错误从而增加配送时间，偶然性因素会在一定程度上影响算法的精准度，针对该问题，日后还需进一步的进行深入研究。