供应链视角下餐饮O2O模式的配送路径优化

周李晶

（华北电力大学 经济与管理学院，北京 102206）

1 引言

电商的迅速发展使实体店受到前所未有的压力，各零售商纷纷转型，线上和线下共同协力满足客户要求，线上接收客户订单，完成资金流和信息流的流通，线下致力于服务质量，保证顾客的忠诚度。随着市场竞争的加剧，电商企业需根据市场需求制定战略以加大市场份额，O2O模式的优势愈发明显。

O2O 模式指的是线下的商务时机和互联网联合，使互联网变成线下业务的平台。最典型的O2O模式应用案例是餐饮行业，外卖的飞速发展使消费者的多样化需求更能得到满足，快节奏生活中点外卖成为工作人群的首选。O2O供应链是构建以交易平台为中心的物流网络，顾客在平台上下单，订单信息通过汇总移交给食品零售商进行生产制作，然后平台发放配送订单，由配送员根据实际情况选择接收配送订单，完成配送任务。配送是最接近消费者的一环，是O2O供应链的关键环节之一，配送效率的提升可以促进供应链整体效率的提升，供应链效率的提升也进一步提高了物流配送效率，两者相辅相成[1]。

中国餐饮外卖市场正在发生一些深刻变化，推动这些变化的既来自于外部环境，也来自于内部原因。从配送入手优化配送路线，可以节约成本并提高效率，从而提升顾客满意度，保证顾客忠诚度，使供应链整体效益得以增加。以供应链视角去解决配送这个瓶颈问题，可以从多个主体出发考虑路径优化问题，在保证供应链整体效益基础上尽可能满足多方需求。

O2O 模式的兴起给学者们提供了新的研究思路。孔栋，左美云和孙凯[2]在早期总结出3个分类维度并构建了O2O 模式分类体系。赵道致和杨洁[3]提出决策模式的选择策略，根据决策主体构建三个模型并分别分析其利润。赵志伟和乔晗[4]通过大数据分析了加盟外卖平台后利润变化的影响因素。尤宝庆[5]将供应链管理融入O2O配送模式中，分析两者关联，为电子商务和物流业的发展提供新的视角。顾淑红和花均南[6]基于茶叶行业特点分析消费者特征以增加柔性化。赵泉午[7]等人构建了配送中心到需求点近似配送距离的选址及分配优化模型。陈萍和李航[8]以顾客满意度最大化为目标，其中满意度以到达时间的函数进行描述，对配送路径进行优化。

餐饮O2O 配送是多方参与的活动，牵扯到多方利益，但大多数学者仅仅考虑单目标的优化。缺乏从供应链视角去考虑路径优化问题，因此本文在考虑O2O配送特点的基础上，结合道路交通状况，考虑配送车辆的最大里程数基础上，搭建配送总时间最短作为上层目标，固定成本、配送成本和时间惩罚成本之和最小为下层目标的双层规划模型，考虑车辆总数和顾客时间窗，采用NSGA-Ⅱ算法求得可行的订单分配和配送路径。

2 问题描述

在餐饮外卖环境基础上进行研究，首先要分析外卖配送的特点。通常情况下，外卖订单的接单高峰期是每天中午和晚上用餐时间，大量配送员被调用起来完成分配或者主动接收订单，接到订单后立即赶往餐厅实体店等待食品的完成，然后再立即送至客户手中，其间有时间限制。时间越短，顾客满意度就越高。时间是外卖配送重点关注的因素之一，同时平台也关注配送成本的问题。餐饮实体店希望平台能够高质量地完成线上订单以及线下配送工作，从而提高顾客的忠诚度，平台则希望在满足餐饮实体店的前提下缩减物流成本来获得更多利润。

因此本文研究的内容可以描述为：配送员在开始接单时刻前到达起始点，起始点是地区中心大型商业聚集区，从起始点开始接单后到多个商家和消费者间进行取餐和送餐，对于同一个订单要保证先取餐后才能送至客户。合理分配订单和配送路径，使配送员经过合理的路线完成配送任务，再次回到起始点进行下一次接单。在满足消费者需求、车辆总数和最大里程数等限制下，商家以总时间最短、平台以配送成本最低作为目标为消费者进行服务。

