基于遗传算法的生鲜农产品物流配送路径聚类优化

王有鸿

(运城学院经济管理系，山西运城 044000)

随着国民经济的飞速发展，国内居民的生活品质不断提升，当前国内居民的膳食模式逐步由过去的温饱型向营养养生型转换。膳食模式是衡量国家和区域居民生活水准的重要指标，且对增强各年龄段人们的身体素质具有重要意义。生鲜农产品存在季节特征、地域特征和易腐败特征，这些特征给贮藏、运输、销售带来了挑战，并易于引发淡季食品供给不足、商品单调，旺季食品物流输送不顺畅等状况。为改变生鲜农产品的供需状况，须要最大化地满足居民对新鲜食物的需求。

目前我国的农业物流配送存在诸多问题，如配送渠道杂乱，配送过程开销大、时间长，且很多生鲜农产品配送企业往往采用传统的经营与输送方式，农产品物流输送效率低，运输过程消耗大，无法与当前的市场需求相适应。因而采用先进的科学技术组织生鲜农产品配送、规范车辆配送路径具有重要意义。对生鲜农产品企业来说，改进配送线路可提升配送效率，减少运输开销，并可迅速将农产品配送到顾客手中，提升顾客满意度，且能够节约配送车辆数目，缓和交通情况，保证生态平衡。车辆路径问题(vehicle routing problem，简称VRP)[1]对于生鲜农产品能否被准确运送具有重要作用，好的配送模式对于生产效率的提升具有重要意义，国内外研究者针对生鲜农产品的配送进行了大量解析和调研。Christiansen等对车辆路径状况进行了专门探索[2]；Santini等选取人工神经网络模式来实现车辆路径优化[3]；Paraskevopoulos等给出5种模式的车辆路径优化策略，分别为带时间约束的VRP模式、带能力限定的VRP模式、多配送核心的VRP模式、分批次配送的VRP模式以及开放性的VRP模式[4]；李军针对有时间窗的车辆路径优化状况提出一种利用旅行商问题的 C-W 算法来安排路线的启发式算法，并得到较好的效果[5]；郭森等把使用者分配在相同的车辆中，进而选取一种基于动态学习和突变因子的粒子群算法实现车辆分配，最后依照现有需要实现仿真测试[6]；殷亚等依照路径优化特性，利用遗传算法特点，构建出3种混合蝙蝠算法，能提升优化效能[7]。

国内外科研人员针对车辆配送路径的研究较多，但结合生鲜农产品提升农业物流效率的研究较少。本研究探讨基于遗传算法的生鲜农产品物流配送路径的聚类优化，以期实现高效和低成本物流。

1 生鲜农产品配送线路优化模型设立

1.1 生鲜农产品配送的车辆路径问题结构模型

车辆路径问题即针对各个需求配送点选取科学的车辆运输线路，从生鲜农产品配送核心起始，有序地通过需求配送点，并最终返回配送核心，其中货物的需求状况、车辆的限定、运行里程的限定以及时间限定等须达到相应的标准，如里程最小、开销最少、采用的车辆数目最少等。图1给出传统配送VRP模型。

1.2 带时间窗口的车辆路径模式

在VRP的基础上加入时间窗体限定，即将VRP拓展为有时间窗车辆路径问题(vehicle routing problems with time windows，简称VRPTW)。依据用户的满意程度可将时间窗体划分为硬时间窗体和软时间窗体[8]。

硬时间窗体即生鲜农产品配送车辆应在给定时间段内把配送物品运送至使用者所在地，如果使用者拒绝接受时间段之外的相关服务，则拟定相应的惩罚函数，若配送生鲜农产品在指定的时间内超出惩罚值，则超出硬时间窗体限定(图2)。

在硬时间窗体运输路径模式的配送过程中，生鲜运输车应当在恰当的时间点内达到配送点，若生鲜运输车在最早服务时间之前或最晚服务时间之后到达使用者所在地点，则会出现整体生产模式的延迟与空置，出现时间开销大而效率低的状况，并产生很大的惩罚值。

软时间窗体指配送车辆若不能把生鲜农产品在给定的时间内运达，则应对相应环节进行处罚[9](图3)。与硬时间窗体的车辆路径问题(vehicle routing problem with hard time window，简称VRPHTW)相比，软时间的路径窗体路径问题放弃了时间窗体限定，在现实中，由于路面交通流量、车辆的运转速度和使用者需要时间等不确定原因使得车间存储的生鲜农产品没有在给定的时间内到达使用者所在地，若采用硬时间窗体限定模式优化，则使开销增大。

本研究结合数学建模方法对生鲜农产品物流配送路径进行优化设计，采用生鲜运输车完成生鲜农产品配送核心与几个配送点之间的n个运输动作，假定现有生鲜运输车的容量为Q，生鲜运输车的固有车辆成本为h(h>0)，各个配送点的需求量为qi，令qi小于Q，此外规定任务起始的执行时间区，整个任务的需求时间为si，路段(vi，vj)对应的时间成本、运输时间分别为cij、tij。

