蚁群优化算法下农村生鲜配送车辆路径对比研究

韩荣腾

摘 要：近几年，美团优选、多多买菜等生鲜电商涌入农村市场，开始针对性地解决农村生鲜物流配送的“最后一公里”的难题。文章通过引入生鲜电商的“社区团购”配送模式，综合考虑农村用户的商品需求量、生鲜商品送达用户时的鲜活度、商品履约率、容量受限开放式路径规划配送车辆等因素，以总配送成本最小为目标构建开放式带时间窗容量受限车辆路径优化模型，利用蚁群优化算法对该模式求解。通过算法求解的结果表明：在农村生鲜产品配送中，开放式容量受限车辆路径规划，能有效地降低农村生鲜物流配送的总成本，缩短车辆行驶距离，提高商品履约率。

关键词：农村生鲜配送；开放式车辆路径规划；容量受限；带时间窗车辆路径规划

中图分类号：F259.23   文献标识码：A 文章编号：1005-6432（2023）10-0189-05

DOI：10.13939/j.cnki.zgsc.2023.10.189

1 引言

生鲜行业是我国民生的刚需行业。随着疫情的出现，生鲜电商大量涌现，生鲜电商市场迅速成长，已经在生鲜行业占据一席之地。根据中国电商委的数据，农村生鲜网购消费人群更加关注生鲜产品的价格和质量，对生鲜产品的时效性关注度不高。而社区团购模式保证了消费者的低价高质，物流配送为T+1天，商品为次日达，可以满足农村消费者的需求，解决了生鲜产品农村配送“最后一公里”的难题。农村生鲜电商平台的商品价格竞争较为激烈，生鲜电商要保证盈利与占據农村市场份额，就要降低物流配送成本，提高商品履约率。物流配送成本的降低，商品履约率的提高，将推动生鲜电商的核心竞争力的提高，更多的让利于农村消费者，促进农村生鲜电商的发展。

降低农村生鲜物流成本的关键是如何规划车辆路径的问题，通过构建开放式车辆路径规划，探索规划车辆路径的解决方案，提高商品履约率。农村生鲜产品的物流配送多使用普通车辆配送，并不涉及冷链车辆配送。王邦兆［1］针对生鲜配送中订单较少以及消费者较为分散，提出了结合改进遗传算法的社区搜索算法，对以成本为导向的多中心共同配送进行优化，但是要求分拣率的提高。王可山［2］认为降低生鲜电商的配送成本应该对配送成本、包装成本等进行优化，并没有针对配送的路径成本进行分析。李昌兵［3］综合物联网技术优势和生鲜农产品的特点，使用RFID技术降低分拣和配送成本。付朝晖［4］引入了时变路网条件，构建了生鲜配送的开放式路径规划车辆路径问题优化模型，以期降低生鲜电商的总配送成本。范厚明［5］提出车辆在完成配送任务后可继续补货进行配送或自行结束配送任务的一种半开放式配送模式。余海燕［6］提出结合生鲜产品订单的动态性、硬时间窗等因素，设计滚动时域延迟配送算法模式，并对其模型参数进行敏感性分析。

现存的文献对深入研究末端生鲜物流配送提供了大量的参考。但由于已有的文献主要研究城市生鲜物流配送问题，多针对封闭式车辆路径规划问题，对开放式带时间窗容量受限车辆路径配送问题以及农村生鲜物流配送涉及较少。文章针对农村消费者网购关注度以及社区团购时效性等特点，考虑到“T+1”的配送模式、开放式车辆路径规划、车辆容量受限以及商品履约率等因素，以配送成本最低为优化目标，建立开放式车辆路径规划模型，并设计蚁群优化算法求解该模型。

2 问题建模

2.1 问题描述

