基于运筹优化的河南省农产品运输路线问题研究

Research on Agricultural Product Transportation Route in Henan Province Based on Operation Optimization

摘要: 河南省农产品运输路线问题以总运输路线最短为目标函数，以销售点间的关系为约束条件，建立了农产品运输线路的整数线性规划模型，采用遗传算法和蚁群算法进行模型求解，结果比较发现，具有启发式概率搜索方式的蚁群算法易于寻找到全局最优解，因此使用蚁群算法确定最优的运输路线。本文对农产品运输路线进行统筹优化，降低农产品的运输成本，缩短物流时间，保证农产品的质量。

Abstract: With the shortest total transport route as the objective function and the relationship between sales points as the constraint condition, the integer linear programming model of agricultural product transport route in Henan Province was established. Genetic algorithm and ant colony algorithm were used to solve the model. The results showed that the ant colony algorithm with heuristic probabilistic search method was easy to find the global optimal solution. Therefore, ant colony algo-rithm is used to determine the optimal transport route. In this paper, the transportation route of agricultural products is optimized to reduce the transportation cost of agricultural products, shorten the logistics time, and ensure the quality of agricultural products.

1. 引言

在农产品的销售运输中，物流运输是最为关键的一环，近年来，国家已经大力推进“数商兴农”工程的实施，奋力推进乡村电子商务化，这大大促进了省河南相对不发达地区的农产品销售情况。随着农业生产机械化、现代化的发展，农业生产产量有了很大的提升，农产品的运输问题逐渐被人们所关注。传统的农产品物流运输主要依靠常温物流和自然物流，物流运输周期较长，中途转运次数较多，严重影响农产品的鲜活度和销售质量，这无疑造成了农业生产效益的降低。随着农产品销售渠道的增加，农产品的销售量得到突飞猛进的增长，随之而来的是物流运输中存在的诸多问题。

为了解决农产品物流运输问题，国内外许多学者针对农产品的物流运输进行了许多研究，其中大部分研究方向主要是农产品的供应链、局域物流或研究物流经济效益。如胡勇建立的SFC法和模拟退火算法求解定位–车辆路线问题 [1] ，汪寿阳等对集成物流管理系统中定位–运输路线安排问题的研究 [2] ，李祎嘉等通过因子分析法河南省农产品物流发展水平的研究 [3] ，张建喜等通过大数据技术对农产品物流管理研究 [4] ，王勇等通过因子分析对农产品供应链绩效进行评价 [5] ，张潜等提出的定位–运输路线安排问题的两阶段启发式算法 [6] ，李进龙等基于改进蚁群算法和免疫算法求解多配送中心路径优化问题 [7] 等。

在物流运输中，销售点的定位和运输过程的优化是关键问题。考虑到运筹优化在解决与数学有关的实际问题中的效果良好，为此，本文在查阅大量参考文献的基础上，运用了运筹优化的方法，如蚁群算法、遗传算法，完成了农产品物流运输的设计，合理安排了销售点的原址，运输路径的最优方法，确保了对整个运输过程进行合理调配，从而大幅度提升农产品物流运输效率，优化物流运输分配，以提升农业的生产效益。

经过对农产品流通各环节进行详细的调查，并进行合理分析，可以优化农产品流通的整体过程，降低损毁率、运输时间，提高农产品质量，从而提高农产品收益。对农产品的后期加工、销售进行调查研究，确定各农产品的加工去向，可以提高资源利用率，提高农产品地自身价值，进而提高农民收益。

2. 运输路线问题调查与分析

近年来，河南农产品的销售运输工作进步显著，取得了较好成绩，随着农产品销售渠道的增加，农产品的销售量得到增长，随之而来的是物流运输中存在的诸多问题：销售规模小，种类单一；销售产品加工程度低，缺乏创新；销售地区集中，市场风险大等问题。为解决这些问题，需要通过科学的运算分配、合理的运筹优化分析，控制农产品运输过程中的损毁率，逐步形成完善的生产、加工、运输、销售系统，降低农产品的积压量，增加农产品的销售量，从而保障农民的最大获益。

