考虑食品新鲜度的健身营养餐配送路径优化

成 冲，蒋洪伟

(北京信息科技大学 信息管理学院，北京 100192)

0 引言

随着经济的发展和人民生活水平的提高，人们在健身方面的重视程度与投入越来越高，中国健身房总量已与美国持平，在北京、上海高度集中，在其余新一线城市同样潜力十足；健身营养餐取代传统膳食成为健身爱好者的一种新生活方式，也带来了新的市场需求和商机。而新零售模式的兴起使得不同行业与互联网技术的融合在不断加深，尤其是即时配送行业，专人直送、代买代送等业务模式不断更新，但仍以外卖业务为主。现阶段已有许多提供健身营养餐的商家，其配送方式同样以外卖配送平台为主，难以形成批量规模。

对于外卖配送以及生鲜产品末端配送的路径优化已经有一定的研究。余建军等[1]以大连市的一家盒马鲜生门店作为研究对象，使用遗传算法对其末端生鲜产品配送路径进行了优化，同时考虑了在不同的客户满意度条件下配送成本的问题。李畅等[2]以某市多家便利店中易变质的沙拉产品为研究对象，考虑到了配送至门店时食品的新鲜度，对比了使用差分进化算法和蚁群算法进行路径优化时的配送成本，最终发现配送成本与食品的平均新鲜度是相悖的。王帅等[3]通过建立客户满意度模型，研究了在顾客通过O2O外卖平台订餐的背景下，不同配送路径、时间窗以及配送车辆数对顾客满意度的影响。刘扬[4]以长春市为研究背景，以WK公司为研究对象，从企业运营的角度对健身营养餐配送方案进行了分析与对比。曾允菁[5]通过对我国健身房消费现状的分析，提出健身房可以通过提供健身营养餐、营养补剂的方式来创造良好的客户体验。李旭等[6]研究了在新零售背景下的生鲜产品末端配送路径优化，以青岛市某盒马鲜生门店为例，设计了改进的遗传算法，对配送路径进行优化。段砚等[7]以北京某食品公司为例建立了路径优化模型，使用改进的人工蜂群算法进行求解，有效降低了农产品冷链物流成本。

目前针对路径优化的研究较多，但在食品配送路径优化方面，将客户满意度与食品新鲜度结合进行研究的较少，对于健身营养餐配送模式的研究也比较缺乏。本文在新零售的背景下，考虑到健身营养餐餐厅外卖的配送模式以及健身营养餐自身的特点，建立货物新鲜度模型和客户满意度模型，使用改进的遗传算法对问题进行求解，最终得到在满足货物新鲜度和客户满意度的约束下，成本最低的配送路径。

1 配送模式

本文针对健身营养餐商家、健身房以及单独的客户提出了一种健身营养餐运营模式，运用数学建模和改进的遗传算法求解出最佳配送路线，以实现健身营养餐的配送成本、食品新鲜度及用户满意度最佳。

在该模式中，健身营养餐商家通过联合多家健身房，借助健身房场馆内的存储冷柜以存储健身营养餐(借鉴现有自助售货柜)，统一提供运力进行健身营养餐的配送。一方面健身营养餐商家可以形成订单规模，降低运输成本，确保食品新鲜度，另一方面健身房可以用最低成本拓展健身房业态模块。

健身营养餐商家将设计和创建专属的手机APP或微信小程序等线上应用，用户需要通过线上应用方能实现健身营养餐的预定、现场购买等，同时线上应用还会为用户提供健身计划和饮食搭配建议，以及运动社区交流等功能，增加线上应用的用户粘性。健身营养餐商家则可以通过线上应用收集到的预定信息和实际购买量等用户信息，制定补货路线及配送计划。

健身营养餐的配送批量小，频次高，主要的配送方式还是以即时配送为主，因此本文选取的第三方平台为外卖平台。新零售外卖平台具有较传统运输更为多变的订单分配以及路径选取问题，外卖配送员的出发起始位置是不同的，配送员在平台中随时会接到订单，且订单的商家与消费者都是不同的，配送员在完成每次配送任务之后并不用返回特定的配送中心。本文假设，健身营养餐餐厅的订单分为两种：一种为普通的顾客订单，一个客户只订购一份外卖，配送时间决定了该类客户的满意度，对于这种客户，必须要满足时间窗、满意度的约束，同时还要保证食品的新鲜程度；另一种为健身房订单，健身房会与专业的健身营养餐餐厅合作，批量地订购健身营养餐，餐品送达健身房后由健身房进行保存，在会员需要的时候提供给会员，所以该类订单对于时间窗和客户满意度的要求可以放宽。因此本文研究的健康餐配送问题，是一个考虑客户满意度以及货物新鲜度的带时间窗路径优化问题。图1为健康餐配送流程。

