程纪扬

（安徽财经大学，安徽 蚌埠 233030）

一、引言

蔬菜与其他商品相比，品种多、流通渠道较短、配送环节复杂。因此，配送过程的优劣直接影响蔬菜产业服务质量、物流效率和蔬菜产业收益的高低[1]。蔬菜配送是将新鲜的蔬菜从种植基地运送到销售点的过程，该过程中需要综合考虑各销售点的蔬菜需求量及蔬菜到达各销售点的路程远近、运输费用及产品耗损等要素，最终对蔬菜产业进行合理种植、拣选分装、配货运输等方面的优化，使蔬菜产业带来的经济利益达到最大[2]。对于一些中小城市，蔬菜种植采取以郊区和农区种植为主，为了保障城区蔬菜的供应，当地政府对蔬菜配送环节实施一定补贴政策[3]。然而，政府补偿是有限的，在既定约束下如何优化配送路径，不仅有效提高城区蔬菜供应的数量和质量，还能带动农区菜农种植蔬菜的积极性。本文以A市为例，利用Floyd算法求出A市各蔬菜种植基地到各销售点的最短距离，并利用Lingo软件进行线性规划操作，求出政府补偿约束下的蔬菜配送最优路径，以期为我国中小城市在政府补偿约束下蔬菜配送路径的优化提供一套行之有效的方法。

二、A市蔬菜配送问题提出

（一）问题描述

A市的人口近90万，该市在郊区和农区建立了8个蔬菜种植基地 （记为Ai，i=1,2,3，...,8），承担全市居民的蔬菜供应任务，每天将蔬菜运送到市区的35个蔬菜销售点（记为Bj，j=1,2,3，...,35）。 市区有 15 个主要交通路口（记为 Lm，m=1,2,3，...,15），在蔬菜运送的过程中从蔬菜种植基地可以途径这些交通路口再到达蔬菜销售点。如果蔬菜销售点的需求量不能满足，则市政府要给予一定的短缺补偿。同时市政府还按照蔬菜种植基地供应蔬菜的数量以及路程，发放相应的运费补贴，以此提高菜农种植蔬菜的积极性，对蔬菜产业起到宏观调控的作用。其中，运费补贴标准为0.04元/（吨·公里）。本文根据A市蔬菜配送相关数据（如表1、表2及表3所示），在政府所付的短缺补偿和运费补贴最少的条件下，为A市设计从蔬菜种植基地至各蔬菜销售点的蔬菜运送方案。

表1 蔬菜种植基地日供应量（吨/天）

表2 蔬菜销售点日需求量（吨/天）及短缺补偿（元/吨·天）

表3 各基地、销售点及路口之间的距离（km）

（二）算法的选择

本文旨在解决在政府补偿约束下的最短路径问题。最短路径问题是指用于计算一个节点到其他所有节点的最短路径[4]，主要特点是以起始点为中心向外层扩展，直到扩展到终点为止。解决这一类问题的方法有很多，包括Floyd算法、Dijkstra算法、SPFA算法等，其中最为常用的是Floyd算法。

Floyd算法是用于寻找给定加权图中顶点间路径最短的算法[5]，适用于 APSP（All Pairs Shortest Paths，多源最短路径），是一种动态规划算法，稠密图效果最佳，边权可正可负。由于Floyd算法简单有效，三重循环结构紧凑，对于稠密图，其效率要高于执行|V|次Dijkstra算法，也要高于执行|V|次SPFA算法。并且，Floyd算法容易理解，可以算出任意两个节点之间的最短距离，代码编写简单。因此，本文采用Floyd算法解决问题。

Floyd算法基本思想为：首先设置一个矩阵A（k），其中对角线元素全为0，其他ak[i][j]表示顶点i到j的路径值，k代表运算步骤，当k=0时：

A（0）[i][j]=arcs[i][j]

得出的矩阵称为临接矩阵，以后逐步的尝试在原路径的两顶点上增加其他顶点作为中心顶点，如果增加中间顶点后，新的路径比原来路径减小了，则用新的路径代替旧路径，并修改矩阵元素，否则不变。

（三）配送路径情况分析

根据A市蔬菜配送相关数据，利用Matlab编程绘制出蔬菜种植基地、交通路口、销售点之间的散点路线图，如图1所示。图中一共有58个节点（其中包括8个蔬菜种植基地，15个路口以及35个销售基地），通过Matlab软件绘图使得各基地、销售点、路口之间的距离一目了然。对图中的8个蔬菜种植基地的编号为 V1—V8；35个销售点的编号为 V9—V43；15个路口的编号为 V44—V58。

三、模型构建与求解

（一）利用 Floyd算法求出各蔬菜种植基地到各销售点的最短距离

在不含负回路的网络中，有节点 V1，V2，…，Vn，用 Wij表示节点Vi和节点Vj之间的连线长，用dij表示从节点Vi出发到节点Vj时的路长[6]。

改进算法步骤如下：

步骤1：作初始权矩阵D（0）

步骤 2：在 D（k）中，若 i=j，则 dij（k+1）=0；否则转至步骤 3。

步骤 3：若 dij（k）=∞ 或 dij（k）=∞（l=1,2,…,n），且 dij（k）≠∞,则 dij（k+1）=dij（k），否则转至步骤 4。

步 骤 4： 若 dij（k）≥dij（k）或 dij（k）≥dij（k）（l=1,2,… ,n 且 l≠i,j），则 dij（k+1）=dij（k），否则转至步骤 5。

