基于Dijkstra 算法的农产品物流节点选址研究

黄建新，陈姣敏，宾 厚

（湖南工业大学 商学院，湖南 株洲 412007）

随着经济不断地发展，人们对于饮食的追求越来越追求健康与天然。而真正天然健康的食品大多来自于广大的农村地区，但对于农村习以为常的农产品在居住在城镇的居民看来许多农产品的价格常常让人望而却步。一方面，在农产品生产地附近许多农产品由于交通不便和不能找到适合的农贸市场进行交易而只能看着其腐坏或是以较低的价格进行交易，造成许多农民和农产品从业人员“丰收不丰产”的现象时常发生。尤其对于交通不便利、信息较为堵塞的经济不发达地区的农产品生产者而言造成了极大地损失，对于地方经济也造成较大的损失。另一方面，物流节点之间的距离和交通状况对农产品物流能否顺利进行也有重要的影响。

对于农产品物流的研究最早是1901年Juhn F.Cruweli[1]为美国政府提供了其研究报告《农产品流通产业委员会报告》中分析了农产品配送过程中物流成本的影响因素，为农产品物流的研究提供了基础。而对于物流节点的选址问题是在1909年Alfred Weber 提出的。近年来，国内外学者对农产品物流的研究主要有：2014年，M Suysal[2]分析了物流成本中运输过程的主要影响因素和农产品自身的易腐性，提出了从物流基础设施建设、政府的税收制度和减少车辆运作过程中的排放量等方面来提高农产品农产品物流发展的效益。2015年，Han Gwan[3]为了寻找能有效降低农产品物流损耗的方法，对生鲜农产品进行了研究。2016年，Mark[4]在研究农产品物流时，提出了农产品物流体系中冷链物流是提高农产品物流效率的有效方法，同时对基于WSN 的水产品的温度控制系统进行了优化从而减少其在运输过程中的损耗。2016年张迎迎等[5]利用马氏距离改进的TOPSIS 法对云南物流节点进行选址研究，避免了指标的量纲和相关线性的影响。2017年，刘明菲等[6]通过改进灰色关联法对农产品冷链物流脆弱性的暴露性、敏感性和适应性等影响因素进行了分析并以实际区域的农产品冷链物流的脆弱性进行了评价。2018年，高芳杰等[7]通过灰色预测模型对农产品物流的需求量进行了预测分析。2018年，王璐璐等[8]通过Lingo 对包装废弃物采用改进的p-中值法优化其选址研究。2018年，李义华等[9]从供给侧结构性改革出发，通过利用云计算等技术提出了基于“互联网+”环境下的生鲜农产品智慧冷链物流体系优化方案。2019年，王军和李红昌[10]通过中间层组织理论对农产品冷链物流进行分析,提出通过减少逆向交易和道德风险来降低物流交易成本同时建议提高行业的信息化水平。

单源物流节点选址通常会采取重心法进行选址分析，但重心法选址所考虑的距离通常情况而言是欧式直线距离，对于山路崎岖的地区而言，其距离通常与欧氏距离产生一点的误差。本文在前人研究的基础上，从运筹学的角度出发，以零陵区为例运用Dijkstra 算法对农产品物流节点选址进行分析求解以得到农产品物流的最佳选址方案。

1 Dijkstra 算法的基本原理

Dijkstra 算法是一种单源最短路径算法，通常用于计算一个节点到其他所有节点的最短路径，分为有向图最短路径算法和无向图最短路径算法。有向图最短路径算法基本的运作原理如下：

定义设D={U,A}是有向图，若A中的弧a与U中顶点uiuj相关联，且弧a的方向是是从ui指向uj，则称ui为a的起点，uj为a的终点，弧a可记为uiuj。

若有向图D={U,A}的弧集A中每一条弧a均赋予一个实数w(a)，则称此图为赋权有向图。

设P是有向图D中一条从ui到uj的路，P中所有弧的权志和称为路P的权，记为w(P)。