时间窗体的设计准则是通过数学模型优化生鲜运输车的行驶路线，且在给定时间内开始操作并完成输送，从而使生鲜农产品派送的花销较少。

(1)

qi≤yipi≤Q,i=1,…,n；

(2)

tij+cij≤si。

(3)

式中：若选取特定路线(vi，vj)，则权值xij为1，否则为0；lj表示配送核心到车间距离；pi表示生鲜运输车的数量；yi表示生鲜运输车离开车间的运载量。

2 生鲜农产品物流配送路径遗传算法聚类优化设计

2.1 生鲜农产品物流配送路径遗传算法

遗传算法[10]的优势在于其中的群体搜索功能能够使种群中的各个个体之间进行数据传送，其模拟策略主要是由个体构建的群体学习策略，并且把与每个个体相关的研究状况形成解。该算法的步骤为：(1)对染色体进行编码，构建符合约束标准的染色体，进而获取相关初始种群并测算种群中各个染色体的适应模式，适应模式主要反馈染色体的优劣状况，遗传算法能够获取适应度较强的染色体；(2)对染色体进行选择，完成交叉和变异，并采用相关基准算子得到下一代种群；(3)重复步骤(1)、(2)直至达到终止条件。

遗传算法同时检索上一层的多个种群个体，并将初始染色体种群用作遗传，从而构建初始化种群的起点。各个个体将1～n之间的自然数排列形成一个序列，本试验采用初始化种群的模式获取popsize模式的初始种群，其中n为各个生鲜农产品的需求网点数目，popsize为整个种群的规模。

图4为一个赌局模型，整个赌局被分割为大小存在差别的扇面区域，指针能够转向各个区域，且指针停留在各区域的概率和各区域圆心角存在一定的比例，若圆心角较大则停留在该区域的概率较大，若圆心角较小则停留在该区域的概率也较小。

假设种群的规模为N，父辈种群Z={a1，a2，…，aN}，其中各个部分的适应程度为f，子群体的初始状况为X={}，并且给定各个部分的具体操作模式：把全部个体依照适应程度从大到小进行排列，则排序之后的种群为Z={b1，b2，…，bN}，且f(b0)>f(b1)>f(b2)>…>f(bN)，基于该模式测算得到父辈种群模式的适应层级；计算种群中全部适应层级的总和，得到各个个体被选取的概率；累积各个个体的概率得到累积值，完成轮盘的转动。

本研究依照VRPTW方式构建改进交叉方法的遗传策略，其算法的基本策略见图5。

2.2 生鲜农产品物流配送路径遗传算法聚类优化

若所需求的生鲜农产品量高于车辆单次运载的容量Q，则

(4)

式中：x为各个需求网点的生鲜农产品需求量。

测算步骤为：(1)设定初始循环次数为1，由于模糊聚类[11]阵列F为一个对称阵列，本研究选取三角阵列实现测算，并得到简化步骤；(2)针对模糊聚类阵列F，选最大部分进行循环，并将F设定为目标，进而给出三角阵列的测算实例(图6)。

本研究综合遗传算法，并结合聚类方法，对简化的VRPTW模式实现优化求取，其测算步骤为：(1)选取自然数编码模式构建可行的生鲜农产品运输线路染色体；(2)设定测控参量，其中设定交叉率为pc，变异状况为pm，群体规模为N；将遗传代数gen设定为0，即随机获取的初始种群p(0)中包含Num个染色体部分；(3)构建生鲜农产品运输的行车线路；(4)设定i的初始值为1，测算种群中第i个染色体的线路距离和适应程度，若达到算法的终止标准则停止，否则继续；(5)i进行自增加，若i小于n则返回步骤(2)，否则进行下个步骤；(6)依照使用层级复制下一代染色体，实现最大交叉保留状况，并且交换变异模式，进行gen的自增加，若满足终止标准则终止，否则转至步骤(3)。

3 生鲜农产品物流配送路径遗传算法聚类优化和分析

3.1 实例设计

本研究假定须配送19个生鲜农产品需求配送点(图7)，并将生鲜农产品配送核心的位置设置为(0，0)，圆圈表述各个需求配送点，编号间的距离表示网点之间的间隔距离。表1 为生鲜农产品需求配送点网点坐标以及需求数目，通过Matlab程序完成需求配送点在遗传算法聚类优化下的仿真。

3.2 生鲜农产品运输外部相似性测算

本研究进一步测算各需求配送点期待服务质量和生鲜农产品外部相似特点，并评判各需求配送点的期望服务质量和所运输商品的外部相似特性。生鲜农产品运输外部相似性见表2。

3.3 生鲜农产品物流配送聚类结果

聚类分类停止标准依照生鲜农产品关联性质和各需求配送点的货物运载状况设置，此处设定权值为0.6，生鲜农产品运输车的运载量为2 t，然后根据客户需求完成聚类测算。M为惩罚值，Q为生鲜运输车的容量。

