基于VRP技术的“弹性”送货模式探索与实践

欢迎大家来到IT世界,在知识的湖畔探索吧!

摘要：卷烟物流是烟草销售中不可或缺的重要组成部分，其中配送环节作为整个物流流程的关键环节，面临着诸如线路规划不合理、车次规划不科学等主要问题。本文以VRP（车辆路径问题）优化方法为基础，针对物流网络布局优化进行研究。通过聚类算法划分配送区域，并运用蚁群算法优化车辆路径，在综合考虑地形地貌、送货难度、送货模式、服务需求等多种因素的基础上，结合淡旺季的特点，提出了弹性送货“六步法”模式。该方法可以帮助烟草公司增加日均单车次配送量、日均配送户数、日均配送里程，并使得每年成本可降低48万元左右。

关键词：物流配送、VRP问题、聚类算法、弹性六步法

一、引言

1.Z烟草公司物流配送的现存问题

卷烟物流在烟草销售中扮演着重要角色，其中配送环节是实现高效物流的关键。在这个环节中，采用先进的技术和方法来优化配送路径和调度是提高效率、降低成本的重要手段。通过实地调研发现，受区域面积、地域特征等客观条件影响，Z烟草中转站物流配送效率较低，与此同时也存在线路布局缺乏弹性、车次规划不科学、岗位轮转不充分等问题。

（1）线路布局缺乏弹性

配送线路的固定性导致无法适应烟草物流的季节性波动。目前全省各地运行的配送线路一般全年固定不变，这种“公交站式”固定不变的配送线路，导致物流配送无法有效应对各月配送需求量的波动性，尤其是淡旺季交替带来的需求剧变。旺季时，卷烟配送量相比平常会成倍增加，每年元春旺季都需额外增加车辆来完成全部配送任务，而淡季时配送车辆普遍存在冗余。另外，近年来由于许可证办理条件的放宽，零售客户数量显著增加且地理位置分散，进一步增加了科学配送的难度。

（2）车辆装载率不均衡

县级公司通常的规划策略是，首先，确定几条固定的配送线路；然后，根据客户的地理位置、配送量、配送里程和配送户数将客户大致均衡地分配到各条线路上；接着，根据当日的配送量和配送户数，临时决定装载情况和车次。该规划策略的好处是线路固定、送货对象明确、管理较为方便。缺点是经常会导致二次出车的装载率较低，产生人力、油耗等浪费，难以满足成本效率均衡的要求。此外，这种规划很大程度上依靠调度经验，不能保证分配的科学性和合理性。

（3）岗位轮转不充分

由于岗位轮转不充分，以及固定的配送线路，导致一个配送组可能长期只服务于特定区域。这会导致配送人员对客户的熟悉程度较低，无法应对区域调动或线路重新规划时的风险。一旦线路出现变动，配送效率可能因不熟悉客户及其地理位置而降低。固定的配送线路、固定的人员组合以及满打满算的配比，无法合理安排员工调休，一旦有员工退休、休假等情况出现，正常的配送工作将会受到很大影响。

2.烟草车辆路径优化问题（VRP）综述

结合烟草物流的零售客户地理位置分布广泛、小批量高频率、季节性波动的特征，从区域划分和路径优化两个方面进行考虑，科学划分配送区域并选择最优的配送线路是降低烟草物流成本的关键。关于区域划分，国内外学者已经开展了大量的研究。为了共同解决分区、资源定位和分配问题，Regis-Hernández等[1]提出了一种迭代算法，利用分区和资源的定位与分配决策之间的相互作用来构建紧凑而平衡的区域，同时能够最短时间得到资源定位和分配的方案。为了解决在伊朗的城市固体废物管理问题，Darmian等[2]提出了一个多目标的位置分区优化模型，并采用最远候选法的多目标局部搜索启发式算法求解大中型数值实例，以及采用商业软件直接求解小型数值实例。谷炜等[3]在针对大规模车辆路径问题求解时，在考虑工作量均衡的条件下提出了一种改进的两阶段K-means聚类算法对配送区域进行划分，并通过实例验证了其有效性。于晓寒等[4]在对快递配送区域进行划分时提出了一种带约束的K-means聚类算法。