图1 健身营养餐配送流程

2 模型建立

2.1 假设条件

本文的研究中，客户提交订单后配送平台将获取所有客户的地理位置。假设条件为：

1)所有的订单由一个配送中心送出。

2)客户分为普通客户和健身房，一般来说健身房是批量订餐，需求量比普通客户要多。

3)外卖骑手由配送中心出发，在送餐结束后返回配送中心。

4)外卖配送时间发生在外卖午餐订单量最高的11∶00-13∶00之间的2 h内。

5)外卖送达的时间不能超过每个客户的预计送达最晚时间之后的10 min，否则将违反时间窗约束。

6)订单由多辆车配送，每辆车携带的外卖数量不能超过其最大承载数量，否则将违反载重量约束。

7)只有新鲜程度和满意度均大于50%，才不会产生新鲜度和满意度的惩罚成本。

8)单个客户的所有订单要满足时间窗与客户满意度的约束。

9)健身房的订单要满足新鲜度的约束，可以暂时不考虑时间窗和满意度，在规定的时间内送达即可。

2.2 符号定义

N：所有配送点的集合，N={0，1，…，n}。

L：所有配送车辆的集合，L={1,2,…，m}。

xijk：外卖骑手k是否从i点运动到j点，若是则为1，不是则为0。

dij：点i到点j的距离。

Q：外卖骑手电车的最大载货量。根据调查，市面上各大平台使用的送餐外卖箱基本是25 L，可以放置10～15份外卖，本文假设电车最大载货量为15 L。

q：需求点的货物需求量。

ETi：顾客满意的最早送达时间。在本文的假设中最早送达时间设置为顾客的下单时间。

DTi：预计外卖送达时间。

LDTi：顾客可以接受的最晚送达时间，只有在这个右时间窗内送达，顾客才会接受。在本文中，可接受的最晚送达时间设置为DTi后10 min，若超出10 min，则违反了时间窗的约束。

t0：货物从商家开始配送的时间。

t0ik：货物从商家由车辆k配送到达配送点i时的时间。

θ：食品的新鲜度。

η：顾客的满意度。

C1：配送固定成本。

C2：配送可变成本。

F：配送总成本。

2.3 数学模型

2.3.1食物的新鲜度

食品的新鲜度主要与配送的时长以及食品的保质期有关，新鲜度函数如下：

θi=2-e(max(t0ik-t0,ETi-t0))ln2/T

(1)

式中T为食品的保质期。由于本文所有的订单均发生在午餐时间11∶00-13∶00，因此保质期T被设定为2，表示餐品在2 h之内送达才不会变质。

2.3.2顾客的满意度

如果不是在外卖平台上指定了送达时间，一般情况下，我们都希望外卖越快送达越好，特别是对新鲜程度要求较高的食物。本文假设所有订单全部都未指定送达时间，因此不考虑客户可接受的最早送达时间。满意度函数如下：

(2)

在预计外卖送达时间DTi之前，客户的满意度为1；在最晚送达时间LDTi之前，每超时1 min，满意度将下降10%；在超过了预计外卖送达时间10 min后，客户的满意度将会降为0。在本文的假设中，若客户满意度下降到0以下，将会违反满意度的约束。

2.3.3配送成本

餐品的配送成本分为固定成本C1与可变成本C2。固定成本包括车辆固定成本与人员固定成本，本文站在商家的视角，需要考虑配送人员每单的工资以及每辆电车的固定成本。一般情况下，外卖配送平台骑手的工资是按骑手配送订单量决定的，每单的工资会根据骑手的总配送订单数从3元到10元递增，本文假设骑手每单的工资为5元，每辆电车的出行固定成本为2.25元，共m辆车。每条路径由1辆车以及1个骑手完成。配送的可变成本包括距离成本、新鲜度损失成本和满意度损失成本。在顾客满意度降到50%之后，满意度每下降10%，将会产生0.5元的满意度损失成本；在食品新鲜度降到50%以后，新鲜度每下降10%，将会产生1元的新鲜损失成本。固定成本与可变成本函数分别如式(3)、(4)所示。