运输路线问题是对各个城市间的相对位置关系进行分析，确定最佳运输路线，使得经过所有城市的同时，运输路线的总距离达到最短。该类问题为旅行商问题(TSP问题)，1932年TSP问题出现以来，已经有诸多学者在研究相关领域的问题。曾经传统的经典优化算法经常被用来求解TSP问题的解，但是当城市数量较大时，就难以快速找到最优解。随着人工智能的发展，出现了许多独立于问题的独立算法，如蚁群算法、粒子群算法、遗传算法等等。这些算法通过模拟自然界的某些现象而得出求解复杂问题的新思路和新方法。在优化领域，这类算法的由于其很好的收敛性和有效性而被广泛使用。

3. 河南省农产品运输路线问题的优化模型

农产品从农产品产地向省内外各个地区以及世界各地运输。假设农产品物流运输车辆从农产品的产地1出发，要运输到农产品的各个销售点2，3，…，n，最后再返回到农产品的原产地1。图3所示为每个产地和销售点共计123个点位的经纬度坐标，车辆应按怎样的次序经过所有销售点，使得总运输距离最短或总运输费用最小。城市的经纬度坐标见图1。

Figure 1. Longitude and latitude coordinates

图1. 经纬度坐标

3.1. 整数规划模型的建立

把该问题表示成整数规划模型，引入0-1整数变量：

