Dijkstra和关键路径AOE在农业经济管理中的应用研究

高羽佳，叶　勇

(安徽农业大学信息与计算机学院, 安徽 合肥 230036)



Dijkstra和关键路径AOE在农业经济管理中的应用研究

高羽佳，叶勇

(安徽农业大学信息与计算机学院, 安徽 合肥 230036)

在农业经济管理领域中，运筹学理论的应用明显“弱化”.分析了Dijkstra和AOE方法在农业经济管理活动中的运用,并通过两个例子进行了实证分析.研究发现，Dijkstra和关键路径AOE在农业经济管理中的应用价值较大，能够促进农业经济的快速发展，值得推广应用.

Dijkstra; AOE; 运筹学; 农业; 优化

随着我国城乡一体化进程的日益加快，农业经济管理已经成为了社会各界广泛关注的焦点问题.虽然农业发展过程中有较多值得优化的问题，但是学术界多注重于农业布局、农村产业结构等宏观经济领域的优化，而对微观农业问题的关注度相对较低，在农业经济管理领域中，运筹学理论的应用明显“弱化”[1].Dijkstra算法是典型的单源最短路径算法，用于计算一个节点到其他所有节点的最短路径.主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止.关键路径是指采用边表示活动(Activity On Edge)网络，简称AOE网络，每个顶点代表一个事件，事件说明某些活动或某一项活动的完成，边表示活动，权表示活动持续的时间[2].本文从微观角度入手，在农业经济管理领域中引入关键路径AOE技术和Dijkstra最短路算法，以此来为运筹学理论在农业中的应用打下基础.

1　Dijkstra和AOE方法在农业经济管理活动中的运用

1.1农产品物流体系中的运输问题

从农户种植场所中将水果、蔬菜、家畜等农产品运输到农产品制造基地或农贸市场时，运输目标往往希望能够在最小成本、最短时间内完成.由于农产品具有较为明显的易变质特征，因此，在不对运力约束、时间约束、运费约束进行考虑的情况下，提升农产品物流体系运行效率的主要措施之一就是寻求一条最短运输距离，而其中最有效的算法就是Dijkstra最短路算法[3].最短路问题的图形表示如图1所示，要从Vs地将农产品运输到Ve地，运输路径有多条，虚框内表示的是一条长度为lij的单路径(从i→j)，那么，需要找出从Vs地将农产品运输到Ve地的最短路径，我们用L(u)来表示最短路径，其计算公式如下：

(1)

Dijkstra最短路算法的具体步骤主要可分为以下5点，分别是：

(1)起点永久性标号P值p(Vs)=0，那么，其他所有点的试探性路径为：Ti=+∞(i=2,3,......n)；

(2)与起点相邻的点记为：Vsk(k=1,2,.....sm)，其中，sm是与起点相连接的节点个数.设定Tsk为Vs地到Vsk地的试探性距离，其计算公式如下：

Tsk=min(Tsk,p(Vs)+ls,sk)

(2)

(3)从Vsk点出发，来对与Vsk点相邻的点进行考虑，可将其记为Vsk,i(i=1,2,......skm)，其中，skm是与Vsk临近点的个数.

基于(2)将Tsk计算出来，那么最小的试探性距离可在原有的(sk-1)个试探距离和新增的skm个试探性距离中寻找.用Vs,k(1)来假设该点标号，则可形成一个全新的确定距离，设定为p(s,k(1)).

(4)初始点选择为p(s,k(1))，以此为基础来进行迭代搜索，迭代搜索的目标在于寻找出最小试探距离.一旦某点被迭代搜索确认为最小距离，那么所计算得出的Tsk值就不再是无限值，而是一个定值，且永远都不能改变[4].

(5)p(Ve)为最后确定的距离，也是被Dijkstra最短路算法公认的最短距离，那么最佳路径就可以据图形判定计算而得.

图1　最短路问题的图形表示

1.2农业生产计划中的网络制定