若P是从ui到uj的所有路中权最小者，则称P是从ui到uj的最短路线。

设网络图的起点是us,终点是ut,以ui为起点uj为终点的弧记为（i，j）,距离为cij；

设有向图D={U,A},其中U={u1,u2,u3,…,u |U|},求点u1各点的最短路线，wij为弧uiuj的权，Dijkstra算法如下：

步骤（1）令P={u1},T={u2,u3,…,u |U|},且u1=0，uj=w1j,j=2,3,…,|U|。（2）在T中寻找一点uk,使得uk=min{uj}(j∈T),令P=P∪{uk},T=T{uk},若T=∅,终止；否则转到（3）。（3）对T中每一点uj，令uj=min{uj,uk+wkj},返回（2）。

若u1uj不是D中的弧，则令wij=+∞，（3）式中的wkj也是类似处理。有向图最短路径算法如图1所示。无向图最短路径算法相较于有向图而言不受固定流向的控制，在算法步骤上与有向图大致一样。求无向图最短路径时，将有向图最短路径算法步骤（2）改为：在T中寻找与u1相邻的一点uk，使 得uk=min{uj}(j∈T),令P=P∪{uk},T=T{uk},若T=∅,终止；否则转到（3）。无向图最短路径算法如图2 所示。

图1 Dijkstra 算法有向图

图2 Dijkstra 算法无向图

2 农产品物流节点选址的主要影响因素

2.1 交通运输条件

交通运输条件的好坏直接影响着物流节点能否顺利将物品输送与接收。常见的5 种运输方式：水路运输、公路运输、铁路运输、航空运输、管道运输，物流节点附近应该拥有这其中的一种及以上的运输方式，以便物品能通过一种以上或多种运输方式进行多式联运从而达到远距离的运输。同时，交通道路的承载力、道路的平整度以及交通拥堵的情况等对于物流的运输起着重要的作用。

2.2 物流响应能力

响应能力是整个物流过程能够有效应对各种状况不可或缺的能力。由于市场变化的多样性、农产品受天气影响具有的季节变化性以及农产品自身的易腐性等都会导致其在整个供应链过程中出现许多的突发情况，物流节点能够根据市场消费者和原材料生产供应者以及流通过程中的变化而能够迅速做出反应并给出相应的解决方法才能够保证物品正常的流通。物流响应能力是伴随着信息化水平的不断提高而提升的。物流节点靠近农产品生产地或者靠近消费者市场对于物流节点能够及时有效地了解实际情况，并迅速针对当前情况给予适当的调整或解决方案。

2.3 基础设施

物流节点自身及周围的基础设施对于物流节点而言有着明显的辅助作用。基础设施的配套与否关系着物流节点能否顺利进行物流运作。物流节点的车辆装载与停放场地、特殊农产品的冷藏库、农产品的暂存库、周围基础的网络设施、周围配套的电力设备与设施等都与物流节点能否正常进行运作有着千丝万缕的联系。对于农产品物流节点而言，最好是靠近农贸交易市场，市场周围一般都会有相应的配套设施。农产品物流节点选址此外还受到物流节点的地质地形、气候、当地政府的法律法规和政策、地价租金、生态环境、劳动力人口和劳动成本、当地的习俗文化和经济发展状况等多方面的影响。

3 案例分析

3.1 零陵区交通道路情况和农产品分布情况

永州市零陵区位于湖南省南部，是永州、邵阳、衡阳、郴州、桂林、连州等城市网络中心点，其经济辐射面可达湘、桂、粤3 省，并已成为这一区域的交通运输、休闲旅游、商贸流通、信息传递和文化教育中心。西与东安县、广西全州交界，东连祁阳，南接双牌，G207、G322、S212、S216、衡枣高速以及洛湛铁路穿越全境，零陵城区距零陵机场7km,距湘桂铁路永州站18 km。道路交通路线图如图3 所示。

图3 零陵区道路交通路线图