车辆路径问题自 1959 年被Dantzig等[5]首次提出后，引起了国内外学者广泛的关注和深入的研究。Bogue等[6]采用列生成算法和基于可变邻域搜索的启发式算法，得到了多时间窗口车辆路径问题最优解的上界和下界。Che等[7]研究了一种求解同时取货和送货车辆路径问题，其中客户需求是随机收集的，并将该问题建模为带追索权的两阶段随机规划问题，然后采用整数L型算法框架求解这类带追索权的两阶段随机规划问题。为研究任意两点之间存在多条通路的带有时间窗口与能力约束的变速车辆路径问题，孔珊等[8]建立了双目标的混合整数规划模型，并采用改进蚁群算法求解，仿真结果表明所提模型和改进算法有效。闫淼等[9]构建了配送总成本最低的不同车型新能源车在冷链物流配送中的路径优化模型，并提出了一种融合海洋掠食者算法与蚁群算法的算法进行求解，该算法能有效提高初期搜索能力和全局搜索能力。

综上所述，对于车辆路径优化方面的研究国内外都比较丰富。通过文献综述发现：在大规模的车辆配送路径优化问题中通过对配送区域进行合理的划分，再进一步对子区域进行路径优化有较好的优化结果。

3.弹性模式的六步策略

本文基于路径优化问题（VRP）以及K-means聚类算法与蚁群算法的相关研究，针对Z烟草公司物流配送中的现存问题，提出了弹性物流模式“六步法”。具体为：（1）划分送货区域；（2）基础线路测算；（3）弹性线路确定；（4）车次规划设计；（5）日级智能调度；（6）岗位轮转设计。本文提出的弹性模式“六步法”可以有效地解决Z烟草公司物流配送中的现存问题，具体步骤如图1所示。

欢迎大家来到IT世界,在知识的湖畔探索吧!

图1 弹性物流模式“六步法”

二、弹性模式下的烟草物流配送路径优化算法设计

1.问题描述与分析

Z烟草公司物流配送面临的主要问题之一是固定配送线路的局限性。为了解决这个问题并保证实际可操作性，本研究提出了一种区域划分并优化的策略：将整个服务区域划分为多个较小的子区域，并在这些子区域内优化配送路径。这种方法有助于应对服务区域广阔、地理位置分散的挑战。通过划分配送区域，优化的搜索范围缩小，从而大幅减少计算量，有效提高求解速度，并降低成本。

2.基于K-means 聚类算法的配送区域划分

K-均值聚类算法（k-means clustering algorithm）是Mac Queen提出的一种非监督实时聚类算法，基本思路是在最小化误差函数的基础上将数据划分为预定的类数K，其原理简单、便于处理大量数据[10]。本文基于K-Means方法来实现配送区域的动态划分。

Z烟草公司的客户数量较大，总配送点达7000余个。本文随机抽样100个客户作为实验数据。区域划分的具体步骤如下：

（1）样本的可行性分析。需要分析样本所在区域的客户点之间是否连通，防止交通阻碍导致的线路规划不当。

（2）数据处理。对实验数据的100个客户的地理位置进行统计，并统一使用百度地图坐标系进行处理，得到规范统一的坐标数据。

（3）划分配送区域。将数据导入Matlab软件中，设置配送区域个数为4个，选择初始聚类中心分别为编号15、40、65、90的客户点，终止条件设置为迭代10次。区域划分的结果如图2所示，其中红、蓝、紫、绿分别代表4个不同的划分区域，黑色“×”代表4个聚类中心。

3.基于蚁群算法的配送路线优化

（1）蚁群算法原理