社区团购主要是以多多买菜、美团优选等生鲜电商企业为主的一种生鲜电商模式。该模式下的农村生鲜物流配送路径主要涉及从配送中心到团长门店和第三方车辆配送或自营车辆配送。大多数生鲜电商为了降低成本，多使用第三方车辆进行配送，司机可以进一步利用车辆的价值，因此第三方车辆在完成配送任务后，不必返回配送中心。社区团购下的农村生鲜物流配送，有多个“团长”门店需要配送，各门店的地理位置已知道，配送容量不超过车辆容量，每个门店只能被一辆车服务一次。为了提高客户满意度，文章将针对商品的新鲜度以及客户需求设置bj点履约率。假设：①每辆配送车辆从站点出发，配送任务完成后，不必要返回站点。②车辆会产生一定的固定成本。③车辆可提前到达门店位置，但需等待该门店最早开始服务时间进行配送，存在一定的车辆等待时间与卸货时间。通过上述条件构建开放式（带时间窗容量受限）车辆路径规划模式。

2.2 模型构建

2.2.1 已知参数

S1 表示开放式路径规划车辆总配送距离；dij 表示客户节点i到达客户节点j之间的距离；Q 表示车辆的最大载装量；Wo 表示开放式路径规划车辆司机的固定工资；K表示车辆的集合；FCij 表示每辆车k单位距离的燃油补贴，其中FCij≤Fk1;N 表示客户的集合；qi 表示一个客户的需求量；R 表示一组客户的路径（c1， c2， …， cn）； r表示一组客户的路径规划（r1， r2， …， rk）； CBest 表示最优的成本； Li 表示在节点i还没拜访的客户；Rej表示配送车辆在客户节点j所增加的一定奖励成本；Puj表示配送车辆在客户节点j所增加的一定惩罚成本；tij表示配送车辆从客户i到达客户节点j的时间；aj表示配送车辆最早到达客户节点j的时间；bj表示配送车辆最晚到达客户节点j的时间；ej表示配送车辆实际到达客户节点j的时间。

决策变量：xijk 表示车辆k是否从节点i行驶到节点j，如果是，值为1，否则为0；vk表示车辆k是否被启用，如果是，值为1，否则为0；yik表示车辆k是否完成客户节点i的任务，如果是，值为1，否则为0。

2.2.2 模型约束条件

∑k∈K∑（i， j）∈Ndijxijk（1）

CBest=FCij∑k∈Kvk∑k∈K∑（i， j）∈Ndijxijk+Wo∑k∈Kvk+Rej∑k∈Kvk∑（i， j）∈Nxijk+Puj∑k∈Kvk∑（i， j）∈Nxijk（2）

s.t.

∑k∈K∑j∈Δ+（i）xijk=1， i∈N（3）

∑i∈N∑k∈Kxijk=1， j∈N（4）

∑i∈Nqi∑j∈Δ+（i）dijk≤Q， k∈K（5）

xk0j=vk， k∈K， j∈N（6）

∑j∈Nx0jk≤1， k∈K（7）

時间窗约束：（8）

xijk∈{0， 1}， k∈K，（i， j）∈N（9）

yik∈{0， 1}， k∈K，i∈N（10）

其中：目标函数（1）表示车辆行驶总距离最优。目标函数（2）为最优的开放式路径规划车辆配送成本。约束（3）限制每个客户只能被分配到一条路径上。约束（4）表示每个客户节点只能被访问一次。约束（5）表示每辆车在配送中心装配的货物不大于车辆自身的最大承载量。约束（6）表示当车辆被启用时，必须从配送中心出发。约束（7）表示每辆车只能启用一次。约束（8）将分为硬时间窗和软时间窗。客户节点j的时间窗范围为［aj， bj］， ［aj， bj］为客户点最早及最晚送达时间，对［aj， bj］时段车辆到达客户节点j将增加一定的奖励成本，对超过bj时段车辆到达客户节点j将增加一定的惩罚成本，对早于aj时间点到达的车辆，并不设奖惩，虽可能导致配送效率降低，但是仍可达到履约率。硬时间窗要求车辆必须在［aj， bj］完成配送任务，即aj≤tij≤bj，软时间窗允许车辆送达时间早于aj，晚于bj。在不超过bj时段车辆到达节点j，客户j的满意度为1，在超过bj时段车辆到达节点j，客户满意度为-1。其奖励成本为式（11），惩罚成本为式（12）。

Rej=1（aj≤tij≤bj）（11）

Puj=－1（bj≤tij）（12）

决策变量（9）表示当车辆k从节点i行驶到节点j时，xijk=1，否则为0；决策变量（10）表示车辆k完成i的任务时，yik=1，否则为0。

3 算法验证及分析