从表3、表4可以看出，改变聚类方法的权重并结合Matlab实现编码，能够得到各种聚类结果，从而得到各种生鲜农产品的配送方式。

设定本研究中的遗传算法参量最大进化代数为100，种群的大小为52，交叉率为0.92，变异率为0.81，软时间窗体之下的待惩罚参量为2，延迟惩罚数据为3；在电脑上运行得到，最优配送间距为108 km，所采用的生鲜农产品运载工具数目最少为3辆，其所对应的最优化配送线路为路径1：0—13—14—7—1—19—6—0；路径2：0—7—15—8—2—25—6—0；路径3：0—10—11—3—1—5—6—0。表5为生鲜农产品配送方法的聚类优化结果。

3.4 组内路径求取结果

在整个算法中，遗传算法给定的参量设定模式：种群规模(N)为100个，最大迭代次数(C)为200次，交叉率(pc)为 0.89，变异率(pm)为0.03，惩罚参量为3。

表1 生鲜农产品配送网点坐标以及需求数目

表2 生鲜农产品运输外部相似性

表3 权重结果为W1状况时的聚类值

表4 权重结果为W2状况时的聚类值

本研究首先采用模糊聚类方法对客户进行分类，即对需求配送点1～19进行分类，共分为5类，其中需求配送点7、10、8、9、19、17为一类，需求配送点2、12、6、5、3为一类，需求配送点10、15、16、5为一类，需求配送点18、4、11为一类，需求配送点13、1、14为一类，然后采用遗传算法规划生鲜农产品运输线路。遗传算法得到的结果为近似的最优结果，不是最优结果，但能够通过选取多次执行代码得到较好的近似最优值。由表6可知，5类需求配送点得到的最优线路模式分别为：0—7—10—8—9—19—17—0，目标解析式数据为 9.121 km；0—2—12—6—5—3—0，目标解析式数据为 8.983 km；0—10—15—16—5—0，目标解析式数据为 8.512 km；0—18—4—11—0，目标解析式数据为8.892 km；0—13—1—14—0，目标解析式数据为9.053 km。

表5 生鲜农产品配送方法的聚类优化结果

依照各个车间对应配送核心(0，0)的坐标方位，以需求配送点7、10、8、9、19、17获取的最优线路模式0—7—10—8—9—19—17—0为例作图。

图8为遗传算法经过198次迭代之后获取的最优结果以及效能的追踪结果。因此在现实的操作中，应当适当削减终止的最大迭代数目。

3.5 本研究方法性能测试

由表7可知，本研究中的5条最优生鲜农产品配送路线的配送间距分别为9.120、8.984、8.512、8.891、9.050 km，它们采用的平均生鲜农产品运载工具数目均为3辆，平均满载率分别92.1%、93.1%、87.6%、91.1%、87.6%。

表6 实现一次运行的模式

表7 组内的最优线路

以需求配送点7、10、8、9、19、17组成的路径0—7—10—8—9—19—17—0为例，对比分析本研究生鲜农产品配送方法和传统生鲜农产品配送方法的结果。

由表8可见，本研究路径0—7—10—8—9—19—17—0测算方法的结果，不论为11次求解的平均结果还是最优测算结果均优于传统方法，本测算方法的最优间距为8.48 km，平均测算距离为 8.55 km，本方法选取的生鲜农产品运输工具平均为3辆；而传统方法的最优间距为10.3 km，平均测算距离为11.1 km，配送生鲜农产品的车辆恒定为4辆。此外，本方法能够动态决定选取生鲜农产品运输工具的数目，说明本方法具有优秀的特性，因而测算所得解的质量较高。

4 结论

在市场经济的大环境下，生鲜农产品的竞争尤为激烈，而生鲜农产品物流的中心环节在于配送，当前生鲜农产品的物流配送过程繁杂，货运种类和需求配送点多，交通路线复杂，在整个配送服务区域内所分布的配送网点不均衡。顾客对生鲜农产品的品质需求日益增加，而生鲜农产品配送企业仍采用以往的经营模式，使得农产品运输效率低。因而科学地规划输送路线完成生鲜农产品配送已成为社会和相关企业关注的重点。

表8 本研究与传统生鲜农产品配送方法的结果比较

本研究对生鲜农产品物流配送路径进行优化设计，并给出生鲜农产品配送VRP模式和带时间窗口的车辆路径模式，进而完成生鲜农产品物流配送路径遗传算法聚类优化，给出生鲜农产品物流配送路径遗传算法步骤和聚类优化方法，即首先设定初始循环数目，并通过模糊聚类阵列给出对称阵列，结合三角阵列测算得到简化步骤；在模糊聚类阵列中，选最大部分完成循环，并采用Matlab完成生鲜农产品物流配送路径遗传算法聚类优化试验设计。假定有19个生鲜农产品需求配送点应配送，通过生鲜农产品运输外部相似性测算生鲜农产品物流配送聚类结果、组内路径求取结果，并对本方法进行性能测试，结果表明，本方法明显优于传统配送方法。