遗传算法在农村电商物流末端配送中的应用研究

Research on the Application of Genetic Algorithm in the Terminal Distribution of Rural E-Commerce Logistics

摘要: 随着乡村振兴战略的深入推进，农村电商领域规模逐年递增，然而末端物流配送的“最后一公里”难题，仍是阻碍农村电商发展的主要障碍。农村地区农户居住分散、道路基础设施薄弱、配送需求碎片化等特点，导致传统路径规划方法难以兼顾成本与效率。本研究针对农村电商物流末端“配送点–农户”环节设计车辆载货限制的路径规划模型，设计契合农村实际的遗传算法，采用实例仿真检验算法性能，对比分析得出，遗传算法在贪心解基础上能迅速找出更合理的配送路径，减少配送总路程，优化农村电商终端配送效率，为农村物流终端配送提供技术方法。

Abstract: With the in-depth advancement of the rural revitalization strategy, the scale of the rural e-commerce sector has been increasing year by year. However, the “last mile” dilemma in terminal logistics distribution remains a major obstacle hindering the development of rural e-commerce. The characteristics of rural areas, such as scattered residential distribution of farmers, weak road infrastructure, and fragmented distribution demands, make it difficult for traditional route planning methods to balance cost and efficiency. This study designs a route planning model with vehicle load constraints for the “distribution center-farmer” link in the terminal logistics of rural e-commerce, and develops a genetic algorithm that conforms to rural realities. Through example simulations to test the algorithm’s performance and comparative analysis, it is concluded that the genetic algorithm, based on the greedy solution, can quickly identify more reasonable distribution routes, reduce the total distribution distance, optimize the efficiency of rural e-commerce terminal distribution, and provide technical approaches for rural logistics terminal distribution.

1. 引言

近年来，国家大力支持农村电商的发展，陆续出台了很多政策，在《“十四五”电子商务发展规划》中明确提出“完善农村电商末端服务体系，打通农产品上行和工业品下行双向通道”。商务部数据显示，2024年农村网络零售额达2.56万亿，农产品网络零售额同比增加15.8%，这表明通过电商赋能，农村经济正实现发展模式的创新突破。然而，农村物流末端配送环节始终存在“成本高、效率低、覆盖难”的问题，一方面，农村地区农户居住分散，部分偏远村庄道路等级低、导航信号弱，导致配送半径大、空驶率高[1]；另一方面，农村的配送需求呈现出小批量、多频次、碎片化特点，单辆车需服务多个分散农户，传统按距离排序的路径规划方法容易导致车辆超载或绕路，从而增加配送成本[2]。据中国物流与采购联合会数据，农村电商物流末端配送成本占总物流成本的35%以上，远高于城市地区20%的平均水平，路径规划不合理是导致成本居高不下的核心原因之一。

研究人员开始聚焦于乡村物流体系中的路径优化难题。靳艺文指出农村地域物流基础设施薄弱等问题成为限制农村电商发展的因素，大数据依托其强大的数据挖掘与分析能力，为优化农村电商物流配送路径给予技术支持[3]。熊胜运用建模方法对物流配送优化问题进行了系统分析，论证了物流效率优化及成本管控的可行性[4]，许菱针对农村地区无人机物流配送展开研究，以降低配送成本为核心目标，开发混合整数规划模型，采用改进K-means和遗传算法的混合方法求解，实证分析了模型与算法的有效性[5]。张丽琼设计改进启发式测算B2C电商物流库存路径优化模型，采用自适应调整的方式完成路径优化处理[6]。车辆路径问题是一个典型的组合优化问题，此问题的主要解决算法有模拟退火算法、遗传算法、禁忌搜索算法、蚁群算法等[7]，总的来说算法在路径优化研究中应用广泛，算法作为技术赋能的核心载体，体现技术与实践的深度融合。

现有的路径优化研究大多聚焦于城市快递、城市配送场景，针对农村分散式农户配送的研究较少，且缺乏对农村道路特性、需求碎片化等场景的适配性设计。另外对于路径优化问题，当前多数研究以单一算法为主要求解工具，未能充分结合不同算法的优势形成混合优化框架，难以兼顾解的质量与寻优效率。本文将遗传算法与贪心算法引入农村电商末端配送路径优化，融合两个算法优点，构建适配农村场景的模型与算法，丰富了农村物流优化的理论体系。在农村电商物流企业的末端配送管理中，通过路径优化减少配送车辆行驶距离，从而减低燃油成本，另外通过合理规划可以减少车辆空驶率，这可促进农村电商的稳定发展，具备现实层面的应用意义。

2. 模型构建

2.1. 模型假设与符号定义

