基于GIS的同城O2O外卖车辆路径优化设计

姜晓红 张萌萌

摘  要：同城O2O外卖配送的管理与优化是当前外卖行业亟待解决的问题。依据外卖配送特点、配送时间、餐损控制等约束，建立以最大顾客满意度为优化目标的配送路径优化模型，综合运用GIS技术得到具有可视化、科学性和高效率的优化决策;以某大学校区O2O外卖路径为研究对象验证所建模型的可行性，分别以顾客满意度最大化为优化目标、最短路径为优化目标进行路径优化，加以对比分析，结果显示GIS技术能够提供很好的解决方案。同城O2O外卖配送路径的优化可以方便消费者，降低成本，提高餐饮业的整体服务水平。

关键词：O2O外卖;车辆路径优化;GIS;校园配送

中图分类号：F252.14    文献标识码：A

Abstract： The management and optimization of the delivery of O2O in the same city is an urgent problem to be solved in the current takeout industry. According to the characteristics of takeaway distribution and the constraints of delivery time and meal loss control， the distribution route optimization model with the maximum customer satisfaction as the optimization objective is constructed. With the comprehensive use of GIS technology， visualization， scientific and efficient optimization decision-making has been put forward. Taking the take-out route of O2O in one university campus the research object， the feasibility of the model is verified. The path optimization is carried out with the maximization of customer satisfaction as the optimization objective and the shortest path as the optimization objective， and comparative analysis is made. The analysis results show that GIS technology can provide a good solution. The optimization of the distribution route of O2O takeout in the same city can facilitate consumers， reduce costs and improve the overall service level of catering industry.

Key words： O2O takeout food; path optimization; GIS; campus distribution

0  引  言

外卖配送属于物流配送范畴，但快递与物流配送有很大差异，配送过程中与普通货物配送特征区分明显。具体来讲在配送中快餐外卖特点主要体现在以下四点：外卖特征属性要求不同、服务时效要求不同、配送点作业不同、配送装备特殊性[1-2]。同城O2O外卖配送模式主要有两种：企业商户自营配送模式、互联网在线平台类型。无论是自营配送还是在线平台配送模式，成本仍然很高，存在的问题很多，如尚不能满足网络订餐行业的迫切需求，外卖配送问题重重，配送路线不合理，餐损问题严重，配送时间超时等，外卖配送的管理与优化是当前外卖行业亟待解决的问题。在校园中主要采用自主配送，效率问题一直影响着外卖服务质量其中存在的主要问题包括以下四点：（1）人力成本高，配置不合理;（2）路线规划不合理，浪费人力时间成本;（3）餐损问题严重;（4）时间要求严格[3-5]。因此迫切需要研究同城O2O外卖配送路径优化问题。

路径优化问题是物流配送研究领域中的典型问题，对外卖车辆路径优化方面的研究考虑的优化目标主要是最短路径和最短时间以及客户满意度等方面[6-10]。随着社会发展以及国民生活水平提高，顾客满意度问题越来越被餐饮行业看重。本文以顾客满意度为目标，综合考虑外卖配送的特殊性，以及配送中存在的诸多影响因素，对外卖车辆路径优化进行研究。另一方面，解决该问题的方法主要有以下四类：（1）精确优化方法;（2）启发式方法;（3）模拟方法;（4）人工智能方法[11-13]。越来越多的研究将地理信息系统（GIS）与模型相结合来解决规划问题，如优化物流配送车辆的安排，解决行程路线规划[14-16]。GIS可以作为一种决策支持系统，为物流配送系统提供较优的决策方案。本文将充分利用GIS空间数据处理和分析能力完成物流系统的决策分析。

1  配送路径优化模型

1.1  模型构建

1.1.1  优化目标

依據外卖配送特点，考虑配送员数量及人力成本、配送时间、餐损控制等约束，从外卖车辆配送路径中路况影响下的餐损、顾客满意配送时间两方面构建了以顾客满意度为优化目标的外卖配送车辆路径优化模型。在外卖配送服务中，影响顾客满意程度的因素主要体现在：餐饮中心的食物质量及配套服务、送餐速度、外卖送达后的物品完好情况。因此选取送餐时间、外卖到达后的物品完好情况作为影响顾客满意度的两种影响因素。