蚁群算法的基本原理来源于自然界蚂蚁觅食的最短路径原理，蚂蚁在寻找食物源时，能在其走过的路径上释放一种蚂蚁特有的分泌物—信息素，使得一定范围内的其他蚂蚁能够察觉到并由此影响他们以后的行为。原理是一种正反馈机制。蚁群算法的两个关键过程包括状态转移过程和信息素更新过程。

（2）路径优化的实现步骤

图2 基于K-means聚类算法的区域划分图

本文基于随机抽样的100个客户数据，已经使用K-means聚类算法将配送区域划分为4个区域，对各个区域进行路径优化具体步骤如下：

①选取配送区域。本文选择图2右上角的蓝色配送区域进行优化，该区域共包含39个客户点。

②数据处理。对该区域的39个客户数据的地理位置统一使用百度地图坐标系进行处理，得到规范统一的坐标数据。

③路径优化。将数据导入Matlab软件中，初始化参数设置如下：蚂蚁数量为m=75，信息素重要程度因子为α=1，启发函数重要程度因子为β=5。不同节点之间的距离基于百度地图经纬度计算得出，最后可以将经纬度距离换算为实际距离。算法收敛轨迹如图3所示，在第35代算法收敛。图4为该区域的配送路径顺序图。

图3 算法收敛轨迹图

图4 配送路径顺序图

三、弹性模式下Z烟草公司物流配送优化措施及效果评估

要真正地做好弹性送货，必须充分发挥“互联网+物流”的平台优势，结合物流配送的核心业务指标，运用简便、实用的模型算法，来配置合理的基础线路。在确定基础线路之后，进一步实施弹性线路和车次规划，并通过科学的岗位轮转优化物流配送供应，以满足零售客户的服务需求，从而稳步提升送货绩效。本文通过理论研究与实例验证的结果，提出烟草物流弹性物流模式“六步法”的应用框架。

1.制定原则

（1）线路弹性原则。在优化算法帮助确定基础线路的基础上，遵循“以量按需定线路”的原则，根据季节性的配送需求变化动态调整线路数量，在旺季配送量多时增加配送线路，在淡季配送量少时减少配送线路，从而摒弃全年固定不变的线路规划，解决线路规划缺乏弹性的问题。

（2）车次弹性原则。主要是以“工作时长”和“车辆装载量”两个指标来确定发车数量，设计合理的运输方案。这样的规划方法使得车次成为确定配送对象的依据，而不是线路，有效解决二次出车效率低下的问题。

（3）人员弹性原则。遵循“多劳多得”的收入分配原则，坚持“循序渐进，平稳运行”的方针，结合省局物流岗位轮转的要求，通过定期的配送人员交替轮换，逐步提高配送人员对客户的熟悉度。

2.“六步法”弹性送货模式框架

弹性送货模式框架由年度规划、月级调整和日级调度三部分构成。年度规划主要是基于上一年度的配送量和年初的预排销量来确定基础线路。考虑到烟草生产和销售计划较为稳定（由国家烟草局规定），使用上一年的配送数据可以有效估计出下一年度的销售量。在基础路线确定后，再结合每个月份的投放计划来配置弹性线路，行程“基础线路±弹性线路”的整体规划，以灵活应对旺季和淡季的需求波动。在路线数确定后，再基于每日的实际订购进行日级的车辆调度。月级调整和日级调度的区别在于：月级调整是根据每月的投放量确定的运行线路，也就是配送线路的增减调整；日级调度主要是根据当日的订货量来调整，在配送线路之间根据装载情况进行客户的盈余互调。

（1）划分送货区域

送货区域划分是将整个送货区域划分为常规送货区与弹性送货区。常规送货区的客户由每条配送线路上需求较为稳定的送货对象组成，这部分客户即使在需求高峰期也能由原线路完成配送；弹性送货区由每条线路的盈余调节客户组成，通常选择在行驶时间短、客户分布比较密集的区域，弹性区域的大小可根据实际运行的需要进行调整。由于凭借经验划分送货区域容易导致线路覆盖区域重复的问题，可以利用简单的聚类算法（如文章第二部分第二小节所示）根据配送点的地理位置对送货区域进行划分，从而克服客户地理位置分散的问题。在区域划分时还应当尽可能考虑子区域的总需求量，防止线路工作量不均的问题。