对于广大基层乡镇政府而言，“三农目标”在该地区的实现程度往往是会受到各项农业决策影响的.无论是农业技术推广，还是农民技术培训，亦或者建立当地特色生态农业，都离不开一系列的计划规划，而要实现这些计划规划，那么离不开先行步骤的支持和完成.针对这种情况，就需要引入AOE技术(关联路径搜索技术)，以便能够用最少的资金投入、最少的时间、最小的精力来达到最理想的效果[5].例如，不管是任何的农业生产过程，往往都需要经历回收账款、销售农产品、深加工农产品、采购种子化肥等一系列的过程，那么就可基于这些过程所需要耗费的时间、人力、物力、财力，以及先后顺序来对网络图进行构建[6].使用图的规则主要包括2点，第一，只有先发生了先行事件之后，才可以发生后续工序.工序前后顺序的表达如图2所示，工序 A是工序B的先行工序，将A(tij) 定义为权数，表示完成工序 A所需要的时间.第二，适当时可引入“虚工序”，其适用情况为存在着共同先行事件的需求，例如，只有在完成了“粮食订单签订”和“粮食加工”之后，才能够实施粮食销售.并行先行事件条件的AOE图规则如图3所示，工序 A、工序B之间没有因果关系，属于并行工序，但只有完成了工序 A、工序B之后，才能够完成工序C，因此，可引入虚工序4.在将网络图绘制完毕之后，需要对工序总时差进行计算，具体步骤主要可分为以下4点，分别是：

(1)对最早发生事件进行计算，用0来标记初始点时间，由i→j的最早事件为上一节点时间加上i→j花费时间，其计算公式如下：

(3)

由于虚工序所需要面临的先决条件有若干个，那么最早发生时间公式为：

(4)

(2)设定tl(j)为事件发生的最迟时间，对tl(j)进行计算，其计算过程实质上是第(1)步的逆向.

(3)对最晚开始时间和最早开始时间进行确定，计算公式为：

(5)

(4)工序时差R(i→j)可通过“最晚开始时间-最早开始时间”来获得，然后再对时差为0的工序进行寻找，并将其确定为关键路径[7].

图2　工序前后顺序的表达

图3　并行先行事件条件的AOE图规则

2　实证分析

例1：成都市沃尔玛超市与蒲江县碣石镇农民签订了蔬菜固定供货合同，用S来代表供出地，用E来代表超市所在地，供出地-超市间的物流体系如图4所示，存在着相互物流服务关系的农产品物流集散中心有6个，以权数表明不同地点间的距离，目前需要找到一条最短路径来运输蔬菜.

(1)有3家农产品物流集散中心(分别是农产品物流集散中心1、农产品物流集散中心2、农产品物流集散中心3)与供出地S直接相连.各自的试探性距离为：

由上可知，最小的是T(3)，那么可将3的距离确定为：P(3)=1.

比较全部的T(i)，假定T(1)=2 最小，那么可将1的距离确定为：P(1)=2，与农产品物流集散中心1直接相连的有农产品物流集散中心3、4、5 ，计算：

比较T值，假定T(2)最小，那么可将2的距离确定为：p(2)=3.与农产品物流集散中心2直接相连的有农产品物流集散中心4、6，

再确定p(4)=3.5，与农产品物流集散中心4直接相连的有农产品物流集散中心5、6，以及超市E，计算：

(3)对T值进行比较，发现T(6)最小为4.5，那么可确定P(6)=4.5.

由此可见，从供出地S到超市所在地E的最短路解为：s→1→4→e，最短运送距离为5.5.

图4　供出地-超市间的物流体系

例2：某粮食生产企业在生产运行过程中所涉及到的环节如表1所示，并且建立起如图5所示的AOE关键路径图.

表1　某粮食生产企业的涉及环节

图5AOE关键路径图

(1)te(i)最早事件可用公式(3)计算得出，计算方式为从左到右：

te(1)=0,te(2)= 5,te(3)=8,te(4)=7,te(5)= 8，te(6)= 15，te(7)= 21,te(8)= 25,te(9)= 28,te(10)= 33

(2)最迟时间tl(i) 可计算得出，计算方式为从右到左：