零陵区包括城区在内一共有11 个区镇乡，其中城区有4 个街道、7 个镇、3 个乡。可将其划分为三个经济区：东部经济区、中部经济区、西部经济区，农产品的主要产地在东部和中部经济区，主要的农产品有稻谷、红薯、黄豆、油茶、杉木,楠竹大米、中药材、蔬菜、生猪等；西部经济区主要利用其自身土地丰富的矿产资源进行开采与加工。根据2018年《永州市零陵区2018年国民经济和社会发展统计公报》显示，零陵区粮食作物总播种面积89.3 万亩，粮食总产量36.7 万t，蔬菜种植面积38.5万亩，水果总产量21.6 万t。猪、牛、羊出栏分别为74.97 万头、2.34 万头和7.15 万只，家禽出栏993.0万羽，水产品总产量1.9 万t。所以该区的农产品的生产量和发展都较为可观。

3.2 零陵区农产品物流现状存在的问题

道路崎岖。一方面，“十里不同音”在山地丘陵地区是十分正常的。由于零陵区的地形以丘陵为多，一些乡镇之间的欧氏距离（理论直线距离）较近但实际距离有较多的崎岖山路，从而两个从地图上看很近的乡镇实际能到达的距离却较远。将农产品从农产品生产地运往消费市场存在一定的难度。另一方面，由于道路崎岖造成当地人们对外界许多事情的闭塞，大部分农产品只在当地进行交易，这样使得从事农业生产者的经济收益停留在一个较低的水平。

响应滞后性。零陵区农产品物流交易的方式主要还是以传统的交易方式进行交易。城区的农贸市场的农产品每天都有往来交易，其农产品大多数也经过好几轮的中间商的流通最终才能到消费者面前。农产品具有一定的易腐性和季节性。城区以外各乡镇的农贸市场由于主要还是以传统的交易方式进行交易，使得农产品物流具有一定的滞后性。同时，许多农产品生产者打算将应季成熟的农产品进行出售时未能在乡镇赶集的日子，只得等到赶集的时候才能将农产品进行出售或者将地里的农产品收上后尽快运往城区。无论是等待赶集日还是运往城区都存在一定的滞后性，一个是时间上的滞后性，一个是空间上的滞后性。

基础设施设备落后。城区内的农产品物流的基础设施相较于各乡镇而言较先进，但同样也存在着一定的缺陷。大多数的农产品的储存需要配套的冷藏处理，而城区专业的冷库或冷藏处理中心较少，各乡镇专业的冷藏设施设备更少。这导致一些农产品由于在物流途中暂存的时候未能做好相应的保护措施，最终只能低价出售或损毁，直接着影响相关从事者的利益。

由以上分析可知，在零陵区建立一个农产品物流中心以帮助农产品生产者增加经济收益和为消费者提供天然实惠的农产品是十分有必要的。

4 基于Dijkstra 算法的农产品物流节点选址优化

由于零陵区的山茶油质量较好，作为当地的特色农产品之一，所以现拟在零陵区这11 个乡镇及城区的节点找一处建立一个山茶油农产品物流中心，通过Dijkstra 算法对这11 个节点进行优化从而得出适合建立山茶油农产品物流中心的地址场所。

4.1 零陵区各乡镇之间的的距离

本文通过高德地图定位导航得出的零陵区各乡镇之间的车辆行驶时间最少的距离并将其整理编制成表格。具体如表1 所示。

表1 零陵区各乡镇车辆行驶距离 km

4.2 构建路径节点图

将11 个乡镇（区）分别用a、b、c…j、k 表示，其中具体表示为：a:城区；b:水口山镇；c:珠山镇；d:黄田铺镇；e:富家桥镇；f:菱角塘镇；g:邮亭圩镇；h:石岩头镇；i:大庆坪乡；j:梳子铺乡；k:凼底乡。其无向图如图3 所示。

