基于OR-Tools 的某市高校蔬菜配送路径优化

陈卿诗 CHEN Qing-shi；邱文倩 QIU Wen-qian；莫立佳 MO Li-jia

（湖南科技大学，湘潭 411201）

0 引言

在互联网的带动下，农产品冷链物流需求越来越大，而成本一直是制约冷链牧流发展的关键因素，如何有效降低冷链物流成本成为国家、企业和消费者共同关注的热点话题。与此同时，冷链物流市场的扩大以及消费者对服务品质的要求提升促使企业不得不提升自身服务质量，食品安全和卫生问题越来越受到关注，提高满意度来增加顾客黏性，在竞争激烈的场中占据一席之地[1]。作为食品安全的重要组成部分，蔬菜的新鲜度和卫生质量是人们关注的重点。而蔬菜的运输路线直接影响到其新鲜度和卫生质量，因此，研究食堂蔬菜运输路线具有重要的现实意义和社会价值。通过深入探究当前蔬菜运输路线的现状和问题，可以帮助我们更好地了解食堂的需求和挑战，为制定相应的政策和措施提供科学依据和参考。同时，也有助于提高人们的食品安全和卫生意识，促进社会的可持续发展。

蔬菜等生鲜的配送优化属于典型的车辆路径规划问题，已有学者对该应用场景展开了论述。张洪瑶等[2]基于灰色神经网络预测生鲜物流需求；冉昊杰等[3]将遗传算法与模拟退火算法融合，实现选址过程的整体优化；赵佳豪等[4]基于大数据技术应用分析，提出优化供应链的对策。上述学者多考虑生鲜配送的需求以及选址等的优化对策。

鉴于此，本文针对社区某市22 所高校蔬菜生鲜配送的实际场景，考虑多车辆类别以及不同容量的约束情况，提出运用基于OR-Tools 的路径优化方法；其次运用matplotlib 绘制路径图像；最后导出各车辆移动路线、移动距离以及载重量，直观反映优化效果。

1 问题及模型

1.1 问题描述

物流中心每日需要为学校提供蔬菜的配送服务，每个学校的蔬菜配送量一定。物流中心拥有一定数量不同规格的配送车，各个学校均设有一个配送接收点，各校之间通有大道。一个物流中心向多个学校配送蔬菜，配送车辆统一从物流中心出发按照一定的配送顺序，配送到需求点，最后返回到物流中心。应用点为基于需求量约束的调度配送车辆、安排配送线路与次序，使配送总成本最小。

基于现实情况，为简化问题处理但不失一般性，假设如下：

①配送中心具有一定数量不同型号的配送车。

②配送车需要从物流中心出发，当完成所有配送任务后，需要返回配送中心。忽略特殊情况下配送量激增所导致的往返配送中心装货。

③各客户节点（买方）只能接受1 辆配送车为其进行配送，且需求量不能超过配送车的最大载荷。

图1 蔬菜物流配送流程

④各客户节点的地理坐标、产品需求量等均已知。

⑤学校快递点和物流中心的个数均唯一。

⑥物流中心至学校快递点、学校快递点之间路径唯一，且距离已知。

⑦物流中心的成本只考虑运输成本，装卸成本忽略不计。

⑧每辆车的行驶距离不超过预定的该车的最大行驶距离。

1.2 参数及变量定义

设蔬菜配送配送中心车场有m 辆车，每辆配送车的最大载重量Q，需要对n 个客户（节点）进行运输配送，每辆车从中心车场出发给若干个客户送货，最终回到中心车场，客户点i 的货物需求量是di（i=1，2，…，n），且di＜Q。记配送中心编号为0，各客户编号为i（i=1，2，…，n），ci，j表示客户i 到客户j 的距离。求满足车辆数最小，车辆行驶总路程最短的运送方案。

模型涉及的参数与变量作以下界定：

n：客户点的数量（不包括起始点）；

m：车辆的总数量；

Q：每辆车的容量限制；

di：客户点的需求量；

ci，j：客户点i 到客户点j 的距离；

1.3 模型构建

基于上述问题与假设，以某物流中心的蔬菜配送服务为应用对象，构建规划模型如下：

其中，式（1）表示目标函数为最小化总行驶距离，式（2）确保每个客户点必须被访问且仅被访问一次，式（3）和式（4）确保每辆车的路径必须从起始点开始，并在终点结束，式（5）为车辆容量限制，式（6）为0～1 决策变量约束。

2 求解方法

2.1 求解思路

上述模型是一个NP-hard 问题，且随着问题规模的增大，传统算法很难快速、智能地去求解这个问题。不少学者基于退火算法进行处理。区别于此，本研究从实际应用角度出发，首先对其某市22 所高校高校进行了实地考察和数据收集。其次，查阅相关文献，了解国内外在VRP 方面的研究进展、方法和技术，总结本文研究某市高校蔬菜车辆配送中存在的问题。随后，建立一个实际的物流网络模型并对在OR-Tools 工具包的基础上编码进行该模型求解。通过对比不同参数设置下的优化的求解结果，分析其优缺点，结合VRP 问题的解决方案，为社区某市蔬菜配送运输提供一种有效的路径优化方案。原因有如下几点，OR-Tools 提供了使用多种算法和工具，且能高效地求解计算出最优车辆行驶路径结果。同时，支持多种编程语言,本文使用Python 编程语言构建模型框架能自由修改源代码，符合本文模型的实际问题求解需要。

