基于GIS的农资物流配送线路优化算法研究

摘 要：农资物流具有较大配送复杂性，物流成本居高不下，本文引入GIS路线规划功能，结合了经典的三类优化算法，提出了混合算法，算法获得最优路线效率更高，并且通过算例对GIS下混合算法的有效性。

关键词：GIS;农资物流;物流配送;混合算法

传统农资物流包括农业生产资料（农药、化肥、农具与其他原材料）的运输、存储等过程，信息化的推进催生了现代农资物流，融入了信息处理，对农资物流流通过程中进行事前、事中与事后的全面控制，从而降低库存、缩短供货周期、减少物流配送成本耗费，节约经济成本。目前，对于农资企业，从小型作坊到大型企业有存在自营、连锁经营与第三方物流配送等三种主要物流模式，相对而言委托第三方更具专业性，对于物流配送成本控制更严格，配送规划也更科学，而另外两种模式缺不乏资源浪费、规划不科学等情形。但是，考虑到企业贸易壁垒、竞争关系与商业机密等因素，不少农资商户还是选择了如自营等耗费大成本的物流配送方式。

那么，不管何种模式，农资物流配送的成本浪费最多体现在哪个节点呢？不少学者认为物流配送成本增加很大程度上体现在配送线路规划不合理，导致绕远路，近路堵塞时间、油耗成本高，空车运输等情形。在路径规划中，一个好的规划算法起到决定性作用，研究中主流的算法有遗传算法、爬山算法与蚁群算法等，该三类算法各有特色，都有不足，并且对于动态道路信息不适应，GIS技术可以较好地提供道路实时信息，提供较好的线路展示功能，由此，本文将结合三种算法，开发一个混合算法，装载入GIS中，达到线路规划达到最高效、最优化、可视化效果。

一、农资物流引入GIS的必要性

现代物流配送中80%以上都会涉及得到复杂的空间地理数据，而且农资物流的配送数据更是涉及到时空数据转换，具有多尺度、维度与不确定性、海量特性，对于物流数据的处理变得越来越重点级。GIS（Geographic Information System）具有强大的地理空间信息的处理与分析能力，运用计算机与通信技术建立一个空间信息数据库，用户可以进行地理信息的查询、分析与处理，还具有预测、定位与监测功能。具体GIS在物流中的应用如下：

1.选址方面

GIS可以很好地整合CAD与数据库系统，使得地理信息数据访问变得非常轻松简单，在物流配送中心选址方面可以准确提供详细定位参考数据与跳过障碍物的拓扑信息，对于选址决策有很大的帮助。

2.配送线路规划

GIS支持实时的地理道路数据访问，对于信息的处理是实时的，对于动态线路规划有很大的帮助。传统的线路规划往往是静态的计算，而借助GIS可以获取路线实况来进行多次智能导航规划，使得成本最小，配送最高效。

3.电子地图显示

GIS在可视化空间展示方面较强，对于线路配送给用户以直观的、交互性强的线路指示软件应用，对于物流配送的实际操作支持较好。

随着现代物流追求高效运作、成本控制与追求安全性等需求高涨，将GIS运用于物流行业的需求也逐渐推高。将GIS引入农资物流可以促进物流配送线路规划、整合资源，提高配送率，有效降低成本与提高客户满意度，因此，将GIS引入农资物流具有必要性。

二、传统线路规划算法

较为经典的优化方法有遗传算法、爬山算法与蚁群算法。三种算法各有优劣，对于物流路径规划各有其长处，均运用了优化理论对最优解进行最优线路求解，获得线路规划满意解。

1.遗传算法

遗传算法运用了生物学中的优胜劣汰理念，模仿群体进化获得适应度最强的解，即满意解。算法首先将研究的对象视为多个个体，对个体进行编码操作，运用适应度函数对各个体进行交叉、变异等遗传操作，得到最优解的集合，进一步获得逼近最优解的满意解。启发式算法的有点在于效率高，算法通用性好。