（1）送达时间

顾客在外卖平台上拍下订单后会有预期送达时间。将预设的需求时间点记为t。当需求时间t小于等于b（b为外卖客户下单时约定的最迟送达时间）顾客满意时间，顾客满意度不受影响为100%，当配送车辆在顾客预设的时间窗超时抵达时，顾客满意度会随抵达时间下降至0。因此，客户满意度与送货车辆到达时间之间的关系可以用分段函数表示，如图1所示。

（2）外卖送达后的物品完好情况

设定道路等级影响外卖送餐的物品完好情况，将道路等级影响因素设定为道路宽度与道路平整情况。将道路等级分五个等级p，设置系数范围为1～5，对应顾客满意度等级为10～2，具体设置如表1所示。

综合考虑校园外卖特点，配送高峰期与学生下课时间段高度重合等诸多因素，不同场景下顾客满意时间不同，所以设定b分钟作为客户满意度阈值。即，如果时间tb， k<0。假定外卖到达后的物品完好情况与道路整体状况呈现一定的关系，用路线中道路整体状况作为表征物品完好情况的指标，即：

y=Level    p=1，2，3，4，5                                      （1）

其中：Level表示第n条路线的等级是p，p的数值越小，表明等级越高，道路越平整。配送中心编号为0，客户编号为ii=1，2，…，n。

外卖配送顾客满意度模型表示为：

y=                                （2）

其中：m为车辆所经过路径中所有路段的数目。

1.1.2  约束条件

首先，外卖配送车辆每次运送的运输量是有限的，所以每辆外卖车辆所服务的客户需求之和应小于或等于外卖配送车辆的承受阈值，即：

gx≤w    k=1，2，…，m                                      （3）

另外，每位顾客仅有唯一车辆为他服务。故有：

x=1    i=1，2，…，n                                         （4）

只有一辆车到达和离开每个客户，故有：

y=x                                                （5）

其中：j=0，1，…，n; k=1，2，…，m。

y=x                                                （6）

其中：i=0，1，…，n; k=1，2，…，m。

每辆车都从配送中心出发，最后回到原来配送中心，即有：

y=y    k=1，2，…，m                                   （7）

y=0或1。其中i=0，1，…，n;j=0，1，…，n;k=1，2，…，m。

x=0或1。其中i=0，1，…，n;k=1，2，…，m。

1.2  求解算法

ArcGIS软件使用Dijkstra算法计算路径优化问题。Dijkstra算法主要特征是从起点延伸到外层，直到到达终点。算法步骤如下：

（1）在起算階段，S中仅有一个源点，并不包含路径。此时，S=v，v的距离为0。顶点集合U里面包括其他顶点，而v被排除在外。即：U=其余顶点。如果v和U在顶点u中有边，则包含两者的属性记录正常值。即有权值。若两者无边，则权值为∞。

（2）在集合U中选取距离v最小的顶点k。将该顶点加入S中即可。

（3）将k重置为中间点。再次计算U中各顶点长度。若v经k到u的行程较未经k的行程短，可以对u的数值进行修正。修正后，将顶点k的路程作为权重加到边上。

（4）重复步骤2和3，直到所有顶点都包含在S中。

2  实例应用

以某大学校区作为研究区域，选取单个、多个配送中心为例进行路径优化，分别以顾客满意度最大化、最短路径为优化目标进行路径优化，加以对比分析。

2.1  单配送点路径优化

配送点选取位于该大学校区附近的“三顾冒菜”。订单位置随机选取学校宿舍区的九处位置作为配送目的地，其中预期开始配送时间与预期最迟配送时间的差值即为模型中的b值。

将两种实验方案进行对比（如表2所示）。由于校区范围较小，总体配送路线未发生重大变化，仅在局部地区出现小幅度的改动，其发生变化的原因是，考虑到顾客满意度情况，在选取路径时优先考虑等级属性高的道路，而对比实验会选取道路最短作为配送路径。相比之下，考虑顾客满意度的情景更多考虑到配送食物的抵达状态，防止汤水外溢等情况的发生。

2.2  多配送中心的路径优化

（1）以顾客满意度最大为路径选择依据

各配送中心路径信息如表3所示。

（2）以最短里程为路径选择依据（对比实验）