结合外卖配送特点可作如下假设：

（1）每个时刻有等待接单的配送员数量限制；

（2）外卖配送通常采用电动车进行配送，有最大行驶里程限制；

（3）将满足每个消费点的需求，并且只能由一辆车访问一次；

（4）配送途中不接单，有商家消费者先后次序的要求；

（5）消费点处有时间限制，到达时间超过规定时间要有惩罚；

（6）高峰期送餐会受到路况信息的影响，这种影响已知；

（7）调动配送员从起始点出发，在交付任务完成后返回起始点。

3 数学模型

3.1 符号说明

R={m|m=1,2,...,M} 表示餐厅集合;

C={n|n=1,2,...,N} 表示消费者集合;U=R ⋃C 表示所有节点集合;

订单o=(mo,no),mo ∈R,no ∈C；

I表示订单的集合；

V={k|k=1,2,...,K}表示车辆的集合；

L表示每辆车充满电后运行的总里程；dij表示从i到j的距离，i ∈ U,j ∈U ；

p表示单位运输成本；

v表示正常行驶的速度；

αij表示i到j路径的交通路况系数；

E表示车辆起始点；

Te表示从起始点出发的时间，Te=0；

TAi表示车辆到达i的时间点；

TLi表示车辆离开i的时间点；

[a,b]表示消费者的时间窗；

PT表示餐厅备餐时间；

WT表示为顾客服务时间；

Ti表示到达时间，i ∈U；

β表示单位时间惩罚成本；

FC表示固定成本；

PC表示时间惩罚成本。

决策变量：

xijk：车辆k从节点i驶向j则取1，否则为0；

yok：把订单o分配给车辆k则取1，否则为0。

对符号dij进一步说明，考虑到现实生活中道路设施布置，总是存在任意点i到j的可行路径存在，且距离长度使用曼哈顿距离进行测算。

3.2 模型建立

上述餐饮配送路径优化问题可以通过以下双层规划模型进行描述：

上层模型：

上述模型中，目标函数（1）表示的是以餐饮商家为出发点考虑最小化配送时间，由准备时间、运输时间、服务时间三部分组成；约束（2）保证每个顾客只访问一次；约束（3）和（4）表示从起始点出发的车订单完成后回到起始点；式（5）是连续性约束；式（6）表示车辆总数限制；约束（7）表示每辆车总里程限制；约束（8）是每个订单只能分配给一辆车；式（9）是决策变量约束。

下层模型：

上层模型的约束同样也是下层模型的约束。此外，下层模型中，目标函数（10）表示从平台出发的最小化总成本，并且分为三个部分：派车固定成本、运输成本和时间惩罚成本；式（11）表明从起始点出发时间为0；约束（12）表示访问顺序的约束，先到餐饮点再到消费者；式（13）表示从离开i点到达j的时间点计算；式（14）和式（15）分别是离开餐饮点和消费点的时间点计算；约束（16）是时间窗限制。

其中时间惩罚成本函数如下所示：

惩罚函数中惩罚成本与超出消费者时间窗的时间存在线性关系，这是符合实际情况的。

4 算法设计

本文建立的上述模型是典型的整数双层规划模型，属于NP-hard问题，没有精确的算法，遗传算法是常用来求解双层模型的算法。双层规划模型是一个需要综合考虑上下层求解的问题，并且上下层具有不同的优先级。上层是从餐饮商家出发考虑建设更快的响应系统，仅对上层模型进行分析，在数量不大的情况下接收到的订单都可以进行相对合理的分配。但下层决策者不光要完成时间上的要求，还需要在订单和路径安排上进行优化，使总成本达到最低。对这个问题，需采取时间惩罚函数连结两层模型，使得两者彼此牵制，才能得到双方都比较满意的结果。