2.2 代码框架

求解的代码框架如图2 所示。其中，OR-Tools 的核心原理是建立数学模型和求解器，且主要用于解决车辆路径、流程、整数和线性规划以及约束等问题，可用ORTools 中的RoutingModel 分析求解，以此寻找方案的相对最优求解结果。在此基础上，代码基于Python3.8 编写，首先引入OR-Tools 以及matplotlib 工具包，其次，记录和设置本文模型中各参数，如物流中心与各高校的坐标位置、车辆数量、物流中心为出发点与起始点，以矩阵和数组表示。随后，利用OR-Tools 的函数求解，求解思路是使用路由模型以及距离回调、确定采用距离矩阵，进而通过计算重量和每辆车的载重以及对应距离长度计算获取路线来寻找每辆车的最佳路径。最后，绘制图像将最优车辆行驶路径结果可视化。

图2 求解思路

3 问题分析

3.1 配送现状

目前，物流中心配送车辆有12 台，其中承载量为4 吨的货车有4 台，配送路况较差的线路，承载量为6 吨的货车有4 台，承载量为8 吨的货车有4 台，配送道路路况较好的线路，订单量激增时会租借其他车队的车。现在的配送是由物流中心分别向各个学校之间的单独配送，每次只配送一个学校的蔬菜，配送完成后需重新返回物流中心进行下一个学校蔬菜的配送。物流中心以及高校分布图如图3 所示。

图3 高校坐标相对位置

3.2 配送现状存在的问题

配送货运车辆运力不足且性能与承载量无法满足目前的需求，相比其他城市，物流中心的配送路线的问题也有很多不合理的地方。

3.2.1 配送规划不合理

现在的配送是由物流中心分别向各个学校之间的单独配送，每次只配送一个学校的蔬菜，配送完成后需重新返回物流中心进行下一个学校蔬菜的配送，因而需要在物流中心和各学校网点之间来回，配送路线出现重复。从而导致物流中心的配送次数增多、配送效率降低，并且运输成本增加，造成不必要的运输资源浪费。

3.2.2 配送时间不合理

配送时间的错乱，现在配送的顺序是按大学、中学来进行区分配送的，单辆配送车负责的配送区域跨度较大，配送时间过长。因而常常导致无法按时送达货物，或使各网点延迟收货时间，对一些急需蔬菜的客户群体造成收货延迟，顾客满意度下降，损失大部分客户。

3.2.3 配送路线不合理

配送线路单一，目前物流中心采用的配送线路是由多年前道路路况状况及货物运输量来设计的，经过的重复路径过多。对于如今的发展，此配送线路已无法满足目前的需求，同时也降低了物流中心对某市高效蔬菜配送的作业效率。

3.3 路径改进

每辆车需要在不同的地点提取货物并在其他地点交付货物，要求是为车辆分配路线以提取和交付所有货物，同时最小化所有访问路线的总长度。考虑使用OR-Tools的RoutingModel 等模块。根据上述背景数据，通过Python实现上述实际问题的蔬菜配送优化求解。实验硬件显卡为NVIDIA GeForce RTX 2060 内存为16GB。

算法运行结果如表1 与图4 所示。其中，编号1 至11为大学A 至K，编号12 至22 为某市第一中学至第某市第十一中学。其中车辆总装载量、车辆路线以及路程距离均得到了体现。

表1 优化结果数据表

图4 车辆运输路线图

配送需求量改进，车辆载重量最大效益化，改进前每次只配送一个学校的蔬菜就回到物流中心。由表1 可见总路程为269531m，运输车辆从原有的12 台降低至10 台，减少了无效车辆2 辆；总路径降低至27 公里左右，配送效率提高了5%，打破了原有的车辆规划与配送路线。表明，本文方法在带容量多车辆类型的路径优化中优势显著，可收获效果理想。每个学校的蔬菜需求量有大有小，蔬菜需求量可能不满足车辆装载量的最大化，本文通过改进后的车辆路径优化，可使车辆完成一个学校配送后还有盈余量送往另一个配送点，减少了无效车辆的使用，节约配送成本的同时还能在客户预期的时间内完成配送，提高用户满意程度，优化后的结果具有实际践行意义。

4 结论与建议

本文基于python3.8，利用OR-Tools 与matplotlib，针对某市各高校的蔬菜生鲜配送为代表的车辆容量约束的VRP 问题，应用本文模型与求解框架进行研究并得到了最优配送线路，探讨了求解时间、门店空间分布以及装载约束条件变化对优化结果的影响，验证了本研究的实践应用价值。与改进前相比，改进后，总车辆数目与平均路程均得到了改善。但研究仍存在以下不足：

①没有考虑带时间窗的VRP 问题。在实际情况中，各高校的食堂会提前制作好菜肴以供师生享用，因此物流中心运输蔬菜生鲜至各高校时应当在其食堂预定时间内送达，否则配送不能满足客户需求，实际意义降低。因此，将来应该考虑带时间窗的VRP 问题。

②没有考虑多配送中心运输问题。在实际情况中，配送中心与各高校协调后应会调度多个配送中心的车辆运输。本文仅考虑了一个配送中心的车辆运输问题，如若考虑多配送中心，客户将会覆盖到湘潭市更多的高校，实际模型才更准确。因此，将来应考虑多配送中心的车辆运输路径的优化问题。