(3)

i,j,r,u∈N,i≠j

(4)

式中：ηv为超出预计最晚送达时间5 min后的顾客满意度；θv为送达后所有新鲜度低于50%的订单的实际新鲜度。

2.3.4目标函数与约束条件

目标函数与约束条件如下：

(5)

(6)

xij=1i,j∈N,i≠j

(7)

(8)

(9)

0≤t0ik≤LDTii∈N

(10)

θ≥0

(11)

η≥0

(12)

式(5)表示要取总成本的最小值，式(6)表示每一个需求点都会被配送到，式(7)表示每一个配送点仅有一个外卖骑手进行配送，式(8)表示每一个骑手所携带的外卖数量不超过电车所承载的最大数量，式(9)表示一条路径上的两个配送点是由一辆车进行配送的，式(10)表示外卖送达的时间不能超过顾客可以接受的最晚送达时间，式(11)表示不能违反食品的新鲜度约束，式(12)表示不能违反顾客满意度约束。

3 算法设计

遗传算法(genetic algorithm,GA)是一种启发式算法,其实质是在优化空间中随机初始化一些种群，以群体中所有个体为对象，利用随机技术指导，有效地搜索编码参数空间，然后根据交叉和变异操作寻找新解，并不断迭代寻找全局最优解。其中，选择、交叉和变异构成了遗传算法的遗传操作。参数编码、初始种群设置、适应度函数设计、遗传操作设计和控制参数设置是遗传算法的核心内容。本次研究在传统的遗传算法中加入了自适应操作与局部搜索操作，增强了算法的性能，得到的结果更优，改进的遗传算法流程如图2所示。

图2 改进的遗传算法流程

3.1 染色体编码

本文涉及多个配送点和一个配送中心，使用多辆车进行配送。遗传算法的编码方式有多种，常用的编码方式有二进制编码、浮点数编码、字符编码等。本文使用自然数编码的方式构造染色体，例如有10个顾客需要配送，最多可以使用3辆车进行配送，那么这10个顾客的编码为1、2、…、10，3辆车的编码为11、12、13。在这10个顾客中有9个插入点，将配送中心随机地插入这9个点中，生成由不同车辆配送的多条路径：

车辆1：0-1-2-3-0

车辆2：0-4-5-6-7-0

车辆3：0-8-9-10-0

这3条路径的染色体编码为(1,2,3,11,4,5,6,7,12,8,9,10,13)，当配送点的数量为n，最大使用车辆数目为m时，染色体编码的长度为n+m-1。

3.2 适应度函数

遗传算法中染色体的好坏是由适应度来决定的，一般来说，适应度越高，代表染色体的质量越高，生存能力越强，所以适应度函数得出的结果越高越好。本文的目标函数是使配送的总成本最小，所以适应度函数取为总成本函数的倒数：

(13)

3.3 选择操作

本文采用轮盘赌选择法，根据个体的适应度来选择，适应度大的个体将被选取，进行下一步的操作。

3.4 自适应操作

在遗传算法中，染色体的交叉概率和变异概率直接影响了算法结果的优劣以及收敛性。交叉概率如果过高，就会导致适应度高的优质父代染色体被破坏，若过低，则产生新个体的速度将会变慢；变异概率过高会导致遗传算法变为随机搜索算法，过低则不易产生新的个体结构。为了避免发散和陷入局部极小,要保持种群中“好”的个体,需要自适应地调整交叉概率Pc和变异概率Pm，这可以通过对高适应度的解降低Pc和Pm的值、对低适应度的解提高Pc和Pm的值来实现。当高适应度的解加快GA收敛的同时,低适应度的解防止GA陷入局部极小[8]。通过自适应操作来保留种群中适应度高的个体，而将种群中适应度不高的个体进行交叉和变异操作。加入自适应操作后，采用M.Srinivas等[9]提出的公式计算交叉概率与变异概率：

(14)

(15)

3.5 交叉操作

1)选择父代染色体