（1）运用二进制方式进行编码。不同的编码方式将直接影响交叉操作，进而影响最优解的产生。不同的编码方式对进化的效率也是有影响的，编码方案的选定也具有一定的实践性。

（2）初始化种群。种群初始化的好坏对于种群的进化效率是有影响的，因此，需要提前设定相关参数，考虑到种群进化中的影响因素，提高初始化种群的合理性，支持快速进化。

（3）合理选择适应度函数。适应度函数的选择是遗传算法的关键，偏向于某个个体会导致收敛过度，若忽略个体特性，又会导致算法不能够及时地收敛，同样影响效率，因此，适应度函数的选择至关重要，需要考虑的因素较多。

（4）选择与交叉变异操作。以适应度值的大小为该个体的被选择概率进行选择操作，让适应能力最强的个体得以保留，将经选择操作留下的个体进行交叉操作，优势互补。为了保持多样性，进行变异操作，随机选择个体进行基因对换。

2.爬山算法

爬山算法是一种局部择优算法，是对深度优先搜索算法的一种改进，充分利用反馈信息辅助生成决策信息。该算法从开始节点出发，不断地与相近的节点做比较，若遇到更小的值则替换原节点，直到遍历完成，达到最优值。

爬山算法通过三步完成搜索，首先是初始序列，第二步根据代价值来进行领域最优解的筛选，最后获得最优解。

3.蚁群算法

蚁群算法模仿了蚂蚁群体觅食的行为，通过信息素的相互交流反馈获得最优路径。蚁群算法是一种模拟进化算法，其具有正反馈性与并行性特点，广泛地应用于各种网络规划与数据挖掘中。一般蚁群算法分四个步骤进行优化路径求解：

（1）初始化信息。合理地分配各条线路的信息量，根据对各条线路的预估做初始化的线路信息素分配。

（2）选择路径。设定概率转移函数，对于单只蚂蚁选择路径时使用该函数进行路径确定，并且对已经经过的路径线节点进行记录，避免重复。

（3）对于分配的信息数量进行更新。模拟蚁群在各条线路上的信息素变化情况，根据特定策略进行多条线路信息素更新，信息素浓的线路表明经过的蚂蚁多，此条线路更优。

（4）根据信息素的分布选择最优解。按照一定概率进行局部最优求解，在迭代次数结束时，获取全局最优解。

三、混合算法的提出

三种传统算法获得的均可能非最优解，均为迭代逼近最优解，如果目标函数形式发生变化则需要根据实际情况制定不同的搜索范围与规则，我们需要在迭代过程中不断吸取有利因素，保持基本模型结构，对搜素规则进行改进，开发出更加符合实际的算法。我们通过吸取三种传统算法的优点构建了如下混合算法，算法主要包括两个环节：运用遗传算法与爬山算法获取各路径的初始信息量;利用蚁群算法进行最优求解。

1.混合算法流程

（1）环节一步骤如下：

①设定目标函数，成本最小、路线最短等。

②随机生成一组编码，选定适应度函数。适应度函数选择比较关键，对于挑选优胜个体起到关键作用。

③进行交叉变异操作，令个体更具适应性。

④进行优胜劣汰操作，融合爬山算法与赌法。判断是否全局最优，直至迭代结束。

（2）环节二步骤如下：

①根据步骤一获得的最优解进行初始化处理，获取信息素初始化值。并设定迭代次数对于初始化有效控制。

②将若干蚂蚁置于对应的节点开始遍历，若已遍历完所有节点则进入步骤4，否则计算进入下一节点的概率。

③若约束条件满足则记录当前解，修改禁忌表，更新所有信息素。

④迭代至获得最优解，否则进入步骤2。

2.混合算法的构建

（1）目标函数设定如下：

■ （1）