对比物流节点的距离表和无向图，多个物流节点的首尾节点的距离与多个物流节点之间相邻物流节点距离的和有些许差距，其主要原因是路径选择的不同。有些镇与镇之间并没有相应的国道或县道能够直接相连接，这种情况下只是乡道将两个镇之间进行直接的连接，或者通过其他乡镇作为衔接点进行农产品交易往来，而通过其它乡镇作为衔接点也有多种选择方式。

图3 零陵区各乡镇距离Dijkstra 算法无向图

4.3 基于Dijkstra 算法的农产品物流节点选址优化

分别以每个物流节点为初始点，其他节点为终点采用Dijkstra 算法进行计算以求出每个物流节点到其它物流节点的最小权之和，比较每个物流节点到其它物流节点权和的多少。在此基础上，求出最小权之和最少的物流节点，再综合考虑物流节点周边的基础设施和交通条件选出合适的农产品物流节点，建立农产品物流中心。

以a 为初始点到其它物流节点最小距离之和,以下是具体求解步骤：

则以b为初始点到其他物流节点最小距离之和为：min∑{wb}=396；以c为初始点到其他物流节点最小距离之和为：min∑{wc}=340；以d为初始点到其他物流节点最小距离之和为：min∑{wd}=298；以e为初始点到其它物流节点最小距离之和为：min∑{we}=339；以f为初始点到其它物流节点最小距离之和为：min∑{wf}=369；以g为初始点到其他物流节点最小距离之和为：min∑{wg}=521;以h为初始点到其他物流节点最小距离之和为：min∑{wh}=421；以i为初始点到其他物流节点最小距离之和为：min∑{wi}=524；以j为初始点到其他物流节点最小距离之和为：min∑{wj}=328；以k为初始点到其他物流节点最小距离之和为：min∑{wk}=501。

由此可得出min∑{wd}=298，d黄田铺镇的最小权和最小。207 国道、322 国道、衡枣高速公路穿越黄田铺镇境内，其交通条件也是较为便利的。由于城区主要是人口聚集处，在城区内建设农产品物流中心需要考虑的土地使用情况。城市人口的增多，居民住房和商业用地将会越来越紧张，若在城区内建设物流中心其土地未来的延展性将不够柔和。所以农产品物流中心应尽量避免在城区内。黄田铺镇离城区距离19 km 左右，与城区互通国道和高速公路，约30 min 的车程即可到达城区内（火车经过城区内）、潇水河（汇入湘江河）附近码头和零陵机场。此外，黄田铺镇还设立电子商务公共服务站和农产品质量安全监管站，其农产品物流基础设施相对其他乡镇而言具有一定的优势。若在此建立农产品物流中心，整个零陵区的农产品不仅可以供区域内的人们消费，还可通过电子商务平台将本土的特色农产品销往外地，不仅可以帮助外地消费者买到绿色天然价格实惠的农产品，而且可以促进农产品生产者提高收益。

6 结束语

通过分析零陵区的农产品物流现状，分别以零陵区各乡镇作为物流节点的初始点利用Dijkstra 算法计算比较每个物流节点到其他各个物流节点的最小权和的大小，从中选出最小权和的物流节点，并对选出的物流节点的周围环境进行分析以判断是否适合在此建设农产品物流中心。

Dijkstra 算法适用于小范围的物流节点选址，由于是一种单源最短路径算法，因而不适合复杂的物流网络节点选址。但对于小区域的物流节点选址具有方便、高效、可实践性的优点。根据零陵区的经济发展现状、交通状况和丘陵地形等其它自身因素，对其使用Dijkstra 算法进行物流节点选址优化是较为合适和具有实用性的。在进行选址优化的同时也存在着不足，比如，未能对拟将建立的农产品物流中心进行成本的预算与分析。总体而言，利用Dijkstra 算法对小区域的物流节点选址对生产者、中间商、销售商和消费者具有一定的优势，能够帮助农产品生产者有效地将农产品运往外地，提高对消费者的服务水平，对整个区域经济的发展起着推动作用。