（2）基础线路测算

经过送货区域划分后，可以利用基于蚁群算法的配送路线优化算法（如文章第二部分第三小节所示）对子区域内的客户配送顺序进行优化，防止“走远路、绕弯路”造成的资源浪费。同时，根据年配送总量和目标单车年配送量，可以计算出基本线路数量：基本线路数量=年配送总量/目标单车年配送量。其中，年配送总量可以根据往年的配送总量和预计的配送量增减幅度进行估算；目标单车年配送量可按车辆装载量和管理需要进行可行性分析后确定。通过科学的路径规划，能够在保证绝大多数月份正常运行的前提下进行线路精简，进一步降低物流配送成本。

（3）弹性线路确定

在确定基础线路之后，可以根据卷烟配送的淡、平、旺季适当增减配送线路。主要分为以下两个步骤：①计算基础线路，即理论上各月需配置的线路数量。主要考虑的参数为运行方式（一般为单车单次和单车双次）和车辆平均装载量上限，计算公式为：测算线路数量＝月配送总量/单车月配送量。②计算弹性线路，在测算线路数量确定后，再结合送货户数、送货里程、配送量、运行方式、车辆平均装载量、工作时长等因素进行分析，逐月分析确定各月实际需配备的线路数量。最终形成一个弹性线路的规划方案，即月配送线路＝基础线路±弹性线路的线路随量弹性变动的方案。如在元春旺季时，卷烟配送量激增，若仅运行基本线路会大大超过单线路的工作时长，这时就需启动线路随量变动方案，集合部分弹性送货区的客户组成新的配送线路，形成基础线路+弹性线路的运行方案。而在元春后的淡季，卷烟配送量减少时，可相应减少基础线路，形成基础线路-弹性线路的运行方案。

（4）车次规划设计

车次规划主要思路是在满足每天每车配送户数100户，配送里程100公里，作业时间6个小时以上的“116”劳动强度的基本要求下，提高车次规划的频率，变一天一规划为一天两规划。在规划前，利用每户平均配送时间的历史数据进行分析，以确定常规送货区和弹性送货区客户平均配送时长，然后在“工作时长和车辆装载量”两个条件下进行具体规划。

上午专门配送常规送货区，按既定的工作时长结合客户均配送时长，规划并执行全部路线单元的配送任务，确保每辆车在上午完成一个配送路线单元的所有送货任务。下午则配送弹性送货区，同样基于既定的工作时长和车辆装载量结合每户均配送时长来规划，确定实际需发车的数量。

在弹性线路启动时，需对弹性送货区进行重新规划，根据弹性线路的实际情况，进行车次与线路的重新规划。

（5）日级的智能调度

在做好线路规划和车次规划后，为弥补线路规划和车次规划的不足，在实际运行中需充分利用平台的终端送货调度功能，启动日级智能调度。主要包括三种方式分别应对不同的场景，实现协同送货：①散点式的日级弹性。适用于各线路的日配送量基本接近于车辆装载量的情形，通过各车次间的客户调度来减少出车次数；②组团式的日级弹性。适用于销售淡季，各车的日配送量远低于装载量的情形，通过相邻线路的组团协同，如三车并两车，四车并三车等方式来减少出车次数；③区块式的日级弹性。适用于各车的日配送量普遍高于装载量的情形，如9月、10月份的小旺季，则各线路选择同一区域剔出部分客户，组合后进行二次配送来减少出车次数。

（6）岗位轮转设计

企业可以结合省局物流岗位轮转要求，通过设计合理的轮转方案，提高配送两员的客户熟悉程度，主要思路是采用“相邻配对、以熟带生，交替轮换”方式，定期进行作业片区的更换。