结合实际意义和模型的特点，本文采用NSGA-Ⅱ算法进行求解。NSGA-Ⅱ算法是Deb 等学者在2000年对NSGA算法的改进，由此能通过计算得到一系列多样性好、分布均匀的最优解集。NSGA-Ⅱ是目前最流行的多目标遗传算法之一，它降低了非劣排序遗传算法的复杂性，具有运行速度快，解集的收敛性好的优点。NSGA-Ⅱ算法的流程具体如下：

（1）随机产生初始化种群。

（2）使用帕累托优胜级别排序法对种群内全部个体进行分级排序。

（3）根据种群个体特点选择精英个体进入下一代种群。

（4）使用模拟二进制交叉等方法产生子代种群。

（5）将父代中精英个体和子代种群合并构成下一代种群。

（6）如果达到迭代次数条件则停止并输出结果;否则继续循环。

5 算例结果与分析

为验证所建模型的合理性和算法的有效性，本文以北京市昌平区回龙观镇地区的外卖配送为例，将商业聚集地点作为餐饮商家，将回龙观各小区作为消费者，通过查阅资料获取合理的相关数据，构建测试算例并进行仿真实验。

根据地图实际情况建立坐标轴，商家和消费者地点坐标见表1 和表2。假设某时刻T，外卖平台接收到30 个订单，订单具体情况见表3。假设在T 时刻，在初始点有20辆车等待分配，由于使用电动车进行配送，最大里程数为15km，单位运输成本4元/km，速度15km/时，备餐时间和等待时间都是5min，单位惩罚成本0.5元/min，固定派车成本5元/辆，交通阻塞系数为随机生成0.5-1范围内的数来降低行驶速度，时间窗采用实际平台上常见的标注时间30min。设计算法采用Matlab2014a实现。

表1 餐饮商铺坐标

表2 消费者坐标

表3 订单信息

最终路径规划图如图1所示，商业聚集区比较聚集，居民区往往距离热闹繁华的商业街有一定距离，而且小区分散较广，远不如商业区的密集程度。这也是导致配送员在分配时只能拿到1 至2 个订单的原因。从图中也可以发现，距离下单餐馆比较近的地区往往多单一起配送，而位于较远处的消费者配送时目的较为明确，方向比较固定。

图1 最终配送路径规划图

表4 最终求解的订单分配与路径规划

实验结果表明，在满足时间约束条件下，所花费的成本为667.93 元，其中固定派车成本20 元，从表4可以看到20 辆车都进行派遣来满足上层时间的要求，惩罚成本为31.74 元，并不是很高，除个别订单外，大部分满足在30min 以内。每个人接收1 至2 个订单，比较符合现实情况。

采用NSGA-Ⅱ算法的收敛图如图2 所示。该算法的收敛速度快，迭代50 次即趋于平稳，算法效率高，说明该算法是有效可行的。

6 研究结论与展望

图2 下层模型求解的收敛曲线

本文从供应链的角度，从餐饮商家和外卖平台两个参与主体出发，解决了餐饮O2O 模式中各主体不同优化目标的问题，建立了上层模型时间最短,下层模型配送成本最低的双层规划模型,并采用NSGA-Ⅱ算法来进行求解,算例求解的结果证实了模型和算法的合理性和有效性。除此之外,实验结果表明,为了满足商家时间上的要求，尽可能把所有配送车辆派遣出去，而且惩罚成本比派遣的固定费用更影响决策。因此，本文提出以下建议：各主体应该具备基本的供应链思维，不应盲目追求自己的目标，而是把供应链作为一个整体来寻求利益最大化；外卖平台应该提升自己的管理能力，要充分考虑顾客和餐饮商家的感受，建立起公平完善的管理机制，合理地进行决策；物流专员也应该提高服务水平，以保持较高的客户满意度。

在未来的研究中，还可以重点关注自营物流与第三方物流的合作，并考虑加入订单不确定因素，更接近现实生活。