为了简化研究问题，我们结合农村场景特点提出以下假设：采用单配送点配置，配送车辆皆从配送中心开出，配送结束后返回起始点；每个农户的配送需求已知且固定，不考虑临时加单或取消订单；配送车辆型号统一，容量与最大行驶里程固定，无故障或交通拥堵等突发情况；忽略车辆装卸货时间，仅以行驶距离作为成本衡量指标(农村场景中行驶距离与时间、燃油成本呈正相关)。符号定义如表1所示。

Table 1. Definition of symbols

表1. 符号定义

符号	符号说明
N	$N=\left\{1,2,\cdots ,n\right\}$ ，n为农户数量；
V	节点集合，$V=\left\{0\right\}\cup N$ ；
$q_i$	农户i的配送需求(单位：件)；
Q	单辆车的最大容量；
$d_{ij}$	节点i到j的最短行驶距离(km)，$d_{00}=0$
$x_{ijk}$	0-1变量，若车辆从节点i行驶到节点j，则$x_{ijk}=1$ ，否则$x_{ijk}=0$ ；
$y_{ik}$	0-1变量，若农户i由车辆k服务，则$y_{ik}=1$ ，否则$y_{ik}=0$ ；
K	配送车辆总数

2.2. 目标函数与约束条件

车辆总行驶距离直接决定燃油成本与配送时间，最小化该指标可同时实现降成本与提效率的双重目标，构建的模型如下：

$\min Z={\displaystyle {\sum }_{k=1}^K{\displaystyle {\sum }_{i=0}^n{\displaystyle {\sum }_{j=0}^n{d}_{ij}{x}_{ijk}}}}$ (1)

${\displaystyle {\sum }_{k=1}^K{y}_{ik}}=1$ ，$i=1,2,\cdots ,n$ ； (2)

${\displaystyle {\sum }_{i=1}^n{q}_i{y}_{ik}}\le Q$ ，$k=1,2,\cdots ,K$ ； (3)

${\displaystyle {\sum }_{i=0}^n{x}_{i0k}}=1$ ，$k=1,2,\cdots ,K$ ； (4)

${\displaystyle {\sum }_{j=0}^n{x}_{0jk}}=1$ ，$k=1,2,\cdots ,K$ ； (5)

${\displaystyle {\sum }_{i=0}^n{x}_{ijk}}={\displaystyle {\sum }_{j=0}^n{x}_{ijk}}=y_{ik}$ ，$i=1,2,\cdots ,n$ ；$k=1,2,\cdots ,K$ ； (6)

$x_{ijk}\in \left\{0,1\right\}$ ，$y_{ik}\in \left\{0,1\right\}$ ，$i=0,1,\cdots ,n$ ；$j=0,1,\cdots ,n$ ；$k=1,2,\cdots ,K$ ； (7)

其中，(1)是需要优化的目标函数，表示最小化所有配送车辆的总行驶距离；约束条件(2)表示每个农户只能由一辆车配送，避免重复配送或漏配的情况；条件(3)表示每辆车服务的农户总需求量不能超过该车辆的最大容量；条件(4)和(5)表示每辆车从配送点出发，最终返回配送点且路径无断点；约束条件(6)表示若车辆k到达节点i，则必须从节点i出发，保证车辆路径的连续性；条件(7)定义$x_{ijk}$ 和$y_{ik}$ 的取值范围。

3. 算法设计

遗传算法(GA)是一种基于自然选择和遗传学原理的启发式优化算法，它模拟生物进化“选择–交叉–变异”过程，通过种群迭代在解空间中搜索最优解。遗传算法的主要逻辑为：初始化一组随机解，通过计算每个解的适应度，即目标函数值，选择适应度优的解作为父代，再通过交叉、变异生成子代，重复迭代直到满足终止条件。另一种直观且高效的近似求解方法是贪心算法，其核心思想是每次都做在当前看起来最优的选择，即优先访问距离最近的未配送农户，直到车辆满载或没有可以到达的农户，再开启新车辆，贪心算法容易陷入局部最优解。与贪心算法相比，遗传算法具有全局搜索能力强、能处理多约束问题的优势，更适配农村分散式配送的路径优化需求。本文综合两种算法，结合两者优点，用贪心算法生成的初始解作为遗传算法的优质种子，再通过交叉、变异等操作，在贪心解的基础上寻找更优解，借助遗传算法跳出贪心算法的局部最优解，从而找到相对较优的近似解，同时也能加速算法收敛。