3.弹性模式效果评估

本文提出的弹性送货“六步法”模式框架，其特点在于实现了线路随量的弹性变动和按车次规划的配送对象。这一模式有效解决了以下关键问题：线路弹性变动主要针对配送线路数量与配送量不匹配的问题，而配送对象按车次规划则解决了低效出车的问题。此外，通过设置弹性送货区，本模式还解决了线路间协同配送的难题。通过“六步法”弹性模式的实施也得到了两方面的成效，如表1所示。

表1 弹性送货“六步法”实施前后配送效率对比

一是通过提高车辆装载率进一步来提高配送效率。如表1所示，与模式运行前（2019年）相比，模式实施后（2020年1～5月）日均单车次配送量增加了2.85箱，增长18.12%；日均配送户数增加13户，增长14.82%；日均配送里程增加6km，增长7.27%。

二是节省了物流运营成本提升了企业管理效益。实施弹性送货后在物流运营成本方面实现了大幅节约，如表2所示。

表2 弹性送货“六步法”实施前后企业效益对比

弹性送货实施后，基本送货线路减少一条；减少了两名配送一线的工作人员，减少工资支出40余万元；燃油费费用支出减少1.9万元；配送车辆减少一辆，减少车辆维护费及折旧费6万元，总计每年可降本48万元左右。

四、结论

本文通过对路径优化算法的理论研究和关于Z烟草公司的实例研究，以“降本增效”为目标，基于K-means算法和VRP算法，提出了烟草物流弹性送货“六步法”。该方法的核心优势可概括为三个关键词：弹性、潜力和平稳。弹性体现在送货“六步法”为其他单位提供了一套完整的思路和方法，可根据各自情况调整参数而运用；潜力在于为未来物流网络的进一步优化留有充分空间，无论是线路的再优化还是车次的再设计，均可通过调整弹性送货区域的规模来实现；平稳则体现在其循序渐进、平稳运行的策略，提高了员工的接受度和满意度。本文所提的物流弹性送货“六步法”已帮助企业实现“降本增效”的目标。

本研究受到中国烟草总公司重点研发项目（3）的支持

参考文献:

[1]Regis-Hernández, F., Lanzarone, E., Bélanger, V., Ruiz, A. Solving jointly districting and resource location and allocation problems: An application to the design of Emergency Medical Services[J].Computers&Industrial Engineering,2023,179, .

[2]Darmian, S.M., Moazzeni, S., Hvattum, L.M. Multi-objective sustainable location-districting for the collection of municipal solid waste: Two case studies[J].

[3]谷炜,张群,胡睿.基于改进K-means聚类的物流配送区域划分方法研究[J].中国管理信息化, 2010, 13(24):60-63.

[4]于晓寒,王东.基于带约束K-means聚类的城市快递配送区域划分[J].哈尔滨商业大学学报

(自然科学版), 2016,32(05):631-634+640.

[5]Dantzig,G.,Ramser,J.The truck dispatching problem[J].Management Science,1959,13,80-91.

[6]Bogue, E.T., Ferreira, H.S., Noronha, T.F., Prins, C. A column generation and a post optimizationVNS heuristic for the vehicle routing problem with multiple time windows[J]. Optimization Letters, 2022,16(1),79–95.

[7]Che, Y., Zhang, Z. An Integer L-shaped algorithm for vehicle routing problem with simultaneous delivery and stochastic pickup[J]. Computers&Operations Research,2023,154,.

[8]孔珊,仲昭林,张纪会.多路径选择变速双目标物流配送路径规划[J].复杂系统与复杂性科学,2022,001:019.

[9]闫淼,初良勇.不同车型新能源车在城市冷链物流配送中的路径优化[J].上海海事大学学报,2022,43(4):9.

[10]罗可,蔡碧野,吴一帆,等.数据挖掘中聚类的研究[J].计算机工程与应用,2003(20):182-184+218.