tl(10)=33, tl(9)= tl(10)-t(9,10)=28, tl(8)=25, tl(7)=21, tl(6)=15,tl(5)= 9, tl(4)=min(tl(6)-t(4,6), tl(5)-t(4,5))=7，tl(3)= 9, tl(2)= 5, tl(1)= 0

(3)各工序的最早开工时间tes和最迟开工时间tls可用公式(5)计算得出，

tes(1,2)=te(1)=0,tes(2,3)=te(2)=5,tes(2,4)=te(2)=5,tes(3,6)=te(3)=8,tes(5,6)=te(5)=8,tes(4,6)=te(4)=7,tes(6,7)=te(6)=15,tes(7,8)=te(7)=21,tes(8,9)=te(8)=25,tes(9,10)=te(9)=28

(4)对各工序的总时差r(i,j)进行计算

R(67)=R(78)=R(89)=R(910)=0, R(46)=0,R(12)=0, R(24)=0,R(56)= R(23)=1, R(36)=3.

基于定义来看，关键序列的特征为：总时差=0；因此，关键工序包括7个，分别是K(9,10)、I(8,9)、A(1,2)、H(7,8)、C(2,4)、G(6,7)、F(4,6).而工序B和工序D属于非关键工序.由此可见，对于技术准备、采购管理和农机管理三个并行工序而言，粮食原产品的采购时间是该企业生产效率的关键.那么可在不调整其他流程的基础上，对物流体系建设力度进一步加大，以便能够使采购时间缩短.此外，若效率压缩路径C之后，那么有可能会改变路径C的关键工序地位，那么需要对其进行重新测定，并且改进关键路径，这充分说明了优化具有动态性，而不是静态的[8].

3　结语

总之，Dijkstra和关键路径AOE在农业经济管理中的应用价值较大，能够促进农业经济的快速发展，值得推广应用.

[1]丁建国,刘晓媛,苏武峥,等. 基于灰色线性规划法的新疆南疆干旱区农业系统优化研究——以新疆和田县为例[J].中国农学通报,2012,(23):130-135.

[2]牛凯.中国农业结构调整的多目标线性规划模型研究[J].浙江农业学报, 2011,(4):108-113.

[3]盛秀艳,窦志伟.农业运输问题的表上作业法与图上作业法的比较[J].安徽农业科学, 2010,(14):56-60.

[4]杨志丹,李爱平,王怀民.基于Dijkstra算法的多属性资源搜索的一种实现方法[J].计算机与现代化,2016,(9):191-196.

[5]葛莉.基于最短路径Dijkstra算法多尺度道路网中优化路径规划方法的研究[J].湖北民族学院学报(自然科学版),2012,(3):181-185.

[6]Nachtigall K. Time depending shortest-path problems with applications to railway networks [J]. European Journal of Operational Research,2015,(4):171-178.

[7]Sung K,Bell M G H,Seong M, et al.Shortest paths in a network with time-dependent flow speeds[J]. European Journal of Operational Research,2014,(11):1811-1820.

[8]Xu M, Liu Y, Huang Q,et al. An improved Dijkstra’s shortest path algorithm for sparse network[J]. Applied Mathematics and Computation,2007,(9):2033-2041.

(责任编校：晴川)

Application of Dijkstra and AOE in Agricultural Economic Management

GAO Yujia, YE Yong

(College of Information and Computer, Anhui Agricultural University, Hefei Anhui 230036, China)

In the field of agricultural economic management, the application of operational research theory is obviously weakened. The application of Dijkstra and AOE in agricultural economic management is analyzed, and two examples are given. It is found that the application value of Dijkstra and critical path AOE in agricultural economic management is large, which can promote the rapid development of agricultural economy and is worthy of popularization and application.

Dijkstra; AOE; operational research; agriculture; optimization

2016-06-20

高羽佳(1980— )，女，安徽滁州人，安徽农业大学信息与计算机学院讲师, 硕士.研究方向：物流信息化.

F322;O22

A

1008-4681(2016)05-0106-04