我们采用“整数编码 + 分隔符”的混合编码方式，将车辆分配与农户服务顺序整合为一个染色体，即目标函数的一个解。例如，若有编号1~10的农户，在车辆容量约束下需要3辆车服务，则染色体可表示为：[0, 3, 7, 0, 1, 5, 9, 0, 2, 4, 6, 8, 10, 0]。在这个染色体中，“0”作为分隔符，分隔不同车辆的路径，该染色体所表示的含义为：车辆1路径为0→3→7→0；车辆2路径是0→1→5→9→0；车辆3路径使0→2→4→6→8→10→0。用“0”作为分隔符，既可以表示车辆从起点出发，完成配送或达到某个约束条件之后又回到起点，又可以直接看出每辆车的具体路线。

本文设计的遗传算法具体步骤如下：

(1) 种群初始化。将贪心算法生成的一个近似解作为遗传算法初始种群中的一个染色体，通过对贪心解的轻微变动，如交换两个农户的位置，生成多个相似但有差异的个体，避免初始种群质量过低；其余染色体由Python随机生成农户服务顺序，即1 − n的随机排序列，并根据车辆容量Q，计算至少需要的小车辆数$K_{\min }=\lceil {\displaystyle {\sum }_{i=1}^n{q}_i/Q}\rceil$ ，在农户顺序中随机插入$K_{\min }-1$ 个“0”作为分隔符；最后在染色体首尾各添加一个“0”，形成完整初始解。重复上述步骤，生成规模为$N_{pop}$ 的初始种群。

(2) 适应度函数。适应度函数需与目标函数(所有车辆总行驶距离)呈负相关，即总行驶距离越短，适应度值越高。定义适应度函数为：$F=\frac{1}{Z+\epsilon }$ ，其中，Z为染色体对应的总行驶距离，取$\epsilon ={10}^{-6}$ 避免Z = 0时适度函数无意义。

(3) 选择算子。采用“轮盘赌选择 + 精英保留”的策略，既保证种群多样性，又避免优秀解被淘汰，计算种群中每个染色体的适应度值$F_i$ ，并计算累计适应度${\displaystyle \sum F_i}$ ；生成$\left[0,{\displaystyle \sum F_i}\right]$ 的随机数，选择累计适应度首次超过该随机数的染色体作为父代；保留每代种群中适应度前10%的染色体，即精英个体，直接进入下一代，无需参与交叉、变异。

(4) 交叉算子。传统交叉算子通过随机选择交叉点交换父代序列片段，容易导致子代出现农户重复或农户遗漏，需额外修复步骤才能保证序列有效性，增加计算成本。而有序交叉(OX)通过保留核心片段并填充剩余节点的逻辑，适配路径优化的序列完整性要求。为了避免交叉后出现重复或遗漏农户，我们采用有序交叉的方式，随机选择两个交叉点，不包含首尾的“0”，复制父代染色体$P_1$ 、$P_2$ 中间片段，交换两个交叉点之间的基因片段，用另一父代的剩余基因按顺序填充空白，生成子代$C_1$ 、$C_2$ ，确保每个农户仅出现一次。如图1所示。

(5) 变异算子。为避免算法陷入局部最优，对每个染色体以变异概率$P_m$ 触发变异，随机选择染色体中两个非“0”的基因(农户编号)，交换两个基因的位置，生成新的染色体，如图2所示，校验变异后染色体的车辆容量约束，若存在超载，调整分隔符“0”的位置，确保每辆车总需求量 ≤ Q。变异算子的核心作用是打破局部最优，探索新的解空间，但需避免因变异幅度过大导致优质解退化。而交换变异通过随机交换两个农户位置的轻微变异，实现小幅度探索且能高概率保留优质结构。

Figure 1. Ordered crossover

图1. 有序交叉

Figure 2. Mutation operation

图2. 变异操作

(6) 算法终止。设定终止条件，迭代次数达到预设最大值$G_{\max }$ ，即算法收敛。

4. 实例仿真与结果分析

农村农户分布在乡镇配送中心的周围，且村与村之间相对分散，根据这个特点，我们以配送中心为坐标原点(0, 0)，利用Python随机生成分布在配送中心周围且相对分散的15个农户(编号1~15)作为研究对象，且假设农户配送需求$q_i$ 相对固定，15个农户平面直角坐标和配送需求$q_i$ 如表2所示。根据农村道路狭窄的特点，配送车辆一般选用小型面包车，最大容量Q = 15件，每百公里燃油成本约60元；根据农村道路多为直角转弯情况，我们采用“曼哈顿距离”计算节点间行驶距离，公式为：$d_{ij}=\left|x_i-x_j\right|+\left|y_i-y_j\right|$ (km)。

Table 2. Farmers’ demand and coordinate data

表2. 农户需求与坐标数据

农户编号	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
需求量$q_i$	2	3	1	4	2	1	3	3	1	4	1	3	2	2	4
坐标(x, y)	(10, 8)	(15, 12)	(8, 15)	(12, 5)	(−10, 7)	(−8, 14)	(−14, 5)	(−9, −8)	(−13, −5)	(−7, −12)	(9, −7)	(14, −6)	(7, −13)	(3, 7)	(−4, 6)