车辆路径规划是经典的组合优化问题，而开放式带时间窗容量受限车辆路径规划属于VRP的衍生问题，因此需要求解的模型同样具有NP-hard形式。蚁群算法是一种启发式智能算法，具有降低编码复杂性、提高效率的特点。

为检验文章采用的蚁群优化算法的有效性以及可行性，文章采用聊城市某多多买菜农村社区站点所提供的数据。其中，车辆行驶的距离为坐标点之间的距离。该多多买菜站点，主要配送社区为乡镇辖区内的农村门店。文章选取了其中25家多多买菜门店数据。涉及车辆的最大载重量为4500千克，车辆的行驶速度设为60千米/小时。每辆车的司机工资采用当地工资平均值为4500元/月，金杯汽车的百千米油耗为12升，当地92号汽油价格的平均值为6.5元/升，因此每辆车的百千米油料补贴为10元。送达时间即为签单时间，惩罚成本设为50元/每门店，奖励成本设为50元/每门店。

设配送中心以及25个门店分布在有向图G中，配送中心为（40，50），门店等待以及卸货时间设为90分钟/门店，25个门店其他数据如表1所示。

文章所设蚂蚁数量m=50，车辆最多使用数目kmax=25，最大迭代次数iter_max=100，其他参数设置如上文。利用Matlab工具，将蚁群优化算法进行运算，所得最小成本为15371.74元，最小距离均为187.174。

为防止存在误差，文章在计算机上运行10次所得最小配送总成本均为15371.74，最小配送总距离均为187.174，算法结果具有稳定性，其中运行101次时间平均为26.522679秒，运行时间较短，效率较高。车辆最优路径规划如图1所示，其搜索各代最小成本变化过程如图2所示。

如图2所示，文章所实验的结果具有可行性和有效性，所展示出的配送路径为：配送路线1为0→5→3→7→8→10→11→9→6→4→2→1，配送路线2为0→13→17→18→19→15→16→14→12，配送路线3为0→22→24→25→23→22→21。

文章为证明开放式车辆路径规划相比封闭式车辆路径规划更加节省成本，采用蚁群算法计算25个门店的封闭式车辆路径规划，所得最优路径规划如图3所示，其搜索各代最小成本变化过程如图4所示。其中封闭式最佳车辆配送路径与开放式最佳车辆配送路径相对比，多出了回到配送中心的路程，使得油料补贴成本有所增加，增加70元，但使用车辆一致，司机工资成本一致，奖惩成本一致。

4 结语

文章将传统的TSP问题加入开放式、带时间窗及容量受限等元素，并考虑配送司机的奖惩成本、对比封闭式车辆路径规划，以配送最小总距离与配送最佳成本为目标，从而构建蚁群优化算法，为现实生活中农村生鲜社区配送路径规划提供一个新思路。实验结果证明：①开放式车辆路径规划可以节省配送成本，缩小配送距离，节约车辆配送时间。在配送任务完成后，司机可以自由支配时间，提高了车辆使用的灵活性。②农村一直存在的配送“最后一公里”难题得以解决，为振兴农村物流提供了一定借鉴。③与封闭式车辆路径规划相对比，开放式车辆路径规划具有更好的优化效果，不易陷入局部最优。

参考文献：

［1］王邦兆，李慧.生鲜农产品同城配送复杂网络布局设计［J］.统计与决策，2019，35（12）：40-44.

［2］王可山，张丽彤，刘彦奇.生鲜电商配送成本影响因素及控制优化研究［J］.经济问题，2019（1）.

［3］李昌兵，汪尔晶，袁嘉彬.物联网环境下生鲜农产品物流配送路径优化研究［J］.商业研究，2017（4）：1-9.

［4］付朝晖，刘长石.生鲜电商配送的兼职时变车辆路径问题研究［J］.计算机工程与应用，2021，57（1）：271-278.

［5］范厚明，杨翔，李荡，等.基于生鲜品多中心联合配送的半兼职车辆路径问题［J］.计算机集成制造系统，2019，25（1）：256-266.

［6］余海燕，唐婉倩，吴腾宇.带硬时间窗的O2O生鲜外卖即时配送路径优化［J］.系统管理学报，2021，30（3）：584-591.