根据自适应的Pc选择两条父代染色体，在每条父代染色体中随机找到两个位置相同的点截取片段。

2)移动截取片段

将第一条染色体被截取的片段移到第二条染色体的最前面，同理，将第二条染色体被截取的片段移到第一条染色体的最前面。

父代染色体1变为：

父代染色体2变为：

3)生成子代染色体

将每条染色体中第二个重复的基因位删除，生成两条子代染色体。

3.6 变异操作

由于本文的编码方式为自然数编码，为了避免产生相同的基因，本文使用逆转的方法对染色体进行变异操作，首先随机选择两个基因位，将这两个基因交换位置，生成新的染色体。

3.7 局部搜索操作

为了提高模型的性能，防止算法进入局部最优，将局部搜索操作引入算法之中。该操作的大致步骤是：首先随机选取路径中的一个配送点a，将这个配送点从原有路径所有顾客点的集合B中移除；再从移除该点后的配送点集合B′中找到与其相关性最大的一点移除并与该点放到同一集合A当中，相关性与两点之间的距离以及两点是否属于同一路径有关；然后从被移除点的集合A中随机选取一点重复上述操作n-1次，最终移除n个配送点；在完成移除操作后进行重新插入操作，找到与被移除点产生目标增量(即成本增量)最少的一点作为插入点，之后找到最大目标增量最小值的被移除点作为第一个重新插回的点，重复此步骤直到所有被移除点重新插回顾客点集合B中。

4 算例研究

4.1 数据整理

本文以北京市朝阳区常营商圈中长楹天街商业街的某健身营养餐品牌为研究对象，选取周围半径4 km以内的20个顾客进行配送，所有顾客的订餐时间均在11∶00-13∶00之间。现已知顾客下单的时间以及预计最晚送达时间，配送人员对每个顾客点的服务时间为90 s，每个顾客的地址经纬度、下单时间、需求量以及预计最晚送达时间(即右时间窗)如表1所示。表中第1～17号订单为普通顾客的外卖订单，包含下单时间和预计最晚送达时间；第18～20号订单为健身房批量订餐。批量订购的健身营养餐一般是长期的订餐需求，所以没有订餐时间，餐品在14∶00以前送达即可，送至健身房后存入冷柜当中。配送中心以及各个配送点的距离如表2所示。

表1 配送点信息

表2 各配送点之间的距离 m

4.2 参数设定

在本文改进的遗传算法中，将种群大小设为100，最大迭代次数设为30，交叉概率Pc设为0.9，变异概率Pm设为0.05。

4.3 模型求解

使用MATLAB R2018b进行求解，经过30次的迭代后，模型求出最优解，共4条路径，如图3所示，迭代优化过程如图4所示。

图3 最优配送路径

图4 优化过程

配送路径如表3所示，共使用4辆车进行配送，车辆固定成本为9元，配送总成本为67.09元。模型求解得出车辆行驶总距离为29.043 km，配送可变成本为58.09元。

表3 改进GA求解的配送路径

4.4 算法对比

1)传统遗传算法求解结果

本文使用的改进遗传算法在传统遗传算法的基础上增加了自适应与局部搜索操作，若使用未改进的传统遗传算法求解模型，计算出的成本比改进的算法要高。传统GA求解的配送路径如表4所示。

表4 传统GA求解的配送路径

从表4中可以看出使用车辆数为6。计算可得：车辆固定成本为13.5元，车辆行驶总距离为37.02 km，配送可变成本为74.04元，配送总成本为87.54元。

2)加入自适应操作的遗传算法求解结果

在传统遗传算法的基础上加入自适应操作之后，车辆行驶总距离为34.697 km，配送可变成本为69.39元，使用4辆车进行配送，配送路径如表5所示，车辆固定成本为9元。配送总成本为78.39元。

表5 加入自适应GA求解的配送路径

5 结束语

本文提出了一种健身营养餐外卖的配送模式，研究了健身营养餐外卖配送的路径优化问题，针对健身营养餐外卖的一些特点建立了包含客户满意度以及食品新鲜度的模型，设计了改进的遗传算法对其进行求解，以求在不违反新鲜度、满意度、车辆最大载重以及时间窗的约束下成本最低的配送路径。通过实例验证和算法对比可以得出，改进的遗传算法相较传统遗传算法性能更加优越，最优解更佳。