对比项目中仍选取相同配送速度，在属性设置中以配送车辆通行路程作为阻抗，以达到总里程最短的目的，建立对比试验的几何网络模型，求解得到配送路径。对比试验路线如图2。

分别计算基于顾客满意度和最短里程的两种配送路径的顾客满意度，结果如表4。椒麻鸡米饭的配送路线因为可选路径少等原因，在两种方案选取了同样的配送路径。而“三顾冒菜”和“蓝湾咖啡”的配送中心则出现了一些不同的配送路径。对比试验中“三顾冒菜”配送中心的两种方案在图2中的B区域有所差异，对比试验比基于顾客满意度的方案短2.3米，但总体顾客满意度相较最短路径方案，最终满意度增加6，提升1.42%。“蓝湾咖啡”配送如图2中A区域的时候，选取的距离比基于顾客满意度的优化方案少13.5米，但总体顾客满意度相较最短路径方案提升16点，提升幅度为4.97%。总体而言，基于顾客满意度的配送方案，能在保证顾客可以接受的时间范围内，将外卖在运输过程中产生的颠簸等情况降低到最小，从而达到提升顾客满意度的目的。

3  结  论

基于地理信息系统技术，对外卖配送的车辆路径规划进行了优化研究。针对同城O2O外卖配送特点，建立了切合实际的车辆路径优化模型。应用GIS技术进行外卖配送车辆路径优化，使其在决策可视化、效率和可靠性等方面得到改善。通过对外卖配送地理要素特点的分析，建立了外卖配送路网的模型，从顾客满意度这一视角分析问题，力图改善实际生活中以顾客满意最大化的路径优化问题。

参考文献：

[1] 吕晓永. O2O模式下电子商务物流配送现状分析及对策研究[J]. 价值工程，2016，35（7）：98-99.

[2] Dantzig G B， Ramser J H. The Truck Dispatching Problem[J]. Management Science， 1959，6（1）：80-91.

[3] 郭月，张涵. 校园外卖配送体系研究[J]. 中国市场，2016（20）：67-69.

[4] 李童，伍婵提. 淘宝与美团外卖顾客满意度的比较研究——以宁波地区大学生为例[J]. 中国商论，2016（32）：19-21.

[5] 罗琴. 餐饮外卖企业顾客满意度影响因素的研究——以美团外卖为例[J]. 商场现代化，2016（28）：30-31.

[6] 薛亮，郑琰，余伟. 考虑碳排放的贵州省茶叶物流配送路径优化设计[J]. 物流科技，2018，41（10）：9-12.

[7] 郑琰，孟晓露，伍佩琪，等. 电子商务企业物流配送路径优化研究[J]. 物流工程与管理，2018，40（6）：111-113.

[8] 张婷，赖平仲，何琴飞，等. 基于实时信息的城市配送车辆动态路径优化[J]. 系统工程，2015（7）：58-64.

[9] 盧尔赛，李汉卿，赵辉，等. 基于有时间窗的城市配送车辆路径方案优化[J]. 物流技术，2016，35（12）：93-96.

[10] 张湘博，李文敬，周杰，等. 基于深度学习的物流配送路径优化算法的研究[J]. 现代计算机，2017（14）：14-20.

[11] 薛德琴，张永强. 基于线性规划的公路运输成本优化研究[J]. 物流工程与管理，2020，42（12）：121-123.

[12] 张骏，巴文婷. 大数据背景下区域木材物流配送中心选址[J]. 物流技术，2020，39（2）：84-87.

[13] 巴文婷，闫星臣. 民营快递企业区域物流网络优化分析——以A企业为例[J]. 物流工程与管理，2020，42（6）：37-39.

[14] 邱荣祖，钟聪儿，修晓虎. 基于Gis和禁忌搜索集成技术的农产品物流配送路径优化[J]. 数学的实践与认识， 2011，41（10）：145-152.

[15] 谷炜，张群，卫李蓉. 基于Gis的物流配送中心末端大规模车辆路径优化问题研究[J]. 中国管理科学，2013（S1）：379-389.

[16] 潘国强，胡俊逸，洪敏. 考虑Gis的物流配送区域划分与路径规划算法[J]. 大连海事大学学报，2015，41（1）：83-90.