其中■，■，■分别表示车辆权重、行驶路程与等待时间权重，■表示车辆■费用，■表示配送总路程，■表示车辆等待时间。目标函数综合了三种考虑，即车辆的出车、运输与时间三大成本，以最小化三类成本获得综合成本，当综合成本最小时我们获得的最优路径才是实际物流配送中所需要的真正最理想的配送路径。

（2）适应度函数的选择

适应度函数的选择比较关键，直接影响算法的性能，为了不使得收敛速度波动较大，本文采用较为简单的倒数方法设定适应度函数如下：

■，其中■是以上设定的目标函数，■为既定的权重。

（3）对蚁群算法的信息素进行初始化

通过遗传算法对路径上的信息素进行初始值设定

■ （2）

■与■分别表示运用遗传算法获得的最优解求解过程需要的信息素及求解模型中的信息素常量。

（4）转移概率计算函数

■ （3）

其中■表示第■个个体适应度函数，■表示■蚂蚁可以前往下一节点。

（5）更新信息素

■（4）

其中，■表示第■步边的■信息素，■表示信息素增量

■ （5）

其中■表示挥发信息素因子，而■则表示衰退系数。

■ （6）

其中，■代表信息素总量常量，■代表单只蚂蚁所经路径长度。

根据混合算法的流程，即两个环节8个步骤的计算，参考5个关键步骤，我们可以获得农资物流配送路径的最优结果，以下我们将通过一个实际算例来进行模拟计算，比较混合算法与三类经典算法之间的优劣，以证明混合算法的有效性。

四、算法模拟验证

假设有某农资物流配送中心，对30个不同的农资需求点进行配送，设定配送中心单车配送，负荷与其他参数都一样，各参数设定为：群体总数为50，总迭代次数30，交叉与变异概率分别为0.7与0.07，变异的调换次数为20，爬山次数设定为30，蚁群算法的启发式因子■设定为3，■期望值为7，■为0.7，■为0.00003，蚁群规模为50，迭代次数300次。

选择客户点P30为配送起始点，运用了matlab软件，进行了模拟混合算法得到配送路径，模拟结果如下。

图中红圈点为配送起始客户节点，连线表示配送线路，从中可以看出配送线路较为密集的地方集中在左下方，左下方客户节点分布密集，配送较为集中，花费的时间较少，而其他地方客户点较为分散，配送路径也较为疏散。

通过运用matlab模拟混合算法与遗传算法，获得算例各客户节点配送路线总距离图。按逆序先在城市配送P30-P29-P28-P27-P26五个客户节点，计算两种算法获得总配送距离，再配送P30-P29-P28-P27-P26……P20，计算总距离，依次类推，获得图2。

■

图2 两类算法配送距离图

通过图2可以看出混合算法起始15个客户点配送时所花费的距离较大，到后15个客户配送点是距离逐步缩短，而等全部配送完成时，总距离是各算法中最短的，花费的成本最小。

五、结语

农资物流配送具有大批量、复杂度高、分散分布等特点，对于农资物流的配送是一个生产实际有待解决的问题，本文基于三种优化算法，构建了一种混合算法，该算法具有全局考虑，效率更高等特点，运用该算法进行最优路径求解，获得了比三种经典优化算法更高效、距离更短的全局最优路径，模拟演算验证了混合算法的有效性。但是，本文未对多个配送点，动态的配送进行研究，而现实配送中可能存在多个配送点，多种类型的运输工具，组合式、动态的配送，因此，本文研究存在一定的局限性，对于该方面的研究有待进一步深入探讨的开展。

参考文献：

[1]洪运华.现代农资物流管理信息系统构建研究[J].物流技术，2010， （4）.

[2]陈浩，吴洁明.基Web GIS的物流电子商务与配送网络优化集成[J].计算机与现代化，2005，（3）：89-92.

[3]程赐胜，蒲云虎，吴颖.集成化物流选址-路径问题优化模型的算法研究[J].中南林业科技大学学报，2008，28（5）：113-118.