$x_{ij}=\{\begin{array}{l}1,路线是从i到j,且i\ne j\\ \text{0},其它情况\end{array}$

访问销售点i后必须要有一个即将访问的确切销售点；访问销售点j前必须要有一个刚刚访问过的确切销售点。用下面的两组约束分别实现上面的两个条件。

$\{\begin{array}{l}{\displaystyle \underset{j=1}{\overset{n}{\sum }}{x}_{ij}=1}j=1,2,\cdots ,n\\ {\displaystyle \underset{i=1}{\overset{n}{\sum }}{x}_{ij}=1}i=1,2,\cdots ,n\end{array}$

这样农产品销售运输路线问题转化成了一个混合整数线性规划问题， $S_{ij}\left(i\ne j\right)$ 表示两销售点间距离。

$\begin{array}{l}\min z={\displaystyle \underset{\begin{array}{l}i,j=1\\ i\ne j\end{array}}{\overset{n}{\sum }}{S}_{ij}{x}_{ij}}\\ \text{s}\text{.t}\text{.}\{\begin{array}{l}{\displaystyle \underset{j=1}{\overset{n}{\sum }}{x}_{ij}=1}j=1,2,\cdots ,n\\ {\displaystyle \underset{i=1}{\overset{n}{\sum }}{x}_{ij}=1}i=1,2,\cdots ,n\\ x_{ij}=0,1i,j=1,2,\cdots ,n\\ u_i\ge 0,i=2,3,\cdots ,n\end{array}\end{array}$

农产品销售运输线路问题实质为TSP问题，本文尝试采用遗传算法和蚁群算法对此模型进行求解，下面是遗传算法和蚁群算法的求解过程。

3.2. 遗传算法求解河南省农产品运输路线问题

遗传算法的求解步骤主要有五步：种群初始化、适应度函数、选择操作、交叉操作变异操作，流程图见图2。

Figure 2. Genetic algorithm flowchart

图2. 遗传算法流程图

使用遗传算法进行模型的求解时，本文分别考虑了销售点数量为25、35、50、75时的情况，下面是这四种情况的求解结果：

当销售点数量为25时，求解结果如图3：

Figure 3. When N is equal to 25

图3. N = 25时求解结果

当销售点数量为35时，求解结果如图4：

Figure 4. When N is equal to 35

图4. N = 35时求解结果

当销售点数量为50时，求解结果如图5。

当销售点数量为75时，求解结果如图6。

图3~6左图的横坐标为销售点的横坐标，纵坐标为销售点的纵坐标；右图的横坐标为迭代次数，纵坐标为最短距离。

由三次测试结果可知，随着销售点数量增多，路径总长达到收敛的迭代次数一直增加，并且开始趋近2000次；最短距离开始大幅度增多。由此可得，在销售点数量取值在35之后，遗传算法就不能很好的解决农产品运输路线问题，因此选择蚁群算法解决。

Figure 5. When N is equal to 50

图5. N = 50时求解结果

Figure 6. When N is equal to 75

图6. N = 75时求解结果

3.3. 蚁群算法求解河南省农产品运输路线问题

设整个蚂蚁群体中蚂蚁的数量为m，销售点的数量为n，销售点i与销售点j之间的相互距离为 $d_{ij}\left(i,j=1,2,\cdots ,n\right)$ ，t时刻销售点i与销售点j连接路径上的信息素浓度为 ${\tau }_{ij}\left(t\right)$ 。初始时刻，各个销售点间连接路径上的信息素浓度相同，不妨设为 ${\tau }_{ij}\left(0\right)={\tau }_0$ 。

蚂蚁 $k\left(k=1.2,\cdots ,m\right)$ 根据各个销售点间连接路径上的信息素浓度决定其下一个访问销售点，设 $P_{ij}^k\left(t\right)$ 表示t时刻蚂蚁k从销售点i转移到销售点j的概率，其计算公式如下：

$P_{ij}^k\{\begin{array}{l}\frac{{\left[{\tau }_{ij}\left(t\right)\right]}^{\alpha }\cdot {\left[{\eta }_{ij}\left(t\right)\right]}^{\beta }}{{\displaystyle \underset{s\in allo{w}_k}{\sum }{\left[{\tau }_{ij}\left(t\right)\right]}^{\alpha }\cdot {\left[{\eta }_{ij}\left(t\right)\right]}^{\beta }}},s\in allo{w}_k\\ 0,s\in allo{w}_k\end{array}$

其中，α为信息启发因子，值越大，则蚂蚁选择之前走过的路径可能性就越大，值越小，则蚁群搜索范围就会减少，容易陷入局部最优；β为启发函数重要程度因子，值越大，蚁群越就容易选择局部较短路径，这时算法收敛速度会加快，但是随机性不高，容易得到局部的相对最优； ${\eta }_{ij}\left(t\right)$ 为启发函数， ${\eta }_{ij}\left(t\right)=1/d_{ij}$ ，表示蚂蚁从销售点i转移到销售点j的期望程度。

蚁群算法流程图如图7：

Figure 7. Ant colony algorithm flow chart

图7. 蚁群算法流程图

3.3.1. 蚁群模型计算公式

蚁群算法中释放信息素的特点：蚂蚁循环系统模型。该模型中， $\Delta {\tau }_{ij}^k$ 的计算公式为：

$\Delta {\tau }_{ij}^k=\{\begin{array}{l}\frac{Q}{L_k},第k只蚂蚁从城市i访问城市j\\ \text{0},其它\end{array}$

其中，Q为常数，表示蚂蚁循环一次所释放的信息素总量；L_k为第k只蚂蚁经过路径的长度。

3.3.2. 求解过程

运输路线主要经过的销售点为各个地区的销售点，蚁群规模(蚂蚁数量) m = 123、信息素重要程度因子α = 1、启发函数重要程度因子β = 5、信息素挥发因子ρ = 0.1、信息素释放总量Q = 1、最大迭代次数iter_max = 200、迭代次数初值iter = 1。

运用Matlab求解结果如图8。

最短路径为：27 36 28107 29 31108104105 24 25 22 23 9110 26 86 83 85 87 91 63 92 42 40 65 62 64 67 66 68 69 43 44 41 90 89 88106101 95 98 97 84102 76 71 70 77 75 73109112123111120122113114116117 12119121115118 72 5 8 7 1 2 4 74 96 99103 93100 94 34 3 6 30 39 37 46 45 51 49 81 78 15 10 11 13 14 16 82 79 80 57 55 56 54 18 17 19 21 20 59 60 58 52 61 53 47 50 48 32 33 38 35 27

Figure 8. Matlab solution result

图8. Matlab求解结果

4. 总结

本文以总运输路线最短为目标函数，以销售点间的关系为约束条件，建立了整数线性规划模型，采用遗传算法和蚁群算法，利用Matlab进行模型求解，解决了农产品供应点选址问题和农产品运输线路问题，得出的选址结果和运输线路结果可以为农产品企业制定更优的销售与运输方案提供一些参考。

基金项目

国家基金项目(12101195)；河南科技大学大学生研究训练计划项目(SRTP: 2022225)。

NOTES

^*通讯作者。