本文采用Python实现遗传算法，实验运行电脑安装Windows 10操作系统，处理器Intel(R) Core i5-10500 CPU@ 3.10GHz，算法参数设置为：种群规模$N_{pop}=70$ ，交叉概率$P_c=0.85$ ，变异概率$P_m=0.07$ ，最大迭代次数$G_{\max }=1000$ ，车辆最大容量$Q=15$ 。为了实验结果可靠性，对算法进行10次实验并取平均值，如表3所示，遗传算法优化后的总行驶距离为218.2 km，较贪心算法的236 km减少了17.8 km，直接减少了燃油消耗与车辆损耗。使用贪心算法得到的行驶路径如图3所示，图4是10次实验中优化效果最好的一次行驶路线图，不同颜色代表不同的车辆，总行驶距离减少了28 km，从一定程度上减轻了车辆往返偏远农户的绕路问题。

Table 3. Statistical results of 10 experiments

表3. 进行10次实验的结果统计

实验次数	贪心算法	遗传算法 + 贪心算法	最优路径
1	236.00 km	216.00 km	[0, 9, 8, 10, 15, 0]; [0, 13, 11, 12, 2, 3, 14, 0]; [0, 7, 5, 6, 1, 4, 0]
2		216.00 km	[0, 4, 1, 12, 11, 13, 0]; [0, 15, 10, 8, 9, 0]; [0, 14, 3, 2, 6, 5, 7, 0]
3		224.00 km	[0, 15, 10, 8, 9, 0]; [0, 13, 11, 12, 7, 5, 6, 0]; [0, 14, 1, 3, 2, 4, 0]
4		208.00 km	[0, 9, 8, 10, 15, 0]; [0, 14, 2, 3, 6, 5, 7, 0]; [0, 1, 4, 12, 11, 13, 0]
5		224.00 km	[0, 15, 10, 8, 9, 0]; [0, 12, 11, 13, 7, 5, 6, 0]; [0, 14, 1, 3, 2, 4, 0]
6		228.00 km	[0, 14, 1, 3, 2, 4, 0]; [0, 15, 8, 10, 9, 0]; [0, 13, 11, 12, 7, 5, 6, 0]
7		224.00 km	[0, 13, 11, 12, 7, 5, 6, 0]; [0, 14, 1, 3, 2, 4, 0]; [0, 15, 10, 8, 9, 0]
8		224.00 km	[0, 14, 1, 3, 2, 4, 0]; [0, 15, 10, 8, 9, 0]; [0, 7, 5, 6, 13, 11, 12, 0]
9		210.00 km	[0, 7, 5, 6, 3, 2, 14, 0]; [0, 15, 9, 8, 10, 0]; [0, 1, 4, 12, 11, 13, 0]
10		208.00 km	[0, 14, 2, 3, 6, 5, 7, 0]; [0, 15, 10, 8, 9, 0]; [0, 13, 11, 12, 4, 1, 0]
总行驶平均距离218.2 km

Figure 3. Distribution route of the greedy algorithm

图3. 贪心算法配送路径

Figure 4. Distribution route of the genetic algorithm combined with the greedy algorithm

图4. 遗传算法 + 贪心算法配送路径

5. 结论与展望

本文针对农村电商末端配送环节中“配送点到农户”的路径优化开展研究，设计了考虑运输工具容量限制的路线优化模型，设计了适配农村场景的遗传算法，通过遗传算法与贪心算法相结合提高车辆路径问题解决效率，用贪心算法提供高质量初始解，用遗传算法进行全局优化，既保留了贪心算法的高效性，又发挥了遗传算法的寻优能力。改变传统思路，并通过实例仿真验证了算法有效性，得出以下结论：遗传算法与贪心算法相结合在农村电商末端路径优化中具有显著优势，相较于传统贪心算法能降低总行驶距离、缩短配送时间，可满足农村配送的实际需求。

本研究依旧存在一定的局限性，未来可从下面这些方向进一步深入挖掘，当下模型仅考量单一配送点，实际的农村电商物流过程中存在多个配送点，未来可对“多配送点协同路径优化”进行研究；现有的模型忽视了交通拥堵、车辆故障等不确定状况，未来可在目标函数里加入风险成本项，使优化后的路径在遭遇不确定状况时仍可维持较高的可行性；伴随农村电商数据逐步积累，未来可把遗传算法跟大数据分析、人工智能技术联合起来，实现“预测–优化–执行”全流程的智能操作，优化农村电商物流末端配送环节的精准实施方案。