步骤 5:若 i＜j，则

dij（k+1）=min{dij（k），{dij（k+1）dij（k+1）}，{dij（k+1）dij（k）}，{dij（k）dij（k）}}；

图1 路线图

否则

dij（k+1）=min{dij（k），{dij（k+1）dij（k+1）}，{dij（k）dij（k+1）}，{dij（k）dij（k）}}

若 dij（k+1）=dij（k）+dij（k）， 且 dij（k+1）＜dij（k），则 将 l 标 注 在 权 矩阵 D（k+1）中的元素 dij（k+1）的右下角，表明经过本次迭代后，节点Vi与节点Vj之间的最短路径经过节点Vi，并且路长 的 值 dij（k+1）。

步骤 6:若 D（k+1）=D（k），结束；否则 k=k+1，转至步骤 2。

利用MATLAB实现算法程序化，求得各蔬菜基地到各个销售点的最短距离如表4所示。

（二）建立模型

由表1及表2中的数据可知，市场的总需求量为360吨，而8个蔬菜生产基地的总产量仅为270吨，蔬菜的供给量小于需求量，市场处于供不应求的状态，此时利用Lingo软件进行线性规划操作，求出最优解。

设政府付出的费用为F,则F=F1+F2,F1为市场的短缺补偿费用，即各销售点对蔬菜的需求得不到满足时所获得的补偿，F2为调运费用。 则可知：F1=Pj×（bj-xij）

其中，i=1,2,…,8；j=1,2,3,…,35；Pj为第 j个销售点的蔬菜供给量达不到需求量时的单位补贴；bj为第j个销售点对蔬菜的需求；xij为第i个蔬菜生产基地运往第j个销售点的蔬菜量。

其中 i=1,2,…,8；j=1,2,3,…,35；c 为运输每单位蔬菜的单位距离花费；xij为第i个蔬菜生产基地运往第j个销售点的蔬菜量。sij为第i个蔬菜生产基地到第j个销售点的距离。所以目标函数最小费用为：

又因为市场处于供不应求的状态，每个蔬菜基地的供应量应全部运输到各个销售点，即：xij=ai同时各个基地运送到销售点的蔬菜量应小于其需求量，即：xij≤bj，其中ai为每一个蔬菜基地每天能够提供的蔬菜量，bj为每一个销售点每天需要的蔬菜量。所以，可规划函数为：

（三）模型的求解

利用Lingo程序求解模型，求得运送分配方案结果，具体内容如表5所示。

通过表2与表5的对比参照，得出各销售点的需要量的满足情况。如果未满足销售点需求量，使用短缺量乘以单位短缺补偿，进行简单的数学计算可以得出短缺补偿费用；再通过表2、表4与表5的对比参照，得出蔬菜配送过程中的运输路程与重量，得到的数值乘以运费补贴标准便得出调运费用。其中，运费补贴为0.04元/（吨·公里）。

表4 蔬菜基地与销售点的最短距离表

综上，可以得到：

短缺补偿费用：=42658.00

调运费用：=178.28

政府花费:=42836.28元。

表5 蔬菜运送数量分配方案表

通过模型的构建与求解，计算出政府支付的短缺补偿和运费补贴最少的条件下，花费为42836.28元。可见，政府在推进城市蔬菜供应的过程中，运用Floyd算法，不仅有效保障了城区蔬菜供应的数量和质量，同时促进农区菜农种植蔬菜的积极性，缓解财政资金补偿的不足，进而实现政府的民生工程目标。

四、结束语

以Floyd算法为核心设计并优化蔬菜配送系统，能够在蔬菜运送过程中找到一条从产地到市场的最佳运输路线，有效减少蔬菜运输过程中的产品损耗，提高配送效率并且符合蔬菜配送的时效性特点。在本文中，政府补偿约束下的蔬菜配送路径优化可理解为在原有的路径设计上增加政府补偿约束这一限制条件，使自然的蔬菜配送系统升级为政府调控下的蔬菜配送系统。政府利用补偿约束条件在宏观上对蔬菜配送系统进行调整，使其更加符合市场需求，同时也能有效预防系统长期运行中可能出现的弊端。与传统的蔬菜配送相比，路径优化后一方面可以缩短运输时间，从而保证蔬菜的新鲜程度，提高食材的安全度；另一方面，在经过充分计算后设计的方案，政府能够在支付最少的情况下完成任务，因此能够提升财政资金效用与自身行政效率。诚然，在实际的运输过程中，时间、气温、交通状况等各种受限参数也会对配送产生影响，这些分析工作有待进一步研究。

参考文献：

[1]王琳,杨莉,杨晓明.蔬菜绿色供应链配送优化研究[J].食品研究与开发,2016,37（22）:187-190.

[2]汪世志,张志清.城市蔬菜业的物流配送优化研究——以武汉为例[J].物流技术,2014,33（7）:110-112.

[3]姜思源,曹春玲,孟超,等.基于狄杰斯特拉算法的蔬菜种植和配送最优化[J].长春理工大学学报（自然科学版）,2017,40（3）:130-133.

[4]左秀峰,沈万杰.基于Floyd算法的多重最短路问题的改进算法[J].计算机科学,2017,44（5）:232-234.

[5]刘海洋,木仁.基于Floyd算法的公交专用车道设置路段分析[J].中国管理科学,2015,23（S1）:257-261.

[6]赵礼峰,梁娟.最短路问题的Floyd改进算法[J].计算机技术与发展,2014,24（8）:31-34.